<<
>>

4.2.2 Решение задачи симплекс-методом

Рассмотрим числовой пример.

Пусть имеем игру с платежной матрицей:

Проверим, имеет ли наша матричная игра седловую точку? Для этого используем принцип максимина.

Выигрыш игрока А:a = = 2 он достигается в первой строке.

Выигрыш игрока В:в = = 3 он достигается в четвертом столбце.

Как видим, выигрыши игроков не совпадают, значит у матрицы нет седловой точки. Значит, нужно искать смешанные стратегии.

В данном конкретном случае в множестве ограничений будет четыре неравенства (т.к. в условии задачи четыре столбца). Пересчитывать симплекс- таблицы с четырьмя строками не очень сильно хочется, поэтому удобнее решить двойственную задачу (для коэффициентов вектора смешанной стратегии второго игрока), в которой будет всего две строки (т.к. в условии задачи две строки):

найти вектор двойственных переменных Y = {y1, y2, … yn}, такой что:

целевая функция g = max

при множестве ограничений:АY ≤ Е

Для нашего примера задача линейного программирования будет такой:

найти вектор Y = {y1, y2, y3, y4}, такой что:

целевая функция g = max

при множестве ограничений:

Далее нужно вспомнить методику применения симплекс-метода и использовать её для нашей задачи.

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

Для этого нужно сходить в библиотеку, найти специальную литературу и умело ей воспользоваться. Осмелимся заметить, что и этого половина студентов сделать поленится и благополучно завалит данную тему J . #

Поэтому для всеобщего блага приведем здесь методику применения симплекс-метода (пройденного и успешно сданного в математическом программировании) для нашей конкретной задачи.

1 этап – приведение задачи линейного программирования к каноническому виду.

Неравенства во множестве ограничений нужно превратить в равенства с помощью добавления искусственных переменных. Для того чтобы неравенства превратить в равенства, надо в каждое неравенство добавить (или отнять – в зависимости от знака неравенства) искусственную переменную:

Целевая функция при этом будет выглядеть так:g = y1 + y2 + y3 + y4 + 0y5 + 0y6

2 этап – определение начального опорного плана.

В полученном случае начальный опорный план будут составлять искусственные переменные, входящие в ограничения с коэффициентами +1 :{ y5 ; y6 }. Новых искусственных переменных для данной задачи вводить не требуется.

3 этап – заполнение исходной симплекс-таблицы.

Исходная симплекс-таблица для нашей двойственной задачи будет иметь вид:

В столбец "текущий базис" ставим переменные, начального опорного плана : { y5 ; y6 }.

В столбец "сi" ставим их коэффициенты в целевой функции.

В столбец "А0" ставим вектор ограничений Е : а10 = 1 ;а20 = 1 .

В самую верхнюю строку таблицы ставим коэффициенты cj при соответствующих переменных в целевой функции:c1 = 1 ; c2 = 1 ; c3 = 1 ; c4 = 1 ; c5 = 0 ; c6 = 0 .

В столбцы "А1", ...., "А6" ставим соответствующие коэффициенты матрицы ограничений А.

Вычисляем оценки по формулам

D0 = ; .Dj =  cj

и ставим их в самую нижнюю строку симплекс-таблицы (строку оценок) :

D0 = = 0 * 1 + 0 * 1 = 0D1 =  c1 = 0 * 4 + 0 * 3  1 =  1

D2 =  c2 = 0 * 3 + 0 * 7  1 =  1D3 =  c3 = 0 * 8 + 0 * 1  1 =  1

D4 =  c4 = 0 * 2 + 0 * 3  1 =  1D5 =  c5 = 0 * 1 + 0 * 0  0 = 0

D6 =  c6 = 0 * 0 + 0 * 1  0 = 0

4 этап – пересчет симплекс-таблицы.

1. Если j ? 0 для всех j = 1, 2, .... , n , то данный план (в столбце "текущий базис") – оптимален. В нашем случае это условие не выполняется, значит, текущий базис можно улучшить.

2. Если имеются k < 0 и в столбце Аk все элементы aik 0 , то целевая функция не ограничена сверху на допустимом множестве и данная задача не имеет смысла. В нашем случае видим, что целевая функция сверху ограничена.

3. Если имеются j < 0 и в столбцах Аj , соответствующих этим оценкам, существует хотя бы один элемент aik > 0, то возможен переход к новому лучшему плану, связанному с большим значением целевой функции. У нас так и есть.

4. Переменная хk, которую необходимо ввести в базис, для улучшения плана соответствует наименьшей отрицательной оценке j. Столбец Ak, содержащий эту оценку называется ведущим. В нашем случае все оценки одинаковы. Поэтому в качестве ведущего столбца выберем любую оценку, например, третью: k = 3.

5. Ищем min{ ai0 / ai1 } = min{ 1/8 ; 1/1 } = 1/8– этот минимум достигается при i = 1. Значит, r = 1первая строка – ведущая. (на рисунке помечена стрелкой)

Ведущий элементark = a13 = 8 (на рисунке выделен)

6. Заполняем новую симплекс-таблицу.

В столбец "текущий базис" вместо переменной у5 ставим переменную у3 .

В столбец "сi" ставим коэффициент переменной у3 в целевой функции.

