Методы оптимальных решений. 8

Методы оптимальных решений

Задание 1. Решить задачу линейного программирования графическим методом.

Решение:

Решим неравенство графическим способом. Введем на плоскости прямоугольную систему координат , в которой точки с координатами находятся  в первом  квадранте этой координатной плоскости.

Решением каждого из неравенств будет соответствующая ему полуплоскость, а решением системы будет область, образованная пересечением всех найденных полуплоскостей.

Графическое решение нашей системы приведено на рисунке 1. Здесь прямая (1), соответствует уравнению . Построена она по двум точкам ( ) и    ( . Точка О(0,0), удовлетворяющая нашему первому неравенству , определяет в качестве решения полуплоскость, лежащую ниже прямой (1). Аналогично строим другие прямые и находим соответствующие неравенствам полуплоскости. Решением же системы является отрезок ВС – часть прямой

Найдем координаты точек B и C.

ВС образует область допустимых решений или допустимых планов нашей задачи, в которой мы и будем искать оптимальное решение L= . Для этого построим вектор , который укажет направление наибольшего возрастания целевой функции.

Линии, перпендикулярные этому вектору - , которые называются линиями уровня, задают одно из возможных значений целевой функции. На графике одно из этих уравнений, например , задает прямую, которой соответствует значение L=0. Максимальное же значение целевой функции будет соответствовать, такой линии уровня, которая будет получена путем параллельного переноса одной из линий уровня, проходящей через область допустимых планов, в пограничную область в направлении вектора   =(-2,5)=grad L. В нашем случае максимум целевой функции достигается в точке B.

 и 

Будем параллельно перемещать ее в направлении вектора (-2,5) до границы области допустимых планов в противоположном направлении. Минимум – в точке С(8;0).

Задание 2. Решить задачу линейного программирования симплексным методом.

Для изготовления различных видов продукции 1, 2, 3 и 4 предприятие использует три вида сырья А, В и С. Нормы расхода сырья на производство единицы продукции каждого вида, цена одного изделия, а также запас каждого вида ресурса известны и приведены в таблице 1.1.

Составить такой план производства продукции, при котором предприятие получит максимальную прибыль.

Таблица 1.1 – Нормативы затрат ресурсов на единицу продукции каждого вида

(общие для всех вариантов)

План решения задачи:

• выбрать из таблиц исходные данные своего варианта;
• обозначить неизвестные задачи;
• сформировать систему ограничений и целевую функцию задачи;
• привести систему ограничений к каноническому виду, обозначив и введя дополнительные переменные;
• вычертить симплексную таблицу и заполнить еѐ первоначальным опорным планом;
• пользуясь алгоритмом симплексного метода, найти оптимальное решение задачи;
• выписать оптимальное решение и провести его экономический анализ.

Решение

Обозначим через - количества продукции 1-го, 2-го, 3-го, 4-го видов.

Система ограничений по ресурсам:

Целевая функция:

Приведем систему ограничений к каноническому виду, обозначив и введя дополнительные переменные:

Целевая функция:

Составим симплексную таблицу и заполним еѐ первоначальным опорным планом

Решим симплекс-методом

В последней строке нет положительных элементов, решение оптимально.

Оптимальное решение: . Продукцию 1 вида нужно выпустить в объеме 330, 4-го –282,9. Продукцию 2-го и третьего вида не надо выпускать. Прибыль составляет 4243.

Задание 3. Решить открытую транспортную задачу методом потенциалов.

На оптовых складах А1, А2, А3, А4 имеются запасы некоторого продукта в известных количествах, который необходимо доставить в магазины В1, В2, В3, В4, В5. Известны также тарифы на перевозку единицы продукта из каждого склада в каждый магазин. Найти такой вариант прикрепления магазинов к складам, при котором сумма затрат на перевозку была бы минимальной.

Решение

Для отыскания первого опорного плана применим метод минимального элемента.

Составим  таблицу и решим методом потенциалов:

Общие затраты на перевозку всей продукции, для оптимального плана составляют:

Теория игр

1. Решить игру  с матрицей (тип 2хn). В ответе указать цену игры и вероятности применения стратегий, т.е. v, p, q.

Решение

Проверяем, имеет ли платежная матрица седловую точку. Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

 
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = -3, которая указывает на максимальную чистую стратегию A2. 
Верхняя цена игры b = min(bj) = 0.

Cедловая точка отсутствует, так как a ≠ b, тогда цена игры находится в пределах -3 ≤ y ≤ 0. Находим решение игры в смешанных стратегиях.

Доминирующихся и дублирующих стратегий ни у одного из игроков нет.

Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B3B3 и B4B4, для которых можно записать следующую систему уравнений:

 
Цена игры,

Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B1,B2,B5, которая дает явно больший проигрыш игроку B, и, следовательно,

Цена игры: ,

стратегии игроков:   

2. Решить игру  с матрицей (тип mх2). В ответе указать цену игры и вероятности применения стратегий, т.е. v, p, q.

Решение

Исследуем на наличие седловой точки

Седловой точки нет, нет и решения в чистых стратегиях. 

Решаем в смешанных стратегиях

Запишем систему уравнений. 
Для игрока I

Для игрока II

 
Решаем симплекс-методом

            Цена игры равна  

Для игрока A оптимальная стратегия, учитывая, что имеем:

Согласно двойственной задаче для игрока Б оптимальная стратегия, учитывая,

что имеем:

3. Найти точки равновесия в биматричной игре (A – матрица выигрышей игрока 1, B – матрица выигрышей игрока 2)

Решение

В каждом столбце матрицы A найдем максимальный элемент. Эти элементы подчеркнуты в матрице A.

Затем в каждой строке матрицы B выберем наибольший элемент. Эти элементы подчеркнуты в матрице B. Их положение будет определять приемлемые ситуации 2-го игрока, когда первый игрок выбрал стратегию i соответственно. 
Платежная матрица игрока А:

 
Платежная матрица игрока B:

Если биматричная игра не имеет равновесных ситуаций в чистых стратегиях, то она неразрешима в чистых стратегиях. И тогда можно искать решение в смешанных стратегиях.

Итак, чтобы в биматричной игре:  А=(a), В = (b) пара (p,q);

определяемая равновесную ситуацию, необходимо и достаточно одновременное выполнение следующих неравенств:

(p–1)(Cq-α) ≥ 0, p(Cq-α) ≥ 0; 0 ≤ p ≤ 1

(q-1)(Dp-β) ≥ 0, q(Dp-β) ≥ 0; 0 ≤ q ≤ 1

C = a11 - a12 - a21 + a22

α = a22- a12

D = b11-b12-b21+b22

β = b22-b21 
C = 9 - 6 - 4 + 10 = 9

α = 10 - 6 = 4

D = 0 - 4 - 11 + 7 = -8

β = 7 - 11 = -4

(p–1)(9q-4) ≥ 0

p(9q-4) ≥ 0

(q-1)(-8p+4) ≥ 0

q(-8p+4) ≥ 0

получаем, что:

1) p=1,q ≥4/9 
p=0, q ≤ 4/9 
0 ≤ p ≤ 1, q=4/9 
2) q=1,p ≥ 1/2 
q=0, p ≤ 1/2 
0 ≤ q ≤ 1, p=1/2 
Цена игры 
Ha(1/2;4/9) = 71/3 
Hb(1/2;4/9) = 51/2 
P* = (1/2;1/2); Q* = (4/9;5/9). 
Выигрыш игроков в равновесной ситуации: 
f(P*,Q*) = (71/3;51/2).

