Методы оптимальных решений. 5
Задача 1. Найти максимум целевой функции L =4x+3y при следующих ограничениях:
Решить задачу при дополнительном условии (ДУ):
ДУ: Найти
минимум целевой функции L=2x-
Решение:
1. Найдем множество допустимых планов.
Введем на плоскости
прямоугольную систему
Графическое решение
Исходя из этого, рассмотрим каждое, из приведенной выше системы, неравенство. Решением каждого из них будет соответствующая ему полуплоскость, а решением системы будет область, образованная пересечением всех найденных полуплоскостей. Графическое решение нашей системы приведено на рисунке 1.
В нашем случае множеством ограничений выступает набор из 5 неравенств. На рисунке им соответствуют полуплоскости, образованные прямыми АE, DE, BC, OX и OY (координатные оси соответствуют условиям x≥0 и y≥0). Пересечение всех полуплоскостей образует пятиугольник ABCDE. Чтобы в этом убедиться, возьмём какую-нибудь точку внутри него, например (2,2). Подставляя координаты х=2 и у=2 в ограничения, видим, что выполняются все. Любая точка пятиугольника будет решением системы ограничительных неравенств, поскольку лежит в тех же полуплоскостях, что и (2,2). Таким образом, множество допустимых планов замкнуто и максимум линейной формы достигается на одной из его граничных точек.
Рисунок 1.
2. Найдем оптимальное решение L= max.
Построим вектор = grad L(x,y) , который укажет направление наибольшего возрастания целевой функции. Прямая, перпендикулярная вектору (в нашем случае его координаты (4,3)), соответствует L=const. Если перемещать такую прямую в направлении вектора , значения L будут возрастать. Максимальное значение L, т.е. оптимальное решение, достигается в последней точке ее пересечения с множеством допустимых планов. На рис.2 показана прямая, соответствующая L=0, она проходит через начало координат.
Рисунок 2.
Решение задачи сводится к нахождению точки области ABCDE, наиболее удаленной от прямой L=0. Из рисунка видно, что это одна из точек A, D, E.
Угол наклона прямой ах+bу=с к оси ОХ определяется отношением a/b. Для прямой L=const это отношение составляет 4/3, что больше отношения 8/7 и меньше отношения 9/6 для прямых AE и ED. Это значит, что ED проходит круче PQ (проходящая через точку E L=const), а PQ – круче AE. Точки A и D лежат ниже прямой PQ, значит максимальное значение L и оптимальное решение достигаются в точке E. Найдем ее координаты .
Точка Е лежит на пересечении прямых 8х+7у=56 и 9х+6у=54 (см. рис. 1). Координаты точки Е должны быть решениями уравнений обеих прямых, т.е. надо решить систему
Вычтем второе уравнение из первого, получим у-х=2, у=х+2
Подставим у=х+2 в первое уравнение, получим 8х+7х+14=56, 15х=42, х=42/15, у=72/15
Итак, максимум L достигается в точке (42/15,72/15), значение L в этой точке составит (42/15)*4+(72/15)*3=384/15
3. Найдем минимум функции L=2x-3y при тех же условиях.
Градиент имеет координаты (2, -3). На рис. 3 показана прямая, соответствующая значению L=16. Будем мысленно перемещать ее в направлении, противоположном , т.е. влево и вверх по чертежу. Достигнув точки D, она пройдет над областью допустимых планов и покинет ее в точке A. При этом значение L будет всё время уменьшаться. Значит, минимальное значение L на области допустимых планов достигается в точке А с координатами (0,8). L(0,8) = 2*0 - 3*8= -24.
Рисунок 3
Ответ: Целевая функция L=4x+3y на области допустимых планов достигает максимального значения 384/15 при х=42/15 и у=72/15. Функция L = 2х - 3у при тех же ограничениях достигает минимума -24 при х=0, у=8.
3.2. Предприятие производит
Решение.
1. Приведение условий задачи к канонической форме.
Составим сводную таблицу
Таблица 1.
Сырье, т |
Продукция |
Запасы, т | |
А |
В | ||
1 |
3 |
4 |
120 |
2 |
2 |
2 |
60 |
3 |
2 |
3 |
≥30 |
Прибыль, млн.р. |
2 |
3 |
|
Пусть х1 - количество изделий А, х2 – количество изделий В, которое произведет предприятие. При этом оно израсходует (3х1+4х2) т сырья первого вида, (2х1+2х2) т сырья второго вида, (2х1+3х2) т сырья третьего вида и получит прибыль (2х1+3х2) млн.р.
Итак, следует решить задачу линейного программирования:
(1)
Сразу обратим внимание на то, что при положительных х1, х2 второе неравенство сильнее первого. Действительно, 4х1+4х2≤120, так что 3х1+4х2≤120 верно при всяком неотрицательном х1. Следовательно, первое ограничение ничего не добавляет в систему и может быть исключено. Это существенно упростит задачу.
Чтобы преобразовать неравенства в равенства, введем вспомогательные переменные х3 и х4. Система ограничений при этом примет вид:
(2)
Экономический смысл переменной х3 – остаток сырья второго вида, х4 – использованное сверх минимальной установленной нормы сырье третьего вида.
Следует найти такие допустимые х1… х4, при которых целевая функция L=2х1+3х2+0х3+0х4 достигает максимума. Для решения задачи применим симплекс-метод.
2. Нахождение начального опорного плана.
Система ограничений (2) не является приведенной в смысле преобразования Гаусса, поскольку х4 входит во второе уравнение со знаком минус. Мы можем, конечно, умножить это уравнение на -1, получив таким образом базис {х3 х4} и опорный план (0,0,60,-30), но последний содержит отрицательное значение, что противоречит условиям поставленной задачи. Поэтому следует найти какой-нибудь другой базис, который бы соответствовал опорному плану с положительными координатами. Нам подойдет, например, базис {х2 х3}.
Приведем систему (2) к этому базису. Для этого, во-первых, избавимся от х2 в первом уравнении. Для этого умножим второе уравнение на 2/3 и вычтем из первого. Затем разделим второе уравнение на 3, так чтобы х2 входил в него с коэффициентом 1. В итоге получим (поменяв местами уравнения)
(3)
Присвоив свободным переменным х1 и х4 значение 0, получим х2=10 и х2=40
Вектор х0 = (0, 10, 40, 0) и будет начальным опорным планом нашей задачи.
3. Итерации симплекс-метода
и отыскание оптимального
Заполним симплекс-таблицу 2 в следующем порядке:
Сначала разместим по столбцам х1… х4, b и строкам х2 х3 расширенную матрицу системы (3).
х1 |
х2 |
х3 |
х4 |
b |
bi/αik | |
|
х2 |
2/3 |
1 |
0 |
-1/3 |
10 |
|
х3 |
2/3 |
0 |
1 |
2/3 |
40 |
|
Δ |
Далее, заполним нижнюю строку оценками опорного плана. Рассчитаем их по формулам ([1], с.169):
(4)
где с=(2,3,0,0) – коэффициенты целевой функции, σ= {2,3} – список базисных индексов, т.е. сσ = (3,0). j=1…5
Δ0=2*0+3*10+0*40+0*0=30
Δ1=3*2/3+0*2/3-2= 0
Δ2=3*1+0*0-3=0
Δ3=3*0+0*1-0=0
Δ4=3*(-1/3)+0*2/3-0=-1
Заносим Δj в j-е столбцы, Δ0 в столбец b:
Таблица 2
х1 |
х2 |
х3 |
х4 |
b |
bi/αik | |
|
х2 |
2/3 |
1 |
0 |
-1/3 |
10 |
|
х3 |
2/3 |
0 |
1 |
2/3 |
40 |
|
Δ |
0 |
0 |
0 |
-1 |
30 |
Среди оценок есть отрицательные, значит выбранный нами опорный план не является оптимальным. Введем в базис вектор х4 – ему соответствует минимальная оценка -1. В старом базисе он имел координаты (-1/3, 2/3), из которых положительна только одна – по вектору х3 – его следует вывести из базиса.
Пересчитаем таблицу 2 так, чтобы столбец х4 принял вид (0,1,0). Для этого строку х3 следует разделить пополам и прибавить к строке х2 , а также умножить на 3/2 и прибавить к индексной строке. Результаты преобразований занесем в таблицу 3.
Таблица 3
х1 |
х2 |
х3 |
х4 |
b |
bi/αik | |
|
х2 |
1 |
1 |
1/2 |
0 |
30 |
|
х3 |
1 |
0 |
3/2 |
1 |
60 |
|
Δ |
1 |
0 |
3/2 |
0 |
90 |
Подставляя х1 = х3 =0, получим новый опорный план: х1 = (0, 30, 0, 60). В индексной строке больше нет отрицательных значений, значит полученный опорный план и будет оптимальным. Значение целевой функции на этом плане 2*0+3*30 = 90.
Ответ: Предприятию следует производить только изделия В в количестве 30 шт. Прибыль составит 90 млн. р.
Задача 3. Из пунктов отправки a1 … a3 требуется перевезти груз в пункты назначения b1 … b3 . Количество груза и цены на перевозку приведены в таблице 1. Найти минимально затратный план перевозок.
Таблица 1
По\Пн |
=2 |
||
3 |
2 |
3 | |
1 |
1 |
1 | |
=2 |
2 |
2 |
2 |
Решение.
1. Найдем начальный опорный план.
В опорном плане должно быть n+m-1, базисных переменных, а значит в таблице столько же занятых клеток, где n – количество По, а m – Пн. В нашем случае n+m-1=3+3-1=5, значит столько заполненных клеток должно быть в нашей транспортной таблице.
При построении опорного
плана методом наименьшей
В нашей задаче минимальную стоимость 1 мы имеем сразу в трех клетках. Начнем с клетки ( ).За счет запаса По =3 можно удовлетворить всю заявку Пн =2. Поэтому записываем 2 в клетку ( ). При этом заявка Пн - теперь полностью удовлетворена. Но надо запомнить, что запас По- уменьшился на 2 единицы и теперь составляет 1 единицу. Такую же по величине стоимость равную =1 мы имеем в клетке ( ). Но поскольку запас По- =1, что меньше заявки Пн- =5, в эту клетку мы можем записать только 1 единицу товара. При этом запас По- =1 полностью исчерпан, но помним, в Пн - необходимо доставить еще 4 единицы товара, используя возможности оставшихся По. Так как в клетке ( ) имеющей такую же по величине стоимость =1, уже стоит прочерк, то далее будет заполнена клетка ( ) с наименьшей из оставшихся стоимостью =2, куда мы запишем 4 единицы товара, полностью удовлетворяющих заявку . Рассуждая аналогично заполняем остальные клетки. В результате получим следующую транспортную таблицу 2 соответствующую первому опорному плану:
Таблица 2
По\Пн |
=2 |
||
- |
4 |
2 | |
2 |
1 |
- | |
=2 |
- |
- |
2 |
Нетрудно убедиться, что сумма перевозок в каждой строке равна запасу соответствующего По, а в каждом столбце – заявке соответствующего Пн.
Сам первый опорный имеет вид- =(0,4,2,2,1,0,0,0,2).
А целевая функция задачи на этом плане равна
=2х4+3х2+1х2+1х1+2х2=21.
2. Проверим, является ли найденный опорный план оптимальным.
Сопоставим каждому По – число и каждому Пн – число так, чтобы для любой базисной клетки выполнялось условие: . Числа и называются потенциалами. Оценки - , вычисляются для пустых клеток по формуле . Так как в нашем опорном плане m+n-1=3+3-1=5 базисных переменных, то для нахождения потенциалов нужно решить систему из 5 уравнений с 6-ю неизвестными. Поскольку число неизвестных на 1 больше числа уравнений значение одного потенциала можно выбрать произвольно. В нашей задаче система уравнений для нахождения потенциалов имеет вид:
Полагаем =0 и сразу получаем значения остальных потенциалов: =-1, =3, =-1, =2, =2.
Теперь можно вычислить оценки:
, , аналогично =1, =1. Данные оценки занесены в таблицу в свободные клетки слева от стоимостей перевозок и выделены серым цветом.
Таблица 3
.По\Пн |
=2 |
|||
|
|
1 3 - |
2 4 |
3 2 |
0 |
1 2 |
1 1 |
-1 1 - |
-1 | |
=2 |
1 2 - |
1 2 - |
2 2 |
-1 |
|
2 |
2 |
3 |
Среди оценок есть отрицательные, значит выбранный нами опорный план не является оптимальным.
3. Найдем оптимальный опорный план.
Для перехода к новому опорному плану свободная переменная с отрицательной оценкой вводится в базис, а одна из базисных переменных переводится в свободные. Для этого построим цикл с началом (и концом) в клетке (2,3) с отрицательной оценкой =-1 и вершинами в занятых клетках. Ребра цикла могут проходить и через свободные, и через занятые клетки, но повороты на 90 градусов должны происходить только в занятых клетках. В нашем примере получается следующий цикл:
Таблица 4
.По\Пн |
=2 |
|||
|
|
1 3 - |
+w 2 |
-w 3 |
0 |
1 2 |
-w 1 |
-1 1 +w |
-1 | |
=2 |
1 2 - |
1 2 - |
2 2 |
-1 |
|
2 |
2 |
3 |
Для вывода из базиса выбирается клетка, помеченная знаком “ ” и имеющая наименьшее значение. Это условие гарантирует неотрицательность нового опорного плана. Если наименьшее значение находится в нескольких клетках, то выбирается любая из них. В любом случае значение целевой функции уменьшается на величину .
В нашей задаче w=min{х13 =2, х22 =1}=1. Тогда новые значения переменных будут следующими: х23 =1 (и пустая клетка становится занятой), х22 =0 (занятая клетка становится пустой), х12 =5, х13 =1. Значение целевой функции на новом опорном плане будет равно =21 - 1х1=20. Далее переходим к следующей таблице и вычисляем новые значения потенциалов и новые оценки, которые таким же образом заносим в таблицу.
Новые потенциалы:
u1=0; u2=-2; u3=-1; v1=3; v2=2; v3=3.
Таблица 5
.По\Пн |
=2 |
|||
|
|
0 3 - |
2 5 |
3 1 |
0 |
1 2 |
1 1 - |
1 1 |
-2 | |
=2 |
0 2 - |
1 2 - |
2 2 |
-1 |
|
3 |
2 |
3 |
Отрицательных оценок больше нет, следовательно план х2 является оптимальным. Вот он:
х2 = (0, 5, 1, 2, 0, 1, 0, 0, 2). Наличие нулевых оценок в клетках с11 и с31 как бы намекает нам, что возможны варианты логистических решений с той же стоимостью перевозки.
Ответ: из пункта a1 следует перевезти 5 единиц груза в пункт b2 и 1 единицу груза в пункт b3 . Из пункта а2 следует перевезти 2 единицы груза в пункт b1 и 1 единицу груза в пункт b3. Из пункта а3 следует перевезти 2 единицы груза в пункт b3 .
Стоимость перевозки составит 20 условных единиц.
Задача 4. Игроки А и В имеют по 4 стратегии игры каждый, причем во время игры один не знает, какую стратегию выбрал другой. При выборе игроком А i-й стратегии, а игроком В – j-й, игрок В выплачивает игроку А сумму, равную значению элемента аij платежной матрицы
(1)
Найти цену игры и оптимальную стратегию.
Решение.
Стратегии игрока А – строки платежной матрицы, стратегии игрока В – ее столбцы. Какой бы стратегии ни придерживался игрок В, выигрыш игрока А при выборе им стратегии 1 не будет меньше выигрыша при выборе им стратегии 4, т.е. первая стратегия доминирует четвертую, так что игрок А никогда не выберет последнюю. Аналогично для игрока В стратегия 1 при любом раскладе предпочтительнее стратегий 3 и 4. Следовательно, мы можем упростить платежную матрицу, вычеркнув из нее четвертую строку и третий и четвертый столбец.
(2)
Договоримся считать, что теперь у игрока А имеется первая, вторая и третья стратегии, а у игрока В – первая и вторая (в оговоренном ранее порядке).
Справа в каждой строке выпишем гарантированный выигрыш игрока А, а внизу под каждым столбцом – максимальный проигрыш игрока В для каждой из стратегий:
5 3 | 3
6 -2 | -2
-1 4 | -1
________
6 4
Для игрока А наилучшей является первая стратегия, по которой он гарантированно выигрывает 3 ед. a0 =3 – нижняя цена игры. А для игрока В наилучшей является вторая стратегия, так как он в худшем случае платит 4 ед. b0 = 4 - верхняя цена игры. Так как нижняя и верхняя цены игры не совпадают, то в чистых стратегиях задача не имеет решения.
Найдём решение задачи в смешанных стратегиях. Для этого будем считать, что игрок В с вероятностью р использует первую стратегию и с вероятностью 1 – р – вторую.
р 1-р
5 3
6 -2
-1 4
Найдём средний выигрыш игрока А.
Если игрок А выбирает первую стратегию, то он получает математическое ожидание выигрыша, равное
u1=5p+3(1 – p)=2p+3
Если игрок А выбирает вторую стратегию, то он получает математическое ожидание выигрыша, равное
u2= 6p - 2(1 – p)= 8p -2
Если игрок А выбирает третью стратегию, то он получает математическое ожидание выигрыша, равное
u3= -p+4(1 – p)=-5p+4
Так как неизвестной величиной является только одна – вероятность р, то выигрыш игрока А удобно изобразить на графике в переменных (u,p).
Если бы игрок А знал значение р, он выбрал бы ту стратегию, для которой значение u(р) было бы наибольшим, т. е. выигрыш игрока А всегда является ординатой верхней огибающей всех u(p) (выделена на рисунке).
Игроку В выгодно зафиксировать такое р, при котором выигрыш игрока А, а значит и проигрыш игрока В, минимален. Из графика видно, что минимум верхней огибающей всех u(p) достигается в точке М. Найдем ее координаты.
Так как
то
2р+3=-5р+4
7р=1
р=1/7
Найдём цену игры.
μ=2р+3=23/7
Найдём стратегии игрока А.
Точка М – точка оптимальной стратегии определяется как первая и третья стратегии игрока А, поэтому вторая и четвёртая стратегии игрока А не используются.
Пусть игрок А с вероятностью q использует стратегию 1 и с вероятностью (1 – q) – стратегию 3. Но цена игры известна, поэтому можно написать уравнение на q в виде:
5q+3(1-q)=23/7
2q=2/7
q=1/7
Ответ: Оптимальная стратегия