Самая верхняя строка таблицы всегда остаётся неизменной.

Пересчитываем ведущую строку по формуле :

После этого пересчитываем остальные строки по формуле

:

вторая строка (i = 2)

Пересчитываем и заполняем строку оценок:

D0 = = 1 * + 0 * = D1 =  c1 = 1 * + 0 *  1 = 

D2 =  c2 = 1 * + 0 *  1 =  D3 =  c3 = 1 * 1 + 0 * 0  1 = 0

D4 =  c4 = 1 * + 0 *  1 = 

D5 =  c5 = 1 * + 0 *  0 = D6 =  c6 = 1 * 0 + 0 * 1  0 = 0

После этого повторяем 4 этап до тех пор, пока не будет выполнен п.1 (все j ? 0).

В нашем случае имеются j < 0 и наименьшая среди них 4 . Значит ведущим столбцом на данном шаге будет A4 (пометим его стрелкой).

Ищем min{ ai0 / ai4 } = min{:; :} = min{; } = – этот минимум достигается при i = 2. Значит, r = 2вторая строка – ведущая (на рисунке помечена стрелкой).

Таким образом, в новый текущий базис вместо переменной у6 надо ввести переменную у4 .

Пересчитываем все элементы новой симплекс-таблицы.

Пересчитываем ведущую строку (вторую):

= : = = = : = =

= : = = = 0 : = 0

= : = 1 = – : = – = 1 : =

Приведенные выше и ниже вычисления представлены в весьма подробном виде.

Это сделано из тех соображений, что как опять таки показывает практика, даже не смотря на достаточно хорошее понимание и усвоение теоретического материала, ошибки зачастую возникают именно при выполнении элементарных арифметических операций. Не следует думать, что средняя школа осталась позади, и вы всё можете посчитать в уме. Поэтому всем студентам мы советуем не лениться и подробно расписывать все арифметические действия (особенно с дробями).#

Пересчитываем оставшуюся строку (первую):

= = = =

= = = =

= = = – = –

= 1 – 0  = 1 = = 0

= = + = =

= 0 – = –

Пересчитываем и заполняем строку оценок:

D0 = = 1 * + 1 * = =

D1 =  c1 = 1 * + 1 *  1 = =

D2 =  c2 = 1 * + 1 *  1 = = =

D3 =  c3 = 1 * 1 + 1 * 0  1 = 0

D4 =  c4 = 1 * 0 + 1 * 1  1 = 0

D5 =  c5 = 1 * + 1 *  0 = =

D6 = – c6 = 1  + 1  – 0 =

Повторяем 4-й этап.

При проверке п. 1 видим, что все j ? 0 . Следовательно, данный план {у3, у4} (в столбце "текущий базис") – оптимален. Больше пересчитывать симплекс-таблицу не нужно.

Решение задачи линейного программирования полностью содержится в последней симплекс-таблице.

Значения переменных находятся в столбце А0 возле соответствующих переменных. В нашем случае, мы видим, что у3 = , у4 = . Переменные у1 и у2 не входят в базис, поэтому их значения будут равны нулю. Таким образом, вектор переменных будет выглядеть так: Y = .

Значение целевой функции – это значение оценки 0 . В нашем случае g = 0 = .

Значения двойственных переменных находятся в строке оценок возле искусственных переменных. В нашем случае это 5 и 6 , то есть х1 = , х2 = . Таким образом, вектор двойственных переменных будет выглядеть так:Х = .

Итак, мы получили решение прямой задачи (которая у нас была двойственной): Y =

и двойственной задачи к данной (которая у нас была прямой):

Х =

Значения целевых функций при этом будут совпадать:f = g = .

Найдем цену игры:n = =

Далее найдем коэффициенты смешанной стратегии

для первого игрока по формуле рi = :

Р = = ,

для второго игрока по формуле qi = :

Q = = .

Особо "продвинутые" студенты при нахождении решения задачи линейного программирования, чтобы не считать симплекс-метод вручную академическим способом, могут воспользоваться средствами MS Excel. Это гораздо быстрее и удобнее.#

Ответ: смешанная стратегия для первого игрока Р = ,

смешанная стратегия для второго игрока Q = ,

цена игры n = .

<< | >>
Источник: Ю.О. Матузко. Теория принятия решений.. 2009

Еще по теме 4.2.2 Решение задачи симплекс-методом:

  1. §1.2. Решение задачи о перекрестном токе с неравномерными входными температурами.
  2. 1.3.3. Использование методов анализа сигналов для решения задачи поиска «цели»
  3. 2.3 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
  4. 7.3. Графическое решение задачи линейного программирования
  5. 7.5. Симплекс-методОбщая идея симплекс-метода
  6. 7.6. Методы нахождения опорного решения задачи линейного программирования
  7. 7.7. Экономическая интерпретация решения задачи линейного программирования
  8. 12.2. Аналитический метод решения задач параметрического программирования
  9. § 65. Симплекс-метод решения задач линейного программирования, М-метод
  10. Решение задачи Коши методом разделения переменных. (Метод Фурье.)
  11. Решение задачи Коши методом Даламбера. ( Жан Лерон Д’Ламбер (1717 – 1783) – французский математик)
  12. §1. Комбинаторные задачи и методы их решения