4. Имеется три предприятия (I, II, III); которые выпускают продукцию №1, продукцию №2 и продукцию №3.Следующая таблица представляет общие выпуски продукции по каждому предприятию. Продукция продается комплектами (1ед. №1, 1ед. №2 и 1ед. №3). Спрос неограничен. Комплект стоит 1 тыс. руб. Требуется решить вопрос о целесообразности объединения предприятий, найти максимальный возможный доход объединения, справедливый дележ – вектор Шепли. В левом верхнем углу указан номер варианта.

5. Располагая информацией о количестве голосов, которыми располагают партии, и о размере выигрывающей коалиции, найти веса партий при голосовании.

    1              2                 3               4                       Размер выигрывающей коалиции                          

36,9%      28,2%       17,4%        17,4%                                           58%

Решение

Данная ситуация может рассматриваться как простая игра четырёх игроков, в которой выигрывающими являются следующие коалиции:

{1; 2} {1; 2; 3}, {1; 2; 4},  {1; 3; 4}, {2; 3; 4} {1; 2; 3; 4}.

Определяем все выигрывающие коалиции, но не выигрывающие без 3-го игрока:

{1; 3; 4}, {2; 3; 4}.

В коалиции  имеется  t = 3 игрока, поэтому

.

Аналогично получаем, что .

При нахождении j2 необходимо учитывать, что имеется 3 коалиции, которые выигрывают, а коалиция без 2-й партии не выигрывает. Определяем все выигрывающие коалиции, но не выигрывающие без 2-го игрока: {1; 2} {1; 2; 3}, {1; 2; 4},  {2; 3; 4} .

.

И на первую партию остается

В результате получаем, что вектор Шепли равен .

Веса партий (72%; 12%; 8%;8%)

6. Найти гарантированные выигрыши игроков без кооперирования, Парето- оптимальное множество, переговорное множество, точку Нэша для задания 3.

Решение

Равновесия по Нэшу в чистых стратегиях не существует. Будем искать решение в смешанных стратегиях x={x1, x2} и y={y1, y2} соответственно, где 0≤xi≤1, 0≤yj≤1, x1+x2=1, y1+y2=1.

Легко проверить, что в этой игре нет доминирующих стратегий, нет также равновесных исходов, так как от любого исхода игроки могут отклониться, действуя в своих интересах.

Имеем систему:

Подставляя, имеем

Точки равновесия нет,