Методы принятия управленческих решений (МПУР)

Методы принятия управленческих решений (МПУР) - раздел математики, занимающийся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами. Например. К заданному сроку требуется провести массовое обследование группы населения с целью выявления определенного заболевания. Для этого выделены средства, оборудование, персонал. Требуется разработать такой план обследования: установить число медпунктов, их расположение, вид, количество проведенных анализов, чтобы выявить максимальное число людей находящихся инкубационной стадии течения заболевания. Тема 1. Задачи линейного программирования (ЗЛП) План. 1. Понятие ЗЛП. 2. Графический метод решения ЗЛП с 2 переменными. 3. Графический метод решения ЗЛП с n переменными. 1. Понятие ЗЛП. Задача 1. Об использовании ресурсов (планировании производства) Для производства 2 видов изделий (стол и стул) используется 3 вида ресурсов (сырье, труд, оборудование): Вид ресурса Расход на 1 изделие Общее количество ресурсов Стол Стул Сырье 12 4 300 Труд 4 4 120 Оборудование 3 12 252 Прибыль от продажи 1 изделия 30 40 - Найти: сколько столов и стульев должно выпустить предприятие, чтобы использовать ресурсы не больше указанного количества и при этом получить наибольшую прибыль. Составим математическую модель для решения задачи. Обозначим x1 – количество столов, x2 – количество стульев. f()=30x1+40x2 →max (1) Функция вида (1): f()=c1x1+c2x2+…+cnxn → max (min) называется целевой. Ограничения вида (2): называется системой ограничений. Если целевая функция и система ограничений – линейные функции, то задача называется задачей линейного программирования (ЗЛП). Если хотя бы одна из функций нелинейная, то задачей нелинейного программирования (ЗНП). Решить ЗЛП – это значит найти оптимальное решение (оптимальный план): такие значение переменных x1, x2, … , xn, которые принадлежат области допустимых решений (плану) ЗЛП, т.е. обращают ограничения (2) и (3) в верные неравенства (равенства) и при этом целевая функция (1) достигает оптимума, т.е. максимума (max) или минимума (min). Если в системе ограничений (2) содержатся только уравнения, то такая ЗЛП называется канонической, если только неравенства – симметричной. 2. Графический метод решения ЗЛП с 2 переменными. Алгоритм 1. В системе ограничений (2), (3) заменить знаки неравенства на знак «=». 2. Построить все прямые. 3. Найти решение каждого неравенства, заштриховав соответствующую полуплоскость. 4. Указать область допустимых решений – многоугольник решений. 5. Построить вектор (c1; c2), выходящий из начала координат. 6. Построить линию уровня h-прямую, перпендикулярную вектору , проходящую через многоугольник решений. 7. Если требуется найти max целевой функции, то передвигать линию уровня в направлении вектора до крайней точки (если такая есть). 8. Если требуется найти min целевой функции, то передвигать линию уровня в направлении, противоположном вектору , до крайней точки (если такая есть). 9. Определить координаты искомой точки (точек) аналитически, составив и решив систему уравнений. 10. Подставить координаты точки в целевую функцию, найти оптимум. Пример. Решим задачу 1 графическим методом. f()=30x1+40x2 → max Решение: 1. 12x1+4x2=300 3x1+x2=75 (1) (0;75), (25;0) 4x1+4x2=120 x1+x2=30 (2) (0;30), (30;0) 3x1+12x2=252 x1+4x2=84 (3) (0;21), (84;0) x1=0 (4) x2=0 (5) 2. Построим все прямые. 3. Найти решение каждого неравенства: заштриховав соответствующую плоскость. 4. OABCD – многоугольник решений. 5. Построим вектор (30;40) 6. Построим линию уровня h. 7. Требуется найти max целевой функции, то передвигаем линию уровня в направлении вектора до крайней точки B. 8. – 9. Определим координаты точки B аналитически, составив и решив систему уравнений. B – точка пересечения прямых (2) и (3). B: 3x2=54 x2=18 x1+18=30 x1=12 B (12;18) 10. Подставим координаты точки B в целевую функцию, найдем максимум: max f()=30x1+40x2= f(12;18)= 30*12+40*18=1080. Определим расходование каждого ресурса: сырья – 12x1+4x2≤300 – 12*12+4*18= 216 300-216=84 труда – 4x1+4x2≤120 – 4*12+4*18= 120 120-120=0 оборудования – 3x1+12x2≤252 – 3*12+12*18=252 252-252=0 Таким образом, предприятие должно выпускать 12 столов и 18 стульев, чтобы получать максимальную прибыль в 1080 д.е., при этом объемы затрат на труд и оборудование будут расходоваться полностью, а на сырье оставаться в размере 84 ед. 3. Графический метод решения ЗЛП с n переменными. Графический метод можно применить, если ЗЛП удовлетворяет условию: n-r≤2, где n – число переменных, r – ранг матрицы системы ограничений. Алгоритм 1. Составить расширенную матрицу системы ограничений. 2. Привести ее к ступенчатому виду. 3. Найти ранг. Убедиться, что выполняется условие: n-r≤2. 4. Составить ступенчатую систему уравнений. 5. Выразить r базисных переменных через n-r свободных. 6. Выразить целевую функцию через свободные переменные. 7. Записать симметричную ЗЛП (систему ограничений в виде неравенств). 8. Решить ЗЛП графическим методом с 2 переменными. 9. Найти значения базисных переменных. 10. Записать оптимальное решение исходной задачи. Пример. Решить ЗЛП графическим методом: f()=-x1-x2+x3+3x4+7x5 → min Решение: 1. Составим расширенную матрицу системы ограничений: -1 1 1 2 -3 4 1 1 4 1 -8 3 0 1 1 0 -4 -4 2. Приведем ее к ступенчатому виду. -1 1 1 2 -3 4 1 1 4 1 -8 3 ~ 0 1 1 0 -4 -4 1 1 4 1 -8 3 + -1 1 1 2 -3 4 ~ 0 1 1 0 -4 -4 1 1 4 1 -8 3 0 2 5 3 -11 7 ~ 0 1 1 0 -4 -4 1 1 4 1 -8 3 0 1 1 0 -4 -4 *(-2)+ ~ 0 2 5 3 -11 7 1 1 4 1 -8 3 0 1 1 0 -4 -4 0 0 3 3 -3 15 3. Найдем ранг: r=3. Убедимся, что выполняется условие: n-r≤2: n=5, n-r=5-3=2≤2 4. Составим ступенчатую систему уравнений: 5. Выразим r базисных переменных через n-r свободных: r=3 – 3 базисных переменных: x1, x2,x3. n-r=2 – 2 свободных переменных: x4,x5. Из последнего уравнения системы выразим x3 через x4,x5: 3x3+3x4-3x5=15 x3+x4-x5=5 x3=5-x4+x5 Из второго уравнения выразим x2: x2=-4-x3+4x5 x2=-4-5+x4-x5+4x5= -9+x4+3x5 x2=-9+x4+3x5 Из первого уравнения выразим x1: x1=3-x2-4x3-x4+8x5= 3+9-x4-3x5-4*(5-x4+x5)-x4+8x5= 3+9-x4-3x5-20+4x4-4x5-x4+8x5= -8+2x4+x5 x1= -8+2x4+x5 6. Выразим целевую функцию через свободные переменные: f()=-x1-x2+x3+3x4+7x5 → min f()=8-2x4-x5+9-x4-3x5+5-x4+x5+3x4+7x5= 22-x4+4x5 f()=22-x4+4x5 → min 7. Запишем симметричную ЗЛП (систему ограничений в виде неравенств): или Из каждого уравнения удалим базисную переменную, используя правило: переменная со знаком «+» - «+» заменяет равенство на неравенство вида «≤», переменная со знаком «-» - «-» заменяет равенство на неравенство вида «≥»: + - ≤ - - ≥ В каждом уравнении базисная переменная со знаком «+», поэтому получаем неравенства вида «≤»: 8. Решим ЗЛП графическим методом с двумя переменными. f()=22=x4+4x5 → min 1) 2x4+x5=8 (1) (0;8), (4;0) x4+3x5=9 (2) (0;3), (9;0) x4-x5=5 (3) (0;-5), (5;0) x4=0 (4) x5=0 (5) 2) Построим все прямые. 3) Найти решение каждого неравенства: заштриховав соответствующую полуплоскость. 4) ABCDE – многоугольная область решений. 5) Построим вектор (-1;4) 6) Построим линию уровня h 7) – 8) Требуется найти min целевой функции, то передвигаем линию уровня в направлении противоположном вектору до крайней точки D. 9) Определим координаты точки D аналитически, составив и решив систему уравнений. D – точка пересечения прямых (2) и (3). D: 4x5=4 x4-1=5 x5=1 x4=6 D (6;1) 10) Подставим координаты точки D в целевую функцию, найдем минимум: min f()=22-x4+4x5= f(6;1)= 22-6+4*1=20 9. Найдем значения базисных переменных: x1=-8+2x4+x5=-8+2*6+1=5 x2=-9+x4+3x5=-9+6+3=0 x3=5-x4+x5=5-6+1=0 10. Запишем оптимальное решение исходной задачи: = (5;0;0;6;1), min f()=20 Симплекс-метод План. 1. Основные понятия симплекс-метода. 2. Алгоритм и пример решения ЗЛП симплексным методом с естественным базисом. 3. Алгоритм и пример решения ЗЛП М-методом. 1. Основные понятия симплекс-метода. Симплекс-метод – универсальный метод, позволяющий решить любую ЗЛП. Различают симплекс-метод с естественным и искусственным базисом (М-метод). Симплекс-метод также называют методом последовательного улучшения плана (допустимого решения), т.к. сущность метода в том, что сначала подбирают первоначальный план (допустимое решение), а затем переходят к новому до тех пор, пока не получат оптимальный. Симплекс-метод применяют для канонической ЗЛП (т.е. система ограничений (2) записана уравнениями). Чтобы из ограничений неравенств получить равенства, добавляют дополнительные переменные: со знаком «+» для неравенств вида «≤», со знаком «-» - для неравенств вида «≥»: + - ≤ - - ≥ Рассмотренный алгоритм составлен для ЗЛП на нахождение максимума! 2. Алгоритм и пример решения ЗЛП симплексным методом с естественным базисом. Алгоритм симплекс-метода с естественным базисом. 1. Записать ЗЛП в каноническом виде ( систему ограничений (2) в виде уравнений). Записать целевую функцию, включив дополнительные переменные с нулевыми коэффициентами. Пример. Решить задачу симплексным методом с естественным базисом: f()=30x1+40x2 → max Решение: 1. Запишем ЗЛП в каноническом виде. Т.к. все 3 неравенства системы ограничений вид а «≤», то добавим дополнительные переменные x3, x4, x5 соответственно в каждое неравенство со знаком «+»: Записать целевую функцию, включив доп. переменные с нулевыми коэффициентами: f()= 30x1+40x2+0x3+0x4+0x5 → max 2. Составить и заполнить симплексную таблицу. 1) В столбце «базис» записать базисные переменные. Базисными переменными следует брать такие, которые удовлетворяют 2 условиям: содержатся только в одном уравнении и принимают неотрицательные значения. В первой таблице (с номером 0) в качестве базисных берут дополнительные переменные, если они принимают неотрицательные значения. Пример. 12x1+4x2+x3=300 4x1+4x2+x4=120 3x1+12x2+x5=252 x3, x4, x5 – базисные переменные. 2) В столбце «/» записать коэффициенты целевой функции при соответствующих переменных. 3) В столбце «План ()» записать свободные члены. 4) В рабочей части таблицы соответствующей переменным, записать коэффициенты при каждой переменной из уравнений системы ограничений. Пример. Составим и заполним симплексную таблицу с номером 0. f()= 30x1+40x2+0x3+0x4+0x5 → max 3. Заполнить оценочную строку ∆j по формуле: ∆j=Zj – Cj= ∑ciaij – Cj Пример. Заполним оценочную строку ∆j: ∆0= z0-c0=∑ciai0 – 0=0*300+0*120+0*252=0 ∆1= z1-c1=∑ciai1 – 30=0*12+0*4+0*3-30=0 ∆2= z2-c2=∑ciai2 –40=0*4+0*4+0*12-40=-40 и т.д. № табл Базис Ci Cj План 30 40 Оцен. ограничение Q X1 X2 X3 X4 X5 1 2 3 4 5 6 7 8 9 10 X3 300 12 4 1 75 X4 120 4 4 1 30 X5 252 3 12 1 21 Оценочная строка -30 -40 1 X3 216 11 1 -1/3 19+7/11 X4 36 3 1 -1/3 12 X2 40 21 1/4 1 1/12 84 Оценочная строка 840 -20 10/3 2 X3 84 1 - X1 30 12 1 - X2 40 18 1 Оценочная строка 1080 6+ 4. Проверить выполнение критерия оптимальности. Если в оценочной строке рабочей части таблицы нет отрицательных значений, то полученное допустимое решение оптимально. В противном случае – не оптимально. Пример. Проверим выполнение критерия оптимальности. В оценочной строке рабочей части есть отрицательные значения, то допустимое решение не оптимально. 5. Выбрать наименьшую отрицательную оценку (если их несколько, то любую). Столбец с наименьшей отрицательной оценкой называют разрешающим S (его выделяют). Пример. Выберем наименьшую отрицательную оценку. Это ∆2=-40. Значит разрешающий столбец 2-й: S=2. Его выделяем. 6. Найти оценочные ограничения Q для каждой базисной переменной по формулам: 1) если и одного знака, то Q= 2) если и разных знаков, то Q= ∞ 3) если = , <0, то Q= ∞ 4) если =0, то Q= ∞ 5) если =0, >0, то Q= 0 Пример. Найдем оценочные ограничения Q. Сравниваем и . Он одного знака, применяем формулу 1): Q1==75 Q2==30 Q3==21 7. Из оценочных ограничений выбрать наименьшее. Если минимума нет, то ЗЛП не имеет решения. Наименьшее ограничение определяет разрешающую строку q (ее выделяют), на пересечении разрешающих строки и столбца расположен разрешающий элемент (его выделяют). Пример. Из оценочных ограничений выбираем наименьшее 21, значит разрешающая строка 3-я. Ее выделяем. Разрешающий элемент =12 (выделяем). 8. Осуществить переход к следующей таблице по правилам: 1) Записать новый базис: вместо базисной переменной в разрешающей строке записать переменную из разрешающего столбца остальные оставить те же и в тех же строках. Пример. Запишем новый базис: вместо базисной переменной в разрешающей 3-й строке запишем переменную из разрешающего 2-го столбца, т.е. вместо x5 запишем x2. 2) Для базисных переменных в рабочей части расставить «0» и «1»: «1» против «своей» переменной, «0» - против «чужой». Также расставить «0» в оценочной строке для всех базисных переменных. Пример. Расставим «0» и «1» для базисных переменных в рабочей части таблицы. 3) Заполнение строки для новой базисной переменной. Значения в этой строке получают из предыдущей строки q делением всех ее значений на разрешающий элемент. Пример. Заполним строку для новой базисной переменной x2. Значения разрешающей строки делим на разрешающий элемент =12: a30=252/12=21, a31=3/12=1/4, a35=1/12. 4) Все остальные клетки заполняем по правилу прямоугольника: aij= aij - aij ais aqj aqs Пример. Заполним остальные клетки: a10’= a10 - = 300 - = 300-84=216 300 4 252 12 a11’= a11 - = 12 - = 12-1=11 a15’= a15 - = 0 - = 0-= - 4 12 1 a20’= a20 - = 120 - = 120-84=36 a21’= 4 - =4-1=3 a15’= 0 - = 0-= - 9. Заполнить оценочную строку и проверить решение на оптимальность, т.е. выполнить пп. 3,4. Пример. Заполним оценочную строку ∆j: ∆0= z0-c0=∑ciai0 – 0=0*216+0*36+40*21=840 ∆1= z1-c1=∑ciai1 – 30=0*11+0*3+40*-30=-20 ∆5= 0*(- )+0*(- )+40* -0= Решение не оптимально, т.к. в оценочной строке рабочей части таблицы есть отрицательное значение. 10. Повторить алгоритм с п.5 Пример. Наименьшая отрицательная оценка ∆1=-20 определила 1-й разрешающий столбец: S=1. Его выделяем. Найдем оценочные ограничения Q. Сравниваем и . Они одного знака, применяем формулу 1): Q1=216/11=19+7/11, Q2=36/3=12, Q3=21/(1/4)=84 Из значений Q выбираем наименьшее: min (19+7/11; 12; 84)= 12, значит разрешающая строка 2-я q=2. Ее выделяем. Базисная переменная x4 выходит из базиса, а в новом базисе вместо нее будет x1. Строим новую таблицу с номером 2. 10. Новый базис: x3, x1, x2. Для базисных переменных расставляем «0» и «1». Вторую строку заполняем делением значений предыдущей разрешающей 2-й строки на разрешающий элемент =3. Остальные клетки по правилу прямоугольника. a10’= 216 - =216-132=84 a14’= 0 - = 0-= - a15’= - - = - += a30’= 21 - = 21-3=18 a34’= 0 - = 0 - = - a35’= - = += 10. Заполним оценочную строку: ∆0= 0*84+30*12+40*18=1080 ∆4= 0*(- ) +30* +40*(- )= 10 - =6 + ∆5= 0* +30*(- )+40* = Решение оптимально, т.к. в оценочной строке рабочей части таблицы нет отрицательных значений. 11. Записать оптимальное решение: в столбце «План » содержатся оптимальные значения базисных переменных, а в оценочной строке – максимальное значение функции (небазисные переменные при этом принимают нулевые значения). Пример. Запишем оптимальное решение: = (12;18;84;0;0), max f()=1080 Таким образом, предприятие должно выпускать 12 столов (x1) и 18 стульев (x2), чтобы получать максимальную прибыль в 1080 д.е., при этом объемы затрат на труд и оборудование будут расходоваться полностью (x4, x5), а на сырье оставаться в размере 84 ед. (x3). 2. Примечание. Если требуется решить задачу симплекс-методом на нахождение минимума, то отыскивается max- f(x), т.е. коэффициенты функции цели берутся с противоположными знаками. Алгоритм при этом не меняется. Оптимальное решение берется то же, а значение функции – с противоположным знаком. 3. Искусственный базис используется в следующих случаях: 1) когда естественный базис найти не удается (нет в уравнении переменной, которая содержится только в этом уравнении); 2) если базисная переменная в первоначальном допустимом решении принимает отрицательное значение. Искусственные переменные обозначают y1, y2, … . В функцию цели их записывают с коэффициентом – М, где М – очень большое число. Составляется Т-задача: найти max(min) T-функции: f()=f() – M (y1+y2+…+ym) Задача решается алгоритмом симплекс-метода с естественным базисом с дополнениями: 1) при переходе от одной таблицы к другой в случае, когда искусственная переменная выводится из базиса, то в следующих таблицах она не рассматривается; 2) если хотя бы 1 из искусственных переменных в оптимальном решении отлична от 0, то полученное решение не является оптимальным и функция не имеет экстремума; 3) если имеет решение Т-задача, то такое же решение имеет f-задача. Пример. Решить задачу М-методом. f()=x1 – 2x2+x3 → max Решение. В качестве базисной переменной только из 2-го уравнения можем взять переменную x3, поэтому в 1-е уравнение добавим дополнительную переменную y1. Получим следующую Т-задачу: f()=x1 – 2x2+x3 - M → max Базисные переменные: y1, x3. № табл Базис Сi Cj План 1 -2 1 -M Оцен. ограничение Q X1 X2 X3 Y1 1 2 3 4 5 6 7 8 9 Y1 -M 2 1 1 1 2 X3 1 5 1 4 1 5 Оценочная строка -2M+5 -M -M+6 3. Заполним оценочную строку ∆j: ∆0= z0-c0=∑ciai0 – 0=-M*2+1*5= -2M+5 ∆1= z1-c1=∑ciai1 – 1=-M*1+1*1-1=-M ∆2= z2-c2=∑ciai2 – (-2)=-M*1+1*4-2=-M+6 и т.д. 4. Проверим выполнение критерия оптимальности. В оценочной строке рабочей части таблицы есть отрицательные значения, то допустимое решение не оптимально. 5. Выбираем наименьшее значение. Это – М, значит разрешающий столбец 1-й (выделяем). 6. Найдем оценочные ограничения Q. Сравниваем и . Они одного знака, применяем формулу 1): Q1=2/1=2 Q2=5/1=5 7. min (2;5)=2, значит разрешающая строка 1-я (выделяем). Разрешающий элемент =1. В новой таблице вместо переменной y1 в базисе будет x1. Т.к. из базиса выводится искусственная переменная, то в следующей таблице ее не рассматриваем. 1 X1 1 2 1 1 X3 1 3 3 1 Оценочная строка 5 6 8. Составим новую таблицу. Базисные переменные: x1, x3. Расставляем «0» и «1» для базисных переменных. Заполняем строку новой переменной x1, разделив значения 1-й строки предыдущей таблицы на разрешающий элемент =1. Остальные 2 значения находим правилу прямоугольника: a20’= 5 - =5-2=3 a22’= 4 - = 4-1=3 Заполним оценочную строку. Решение оптимально. = (2;0;3), max f()=5 Транспортная задача (ТЗ). План. 1. Понятие ТЗ. 2. Алгоритм решения ТЗ. 1. Понятие ТЗ. ТЗ – частный случай ЗЛП. Рассмотрим ТЗ на примере. Пусть имеется 3 поставщика и 4 потребителя. Их мощности, затраты на перевозку единицы груза указаны в таблице поставок: 1 2 3 4 40 20 10 30 1 50 5 x11 6 x12 4 x13 2 x14 2 30 3 x21 2 x21 4 x23 1 x24 3 20 2 x31 3 x32 6 x33 5 x34 Найти объемы перевозок для каждой пары «поставщик – потребитель» чтобы выполнялись условия: 1) мощности всех поставщиков были реализованы; 2) спросы потребителей были удовлетворены; 3) суммарные затраты на перевозку были минимальны. Обозначим объемы перевозок , где i=1,2,3; j=1,2,3,4. Чтобы мощности поставщиков были удовлетворены, должны выполняться условия: (1) Чтобы потребители были удовлетворены, должны выполняться условия: (2) ≥0, i=, j= (3) Чтобы затраты на перевозку были минимальны, должно выполняться условие: f()=5x11+6x12+…+6x33+5x34 → min (4) В общем виде ТЗ записывается следующим образом: ограничения (1), (2), (3) в виде – где – мощности поставщиков, где – мощности потребителей. Целевая функция имеет вид: f()=c11x11+…+cmnxmn= → min (4), где – затраты на перевозку единицы груза от i-го поставщика к j-му потребителю. ТЗ называется закрытой, если мощности всех поставщиков равны мощностям потребителей: = В противном случае ТЗ называется открытой. 2. Алгоритм решения транспортной задачи. 1. Определение, является ТЗ закрытой или открытой. Если открытая, то добавить дополнительно фиктивного поставщика или потребителя с недостающей мощностью, чтобы ТЗ стала закрытой. Затраты на перевозку единицы грузов фиктивного поставщика (потребителя) принять равными нулю. В допустимом и оптимальном решениях фиктивного поставщика (потребителя) не учитывать. Пример. 1. Определим, является ли ТЗ закрытой или открытой: ∑=50+30+20=100, ∑=40+20+10+30=100 ∑=∑→ ТЗ закрытая. 2. Нахождение первоначального допустимого решения. Требуется определить объемы перевозок. Используется метод минимальной стоимости. Сущность его в том, чтобы предоставлять наибольшие объемы тем парам, « поставщик-потребитель», у которых наименьшие затраты на перевозку единицы грузов. Пример. Мощности потребителей Мощности поставщиков 1 2 3 4 40 20 10 30 u1 1 50 5 6 - 4 2 + u2 2 30 3 2 + 4 1 - u3 3 20 2 3 6 5 Клетки, в которых распределены поставки, называются занятыми (базисными), а остальные незаполненными – свободными (неосновными). Число занятых клеток должно удовлетворять условию: m +n -1, где m- число поставщиков, n- число потребителей . Пример: m+n-1=3+4-1=6 Должно быть 6 занятых клеток , а имеем 5 . Матрица поставок имеет вид : X1= Найдем значение целевой функции: f(x) = 5*20+6*20+4*10+30+2*20= 100+120+40+30+40=330 Если число занятых клеток меньше чем должно быть по условию, то найденное допустимое решение является вырожденным. Необходимо нужное число клеток сделать занятыми, добавив в них нулевые поставки. Занятой выбирают ту клетку, у которой: 1) затраты минимальны, 2) определить на следующем этапе из системы уравнений потенциалов. 3. Проверка допустимого решения на оптимальность. 1) Для каждой занятой клетки составить уравнение вида: +=, где , – потенциалы клетки, − потребители, – затраты на перевозку единицы груза. Пример: Обозначим потенциалы. Составим систему уравнений потенциалов: =0 v1=5 u3=-3 v2=6 u2=-1 v3=4 v4=2 Количество уравнений в системе должно быть m+n-1. В нашей случае должно быть 6 уравнений. Какое уравнение добавить узнаем из решения. Чтобы решить систему, одной из переменных присваивают любое значение. Пусть u1=0 Для нахождения нужного уравнения выбираем клетку с наименьшими затратами, например, (1;4). Делаем ее занятой. Добавляем в систему уравнение u1+v4=2 и находим все потенциалы. 2) Для каждой свободной клетки найти оценку: =ui+vj - Если все , то допустимое решение оптимально. В противном случае - не оптимально. Пример. Для каждой свободной клетки найдем оценку =u2+v1-=-1+5-3=1 =u2+v2-=-1+6-2=3 =u2+v3-=-1+4-4=-1 =u3+v2-=-3+6-3=0 =u3+v3-=-3+4-6<0 =u3+v4-=-3+2-5<0 Среди оценок есть положительные, поэтому решение не оптимально. 4. Переход к новому допустимому решению. 1) Выбрать клетку, в которой наибольшее положительное значение оценки (если таких несколько, то выбрать любую). Пример. Имеем клетку (2;2), т.к. наибольшее положительное =3. 2) Для клетки «организовать цикл»: соединить ее с помощью многоугольника с занятыми клетками. Пример. «Организуем цикл»: соединим ее с помощью многоугольника с клетками (1;2); (1;4); (2;4). 3) Расставим в выделенных клетках «+» и «-»: в свободной клетке «+», а в остальных по порядку «-», «+». Пример. 4) В клетках со знаком «-» выбрать наименьшие значение объема поставок. Пример. min (20;30)=30 5) Это наименьшее значение нужно прибавить в клетках со знаком «+» к объемам перевозок и вычесть в клетках со знаком «-». Свободная клетка становится занятой, а клетка с объемом перевозок 0 – свободной. Пример. 5. Составим новое допустимое решение и повторим пункты 3,4. Мощности потребителей Мощности поставщиков 1 2 3 4 40 20 10 30 u1 1 50 5 - 10 6 4 2 + u2 2 30 3 + 10 2 4 1 - u3 3 20 2 3 6 5 Матрица поставок имеет вид: X2= Целевая функция: f(x)= 5*20+4*10+2*20+2*20+10+2*20=100+40+40+40+10+40=270. Имеем 6 занятых клеток. Для занятых клеток составим систему уравнений потенциалов: =0 v1=5 u2=-1 v3=4 u3=-3 v4=2 v2=3 Для каждой свободной клетки найдем оценку =u1+v2-=0+3-6<0 =u2+v1-=-1+5-3=1 =u2+v3-=-1+4-4<0 =u3+v2-=-3+3-3<0 =u3+v3-=-3+4-6<0 =u3+v4-=-3+2-5<0 Среди оценок есть положительные, поэтому решение не оптимально. Переход к новому допустимому решению. Имеем клетку (2;1), т.к. =1>0. Организуем с ней цикл по клеткам (1;1), (1;4), (2;4). Расставим «+» и «-». В клетках со знаком «-» выберем наименьшее значение: min (20;10)=10. Это число прибавим в клетках со знаком «+» к объемам перевозок и вычтем в клетках со знаком «-». Мощности потребителей Мощности поставщиков 1 2 3 4 40 20 10 30 u1 1 50 5 6 4 2 u2 2 30 3 2 4 1 u3 3 20 2 3 6 5 5. Составим новое допустимое решение и повторим пункты 3, 4. Матрица поставок имеет вид: X3= Целевая функция: f(x)=5*10+4*10+2*30+3*10+2*20+2*20=50+40+60+30+40+40=260. Имеем 6 занятых клеток. Для занятых клеток составим систему уравнений потенциалов: =0 v1=5 u2=-2 v3=4 u3=-3 v4=2 v2=4 Для каждой свободной клетки найдем оценку =u1+v2-=0+4-6<0 =u2+v3-=-2+4-4<0 =u2+v4-=-2+2-1<0 =u3+v2-=-3+4-3<0 =u3+v3-=-3+4-6<0 =u3+v4-=-3+2-5<0 Среди оценок нет положительных, поэтому решение оптимально. Ответ: X*= Целевая функция: min f(x)=260. Задача 2. Решить ТЗ: Мощности потребителей Мощности поставщиков 1 2 3 ф 40 30 40 u1 1 25 3 2 u2 2 35 1 - 3 + u3 3 50 2 + 5 - Решение: 1. Определим, является ТЗ закрытой или открытой: ∑=25+35+50=110, ∑=40+30=70. ∑=110=∑=70 → ТЗ открытая. Вводим фиктивного 3-го потребителя с мощностью 40 (110-70=40) и нулевыми затратами на перевозки единиц грузов. 2. Нахождение первоначального допустимого решения. Распределим объемы перевозок минимальной оптимальности. Имеем 5 занятых клеток. Должно быть n+m-1=3+3-1=5. Первое допустимое решение: Х1= f()=2*25+35+2*5+5*5=50+35+10+25=120 3. Проверка допустимого решения на оптимальность. Обозначим потенциалы. Для каждой занятой клетки составим систему уравнений потенциалов: =0 v2=2 u3=3 v1=-1 u2=2 v3=-3 Для каждой свободной клетки найдем оценку: =u1+v1-=0-1-3<0 =u1+v3-=0-3-0<0 =u2+v2-=2+2-3=1 =u2+v3-=2-3-0<0 Имеем положительную оценку, поэтому решение не оптимально. 4. Переход к новому допустимому решению. Имеем клетку (2;2), т.к. =1>0. Организуем с ней цикл по клеткам (2;1), (3;1), (3;2). Расставим «+» и «-». min (35;5)=5. Это число в клетках с «+» прибавим, в клетках с «-» вычтем. Мощности потребителей Мощности поставщиков 1 2 3 ф 40 30 40 u1 1 25 3 2 u2 2 35 1 3 u3 3 50 2 5 5. Составим новое допустимое решение и повторим пункты 3, 4. Матрица поставок имеет вид: Х2= Целевая функция: f()=2*25+30+3*5+2*10=50+30+15+20=115. Для занятых клеток: =0 v2=2 u2=1 v1=0 u3=2 v3=-2 Для свободной клетки: =0+0-3<0 =0-2-0<0 =1-2-0<0 =2+2-5<0 Решение оптимально. Х*= min f()=115 Замечание: Если при получении оптимального решения получали оценки =0 (равные 0), то задача имеет столько дополнительных решений, сколько нулевых оценок. Их находят организовав цикл с клетками, в которых нулевые оценки. Целочисленное программирование. Метод Гомори. План. 1. Математическая модель задачи целочисленного программирования (ЗЦП). 2. Алгоритм метода Гомори. 3. Пример решения ЗЦП. 1. Математическая модель задачи целочисленного программирования (ЗЦП). Во многих экономических задачах переменные выражают физически неделимые объекты и потому могут принимать только натуральные значения. В таких задачах на переменные накладывают дополнительное требование их целочисленности. Математическая модель ЗЦП: Найти максимальное значение функции f()= при ограничениях: =, i= xj≥0, xjϵN, j= Наиболее распространенным методом решения ЗЦП является метод Гомори, основанный на симплексном методе. Напомним, что целой частью числа а называется число, не превышающее а. Обозначают [а]. Дробной частью числа а называется разность между числом и его целой частью. Обозначают {a}. Т.е. а=[а]+ {a}. Например: 3,7=3+0,7; 3,7=-4+0,3 2. Алгоритм метода Гомори. 1. Отбросив условие целочисленности решить исходную задачу симплексным методом. Если получилось целочисленное оптимальное решение, то задача решена. 2. Если в оптимальном решении не все переменные целочисленные, составить дополнительное ограничение (сечение Гомори). Сечение строится по базисной переменной, имеющей наибольшую дробную часть. Пусть в оптимальном решении базисная переменная, имеющая наибольшую дробную часть xt, xt+=, (1) где J – множество индексов свободных переменых. Разбить все коэффициенты и свободный член (1) на 2 слагаемых - целую и дробную часть. Неравенство ≥{} (2) называется сечением Гомори. Дополнительное ограничение имеет вид: - = {} (3) 3. Присоединяя равенство (3) к ранее решенной задаче, получить новую задачу линейного программирования, которую вновь решить симплексным методом. Если ее оптимальное решение окажется целочисленным, то решением исходной задачи. Если снова получится нецелочисленное решение, то построить новое сечение, и т.д. 3. Пример решения ЗЦП Найти f()=2x1+2x2 → max при ограничениях: Решение. 1. Решим задачу симплексным методом без учета целочисленности. Для этого приведем ее к каноническому виду: Построим симплексную таблицу. № табл. Базис Ci Cj План 2 2 Q x1 x2 x3 x4 1 2 3 4 5 6 7 8 9 x3 7 2 -1 1 3,5 x4 3 -1 2 1 ∞ ∆j -2 -2 1 x1 2 7/2 1 -1/2 ½ ∞ x4 13/2 3/2 1/2 1 13/3 ∆j 7 -3 1 2 x1 2 17/3 1 2/3 1/3 x2 2 13/3 1 1/3 2/3 ∆j 20 2 2 X*=(17/3;13/3;0;0) fmax=20 2. Решение нецелочисленное, поэтому строим сечение Гомори. Определим, у какой переменной в оптимальном решении наибольшая дробная часть: x1=17/3=5+2/3 x2=13/3=4+1/3 У переменной x1 дробная часть больше, поэтому возьмем первое уравнение, из последней симплексной таблицы: x1+x3+x4= Сечение имеет вид: x3+x4≥ Добавим дополнительную переменную x5, получим: x3+x4-x5=, где x5≥0 3. Присоединяя это дополнительное ограничение, к ограничениям последней симплексной таблицы, получим новую задачу: Решим ее симплексным методом с искусственным базисом (М – методом). f()=2x1+2x2-Мy1 → max № табл. Базис Ci Cj План 2 2 -M Q x1 x2 x3 x4 x5 y1 1 2 3 4 5 6 7 8 9 10 11 x1 2 17/3 1 2/3 1/3 17/2 x2 2 13/3 1 1/3 2/3 13 y1 -M 2/3 2/3 1/3 -1 1 1 ∆j 20-M 2-M 2-M M 1 x1 2 5 1 1 x2 2 4 1 x3 1 1 • ∆j 18 1 3 X*=(5;4;1;0;0) fmax=18 Теория игр План. 1. Основные понятия теории игр. 2. Решение матричной игры в чистых стратегиях. В экономике, управление часто приходится сталкиваться с ситуациями, в которых 2 или более сторон применяют разные цели, и действия каждой стороны зависят от противоположной. Такие ситуации называются конфликтными. Например, арбитражные споры, взаимоотношения поставщиков и потребителей, производство изделий и ограничение ресурсов и т.д. • Основные понятия теории игр Игра – это математическая модель конфликтной ситуации. Игроки – стороны, участвующие в конфликте. Выигрыш (проигрыш) – исход конфликта. Игры бывают парные и множественные. Игра с нулевой суммой – это такая игра, когда выигрыш одного игрока равен проигрышу другого. Личный ход игрока – это сознательный выбор игроком одного из действий, предусмотренных правилами. Случайный ход – случайный выбор игроком действия игры. Игры со случайными ходами называются азартными (кости, рулетка, карты). Чистая стратегия – это совокупность правил, определяющих выбор действий игрока при каждом личном ходе в зависимости от сложившейся ситуации. 1. Основные понятия теории игр Оптимальная стратегия или решение игры – это такая, которая при многократном повторении игры обеспечивает игроку максимальный средний выигрыш или минимальный средний проигрыш. Цель теории игр – определение оптимальной стратегии для каждого игрока. Если предварительно перед игрой участники приходят к соглашениям, то такие игры называют кооперативными. Например, принятие решений в Государственной Думе. Если один из игроков безразличен к результату игры, то такие игры называют играми с «природой». Под «природой» понимают совокупность внешних обстоятельств. Например, 1)производство продукции, в которой вторым игроком является потребитель; 2) вложения в ценные бумаги, где «природа» - прибыль (убыток) по каждому виду ценных бумаг. 2. Решение матричной игры в чистых стратегиях. В случае 2 игроков может быть составлена матрица исхода игры. Такая игра называется матричной, составленная матрица – платежной матрицей или матрицей игры. Пусть игрок А имеет m стратегий А1, А2, …, Аm, а игрок В – n стратегий В1, В2, …, Вn. А=(), i=, j= 1-го игрока (проигрыш 2-го), если 1-й игрок выбирает i-ю стратегию, а 2-й – j-ю стратегию. A1 a11 a12 … a1n A: A2 a21 a22 … a2n … … … … … Am am1 am2 … amn Пример. Игра «камень-ножницы-бумага». Составим платежную матрицу игры. К 0 1 -1 А: Н -1 0 1 Б 1 -1 0 Каждый игрок делает ходы осознанно, стремится к выигрышу. 1-й игрок А, выбирая стратегию, хочет получить наибольший выигрыш. А для 2-го игрока В это наибольший проигрыш. Поэтому он должен ответить таким ходом, чтобы получить ненаибольший проигрыш. Поэтому цель первого игрока А в игре получить наименьший выигрыш, а 2-го В – ненаибольший проигрыш. 1-й игрок среди всех стратегий выбирает наибольшее значение из минимальных выигрышей: A1 a11 a12 … a1n A: A2 a21 a22 … a2n … … … … … Am am1 am2 … amn a1=min (a11, …, a1n) a2=min (a21, …, a2n) … … am=min (am1, …, amn) • ai=min aij, где i=1, 2, …, m. • a=max ai – max min aij – нижняя цена игры, которая обеспечивает 1-му игроку А наибольший из наименьших выигрышей при любых стратегиях 2-го игрока. Такая стратегия называется максиминной. 2-й игрок В хочет получить ненаибольший проигрыш. Поэтому среди всех стратегий выбирает наименьшее значение из максимальных проигрышей: A1 a11 a12 … a1n A: A2 a21 a22 … a2n … … … … … Am am1 am2 … amn В1=max (a11, …, am1) В2=max (a12, …, am2) … Bn=max (a1n, …, amn) Bj=max , где j=1, 2, …, n. B=min Bj=min max – верхняя цена игры, которая обеспечивает 2-му игроку В наименьший из наибольших проигрышей. Такая стратегия называется минимаксной. Если , то такую игру называют игрой в чистых стратегиях. В противном случае – в смешанных стратегиях. Значения, в которых достигается это равенство , называют седловой точкой. Пример. Определить нижнюю и верхнюю цену игры для платежной матрицы. Сделать вывод о стратегии игры: в чистых или смешанных стратегиях. 1) К 0 1 -1 А: Н -1 0 1 Б 1 -1 0 α1=min (0;1;-1)=-1 α2=min (-1;0;1)=-1 α3=min (1;0;-1)=-1 α=max (-1;-1;-1)=-1 β1=max (0;-1;1)=1 β2=max (1;0;-1)=1 β3=max (-1;1;0)=1 β=min (1;1;1)=1 α=-1=β=1, значит игра в смешанных стратегиях. 1) α1=min (2;4;1)=1 α2=min (2;5;3)=2 α3=min (1;2;3)=1 α=max (1;2;1)=2 β1=max (2;2;1)=2 β2=max (4;5;2)=5 β3=max (1;3;3)=3 β=min (2;5;3)=2 α=β=2, значит игра в чистых стратегиях. Седловая точка (А2, В1) означает, что оптимальная стратегия игры, когда 1-й игрок А выбирает вторую А2 стратегию, которая обеспечивают ему выигрыш не меньше 2, а 2-му игроку В при выборе первой стратегии В1 – проигрыш не более 2. Если в платежной матрице имеются одинаковые строки или столбцы, то они называются дублирующими. Дублирующие строки (столбцы) при нахождении цены игры можно вычеркивать. Если значение i-й строки платежной матрицы превышают (или не меньше) все значения к-й строки, то i-я строка называется доминирующей. Если все значения j-го столбца платежной матрицы меньше (или не больше) всех значений р-го столбца, то j-й столбец называется доминирующим. Для большой платежной матрицы при нахождении цены игры можно оставлять доминирующие строки (столбцы). Пример. Найти цену игры: 7 6 5 4 2 5 4 3 2 3 5 6 6 3 5 2 3 3 2 4 3-я строка является доминирующей для 2-й и 4-й. Удалим их. 4-й столбец доминирующий для первых трех столбцов. Удалим их. Получили матрицу: α1=min (4;2)=2 α2=min (3;5)=3 α=max(2;3)=3 β1=max(4;3)=4 β2=max(2;5)=5 β=min(4;5)=4 α=β, значит игра в смешанных стратегиях. Чему равна цена игры? 3. Графический метод решения игры Используют для игр, в которых хотя бы 1 игрок имеет только 2 стратегии, т.е. в играх вида (m*2) или (2*n). Рассмотрим платежную матрицу 2*2: A= Пусть игра без седловой точки, т.е. α<β (α≤ν≤β) Пусть 1-й игрок выбирает 1-ю стратегию А1 с вероятностью х1, а стратегию А2 с вероятностью х2. Оптимальное решение для 1-го игрока Х*=(х1; х2) х1+х2=1 Пусть 2-й игрок выбирает 1-ю стратегию В1 с вероятность y1, а стратегию B2 с вероятностью y2. Оптимальное решение для 2-го игрока Y*=(y1; y2) y1+y2=1 Найдем цену игры ν. Для нахождения оптимального решения 1-го игрока составляем систему: Система имеет такой вид, т.к. 1-й игрок придерживается своей оптимальной стратегии и стремится к среднему выигрышу, равному цене игры ν. Аналогично для нахождения оптимального решения 2-го игрока, придерживающегося своей оптимальной стратегии, стремящегося к среднему проигрышу, равному цене игры ν, составляем систему: Решая системы, находят ν. Геометрическая интерпретация игры 2*2. Откладываем на оси абсцисс единичный отрезок А1, А2 и строим 2 вертикальные оси I-I и II-II. I II a12 B2 B1 a21 a11 B2 x A1 I II A2 Если 1-й игрок выберет 1-ю стратегию, то исходами игры будут значения а11 или а12, а если 2-ю, то а21 или а22. Прямая В1В1 – это исходы игры при выборе 2-м игроком стратегии В1. Прямая В2В2 – это исходы игры при выборе 2-м игроком стратегии В2. Ломаная В1КВ2 соответствует нижней цене игры: К=α=maxmin (). Аналогично находим верхнюю цену игры. Откладываем на оси абсцисс единичный отрезок В1В2 и строим 2 вертикальные оси I-I и II-II. I II a11 A1 A2 a22 a21 A1 x B1 I II B2 Если 2-й игрок выберет 1-ю стратегию, то исходами игры будут значения а11 или а21, а если 2-ю, то а12 или а22. Прямая А1А1 – это исходы игры при выборе 1-м игроком стратегии А1. Прямая А2А2 – это исходы игры при выборе 1-м игроком стратегии А2. Ломаная А1NA2 соответствует верхней цене игры: N=β=minmax (). Пример. Найти решение игры, заданной матрицей A= Уже определим, что α=3≤ν≤β=4. Составим систему для 1-го игрока: 4x1+3x2=2x1+5x2 x2=1-x1 4x1+3(1-x1)=2x1+5(1-x1) x1+3=-3x1+5 4x1=2x1=x2=0,5 ν=4*0,5+3*0,5=3,5 Построим график. B2 5 4 B1 ν=3,5 2 3 x A1 A2 Аналогично находят Y*=(y1; y2) и ν, составляя и решая систему для 2-го игрока. Убедитесь, что Y*=(0,75; 0,25). Найденное решение означает, что если 1-й игрок с вероятностью 0,5 будет применять 1-ю или 2-ю стратегии, то при достаточно большом числе игр с данной матрицей его выигрыш в среднем составит не менее 3,5. Если 2-й игрок с вероятностью 0,75 будет применять 1-ю стратегию и с 0,25 – 2-ю, его проигрыш в среднем составит не более 3,5.