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

y₄ y₅ у₆ y₇ y₁ y₂ y₃

БП СП

Учитывая это соответствие, из индексной строки последней итерации выписываем оптимальный план у^*:

– двойственные оценки.

В соответствии с основной теоремой двойственности имеем max z (х^*) = min f (у^*) = 84000.

Замечание. Если при решении задачи у нас имеются < 0, то переменную, соответствующую этому свободному члену, следует исключить из базиса. Для выбора переменной, включаемой в ба- _{зис, просматриваем i-строку: если в ней не содержится , то исходная задача не имеет решения. Если же есть , то для столбцов, содержащих эти , находим 1 = min}

Затем находим  = max при решении задачи на min и  = min при решении задачи на max. Эту переменную и вводим в базис. В процессе вычисления по алгоритму двойственного симплексного метода ус­ловие оптимальности (_j  0 или _j  0) можно не учитывать, пока не бу­дут исключены все b_i < 0, затем оптимальный план находим обычным симплексным методом.

Пример 16. Найти а) min Z= -2х₁+х₂ +5х₃ при ограничениях

б) решение двойственной ей задачи.

Решение:

а)

 – система имеет пред- почтительный вид.

Составим симплексную табл. 24, выбрав за базисные переменные х₄ и х₅. Так как х₅= – 5<0, то просматриваем коэффициенты второй строки. Среди них два отрицательных коэффициента, стоящие в столбцах х₁ и х₃. Имеем:

Т аблица 24

Исходная задача решается на отыскание минимального значения линейной функции, поэтому в базис исходной задачи надо включить вектор, которому соответствует т. е. вектор x₁ с разрешающим элементом 1, а x₄ исключаем из базиса и т. д. В итоге получаем: план = (9/2; 0; 1/2; 0; 0) оптимальный, т. к. все ∆_j = z_j – c_j  0, Z min = = –

б) решение двойственной задачи:

x ₁ х₂ х₃ х₄ х₅

СП БП

y₃ y₄ y₅ y₁ y₂,

БП СП

тогда оптимальный план = (– 7/2; – 3/2; 0; – 12; 0), F max = F = = – 13/2. Так как все y_j ≥ 0, то умножив на (– 1), получим

= (7/2; 3/2; 0; 12; 0).

Задания для самостоятельной работы

Задание 1. Составить двойственную задачу для исходной задачи из задания (тема 1, стр. 11). Дать экономическую интерпретацию полученной двойственной задачи.

Задание 2. Составить двойственную задачу для исходной задачи из заданий 1 и 2 (тема 2, стр. 26 – 29) и решить ее. Сравнить полученные результаты в двойственной и исходной задаче.

5. Элементы теории матричных игр

5.1. Матричные игры с нулевой суммой

Теория игр занимается разработкой рекомендаций по принятию ре­шений в конфликтных ситуациях. Математически конфликтную ситуа­цию можно представить как игру двух, трех и более игроков, каждый из кото­рых имеет цель максимизации своего выигрыша за счет другого иг­рока. Иногда теорию игр определяют как раздел математики, изучающий выработку оптимальных правил поведения для каждой стороны, участ­вующей в конфликтной ситуации. Совокупность этих правил называется стратегией.

Под термином игра понимается совокупность предварительно оговоренных правил и условий.

Е сли n партнеров (игроков) P₁, Р₂, ..., Р_n участвуют в данной игре, то основное содержание теории игр состоит в изучении следующей про­блемы: как должен вести партию j-й партнер (j = 1, n) (т. е., что он должен делать, какие правила выполнять) для достижения наиболее благоприятного для себя исхода.

В конце партии предполагается, что каждый игрок P_j получит сумму _j, называемую выигрышем, причем каждый игрок преследует цель мак­симизации общей суммы выигрыша. Числа _j могут быть положитель­ными, отрицательными и нулем:

а) если _j > 0, тогда j-й игрок выиграл;

б) если _j < 0, тогда j-й игрок проиграл;

в) если _j = 0, тогда игра имеет ничейный исход.

В большинстве случаев имеем игры с нулевой суммой, т. е. ₁+ ₂ +... + _n = 0. В этих играх сумма выигрыша переходит от одного партнера к другому, не поступая из внешних источников. Игра с нулевой суммой означает, что сумма выигрышей всех игроков в каждой партии равна нулю. В них общая сумма выигрыша перераспределяется между игроками, но не меняется. Примерами игры с нулевой суммой служат многие экономические задачи. В противном случае имеем игру с ненулевой суммой.

Игры, в которых участвуют 2 игрока, называются парными, а игры с большим числом участников – множественными. Принятие игро­ком того или иного решения в процессе игры называется ходом. Ходы могут быть личные и случайные. Если ход выбирается сознательно – это личный ход, иначе – это случайный ход. Игры бывают:

• конечные: каждый из участников имеет конечное число возможных стратегий;

• бесконечные: если хотя бы один из игроков имеет бесконечное число стратегий (ходов);

• бескоалиционные: если игроки не имеют право вступать в соглашения между собой;

• коалиционные: если игроки имеют право вступать в соглашения;

• кооперативные: это игры, в которых заранее определены коалиции.

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

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

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

Рассмотрим примеры простейших матричных игр.

Пример 17. Шахматы – игра двух партнеров с конечным числом личных ходов.

Пример 18. Игра в «три пальца». Игроки А и В одновременно и независимо друг от друга показывают один, два или три пальца. Размер выигрыша определяется общим количеством показанных пальцев. При этом, если число пальцев четное, то выигрывает игрок А, нечетное – игрок В. Такую игру двух игроков можно представить в виде матрицы

Игрок В

Игрок А

где индекс i указывает количество пальцев игрока А, а индекс j – количество пальцев игрока В. Например, а₁₃ = 4 – выигрыш 4 ед. А, а₃₂ = – 5 – проигрыш 5 ед. А и выигрыш 5 ед. В.

Пример 19. Игрок А выбирает одну из двух сторон монеты, игрок В не зная выбора первого, также выбирает одну из сторон. После того, как оба игрока произвели свой выбор и монета брошена, игрок В платит «1» игроку А, если выбранные стороны монеты совпали, и «(– 1)»,если не совпали, т. е. здесь «1» соответствует выигрышу А (проигрышу В), а «(– 1)» соответствует выигрышу В (проигрышу А), т. е. мы говорим, что А играет на maх, а В – на min.

Задачу можно представить табл. 25:

Таблица 25

Таким образом, условия игры определяются матрицей

,

строки которой соответствуют стратегиям для игрока А, а столбцы – страте­гиям для игрока В.

Как только А выбирает строку, а В – столбец, партия заканчивается и выигрыш игрока А равен числу, стоящему на пересечении этой строки и столбца. Число а₂₁ = – 1 показывает на проигрыш А и выигрыш В. Это пример матричной игры 2-го порядка.

В общем случае матричная игра задается матрицей, у которой номер i-й строки соответствует номеру стратегии игрока А, а номер j-гo столбца – номеру стратегии игрока В.

Каждый элемент а_ij матрицы является действительным числом и представляет собой сумму выигрыша, уплачиваемую игроком В игроку А, если А выбирает стратегию, соответствующую строке i, а В – столбцу j. Матричную игру записывают в виде табл. 26, называемой платежной матрицей, где A_i = (i = ) – стратегия игрока А, а B_j = (j = ) – стратегия игрока В.

Таблица 26