Общая задача линейного программирования

Лекция 5 (ММвТУиИО) ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЗЛП) Определение 1. Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции (1) при условиях (2) (3) (4) где - заданные постоянные величины и . Определение 2. Функция (1) называется целевой функцией (или линейной формой) задачи (1) – (4), а условия (2) – (4) – ограничениями данной задачи. Определение 3. Стандартной (или симметричной} задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1) при выполнении условий (2) и (4), где k = m и l = n (т.е. все ограничения имеют вид , а переменные неотрицательны). Определение 4. Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1) при выполнении условий (3) и (4), где k = 0 и l = п (т.е. все ограничения имеют вид = , а переменные неотрицательны) . Определение 5. Совокупность чисел , удовлетворяющих ограничениям задачи (2) – (4), называется допустимым решением (или планом). Определение 6. План , при котором целевая функция задачи (1) принимает свое максимальное (минимальное) значение, называется оптимальным. Значение целевой функции (1) при плане Х будем обозначать через . * Следовательно, X – оптимальный план задачи, если для любого Х выполняется неравенство . 1 Лекция 5 (ММвТУиИО) Указанные выше три формы задачи линейного программирования эквивалентны в том смысле, что каждая из них с помощью несложных преобразований может быть приведена к форме другой задачи. Это означает, что если имеется способ нахождения решения одной из указанных задач, то тем самым может быть определен оптимальный план любой из трех задач. Чтобы перейти от одной формы записи задачи линейного программирования к другой, нужно уметь: 1) сводить задачу минимизации функции к задаче максимизации; 2) переходить от ограничений-неравенств к ограничениям-равенствам и наоборот; 3) заменять переменные, которые не подчинены условию неотрицательности. В том случае, когда требуется найти минимум функции , можно перейти к нахождению максимума функции , поскольку . Ограничение-неравенство исходной задачи линейного программирования, имеющее вид “ ”, можно преобразовать в ограничение-равенство добавлением к его левой части дополнительной неотрицательной переменной, а ограничениенеравенство вида “ ” – в ограничение-равенство вычитанием из его левой части дополнительной неотрицательной переменной. Таким образом, ограничениенеравенство преобразуется в ограничение-равенство (5) а ограничение-неравенство – в ограничение-равенство (6) В то же время каждое уравнение системы ограничений можно записать в виде неравенств: (7) Число вводимых дополнительных неотрицательных переменных при преобразовании ограничений-неравенств в ограничения-равенства равно числу преобразуемых неравенств. Замечание. Вводимые дополнительные переменные имеют вполне определенный экономический смысл. Так, если в ограничениях исходной задачи линейного программирования отражается расход и наличие производственных ресурсов, то числовое значение дополнительной переменной в плане задачи, записанной в форме основной, равно объему неиспользуемого соответствующего ресурса. И, если переменная , не подчинена условию неотрицательности, то ее следует заменить двумя неотрицательными переменными и vk, приняв .. 2 Лекция 5 (ММвТУиИО) Рассмотрим ЗЛП в стандартной форме: f  c1 x1  ...  cn xn  max (1) a11 x1  ...  a1n x n  b1  a 21 x1  ...  a 2 n x n  b2  ... a x  ...  a x  b mn n m  m1 1  x j  0, j  1, n  (2) В этой (исходной) задаче:       требуется максимизировать целевую функцию; все ограничения являются неравенствами со знаком «»; задача содержит n управляющих переменных и m ограничений; все переменные х1,…,хn неотрицательны; коэффициенты при переменных в целевой функции: с1,…,сn; свободные члены: b1,…,bm. Двойственная задача линейного программирования имеет вид g  b1 y1  ...  bm y m  min (3) a11 y1  ...  a m1 y m  c1  a 21 y1  ...  a m 2 y m  c 2  ... a y  ...  a y  c mn m m  1n 1  y i  0, i  1, m (4) В этой задаче:      требуется найти минимум целевой функции; все ограничения – неравенства со знаком «»; управляющие переменные y1,…,ym неотрицательны; задача содержит m управляющих переменных и n ограничений; коэффициенты при переменных в целевой функции: b1,…,bm являются свободными членами исходной задачи линейного программирования, а свободные члены двойственной задачи линейного программирования: с1,…,cn – коэффициентами целевой функции исходной задачи линейного программирования;  матрица коэффициентов aij двойственной задачи транспонирована, т.е. строки заменены столбцами, а столбцы – строками. Задача (3)-( 4) называется двойственной к задаче (1)-(2). 3 Лекция 5 (ММвТУиИО) А обе задачи (1)-(2) и (3)-( 4) называются парой взаимно двойственных задач линейного программирования. Пара взаимно двойственных задач обладает следующими свойствами: 1. Если одна из задач является задачей на минимум, то двойственная ей задача будет задачей на максимум. 2. Если в ограничения одной из задач входит n неизвестных и m ограничений, то в ограничения двойственной задачи математического программирования входит m неизвестных и n ограничений. 3. Матрицы из коэффициентов при неизвестных в левых частях ограничений двойственных задач являются транспонированными друг к другу:  a11 a12 ... a1n     a 21 a 22 ... a 2 n  À ... ... ... ...     a a ... a  mn   m1 m 2  a11 a 21 ... a m1    a a ... a  m2  ÀT   12 22 ... ... ... ...     a a ... a  mn   1n 2 n 4. В правых частях специальных ограничений каждой из двойственных задач стоят коэффициенты при неизвестных целевой функции другой задачи. 5. Каждая из двойственных задач может быть задана в стандартной форме. Причем, если в первой задаче все неравенства будут типа , то во второй задаче неравенства будут типа . Для двойственных задач верна следующая теорема. Теорема двойственности: если одна из взаимно двойственных задач имеет оптимальное решение х*, то другая также имеет оптимальное решение y*. При этом соответствующие им оптимальные значения целевых функций f*=f(x*) и g*=g(y*) равны: f(x*)= g(y*). Пример 5.1. Дана задача линейного программирования: f  3x1  4 x 2  max  x1  x 2  16 4 x  x  48 2  1  x  4 x  48 2  1  x j  0, j  1,2  Составить двойственную задачу линейного программирования и привести ее к канонической форме. Решение: Каноническая форма исходной задачи – 4 Лекция 5 (ММвТУиИО) f  3x1  4 x 2  max  x3  x1  x 2  16  x  4 x  x  48 1 2  4  x  x  4 x  48 1 2  5  x j  0, j  1,5  Составим двойственную задачу g  16 y1  48 y 2  48 y3  min  y1  4 y 2  y 3  3   y1  y 2  4 y 3  4   y j  0, j  1,3 Приводим эту задачу к канонической форме g  16 y1  48 y2  48 y3  max  y1  4 y 2  y 3  y 4  3   y1  y 2  4 y 3  y 5  4   y j  0, j  1,5 ПРИВЕДЕНИЕ МАТРИЧНОЙ ИГРЫ К ЗЛП Пусть игра задана платежной матрицей (aij). Найдем оптимальную стратегию игрока А: 𝑃 = {𝑝1 , 𝑝2 , … , 𝑝𝑚 } где 𝑝1 + 𝑝2 + ⋯ + 𝑝𝑚 = 1 Оптимальная стратегия Р обеспечивает игроку А выигрыш не меньший чем цена игры ν и выигрыш равный ν, если игрок В придерживается своей оптимальной стратегии. Будем считать, что все выигрыши aij положительны. Этого всегда можно добиться, добавляя ко всем членам матрицы достаточно большое число М; от этого цена игры увеличится на М, а решения Р и Q в смешанных стратегиях не изменятся. Если все выигрыши aij положительны, то и цена игры, т.е. средний выигрыш при оптимальной стратегии тоже положителен: ν > 0. Пусть игрок В использует чистую стратегию Bk, а игрок А использует смешанную стратегию Р, т.е. выбирает чистые стратегии A1, A2, …, Am с 5 Лекция 5 (ММвТУиИО) вероятностями 𝑝1 , 𝑝2 , … , 𝑝𝑚 . Средний выигрыш игрока А (математическое ожидание выигрыша) 𝑎1𝑘 𝑝1 + 𝑎2𝑘 𝑝2 + ⋯ + 𝑎𝑚𝑘 𝑝𝑚 не может быть меньше цены игры ν и это справедливо для каждой из чистых стратегий Bk, k=1, …, n, игрока В, т.е. 𝑎11 𝑝1 + 𝑎21 𝑝2 + ⋯ + 𝑎𝑚1 𝑝𝑚 ≥ 𝜈 𝑎12 𝑝1 + 𝑎22 𝑝2 + ⋯ + 𝑎𝑚2 𝑝𝑚 ≥ 𝜈 … {𝑎1𝑛 𝑝1 + 𝑎2𝑛 𝑝2 + ⋯ + 𝑎𝑚𝑛 𝑝𝑚 ≥ 𝜈 Каждое из неравенств поделим на ν и введем обозначения 𝑝1 𝑝2 𝑝𝑚 𝑦1 = , 𝑦2 = , …, 𝑦𝑚 = 𝜈 𝜈 𝜈 В этих обозначениях предыдущая система запишется в виде: 𝑎11 𝑦1 + 𝑎21 𝑦2 + ⋯ + 𝑎𝑚1 𝑦𝑚 ≥ 1 𝑎12 𝑦1 + 𝑎22 𝑦2 + ⋯ + 𝑎𝑚2 𝑦𝑚 ≥ 1 … {𝑎1𝑛 𝑦1 + 𝑎2𝑛 𝑦2 + ⋯ + 𝑎𝑚𝑛 𝑦𝑚 ≥ 1 (5) Поделим также выражение 𝑝1 + 𝑝2 + ⋯ + 𝑝𝑚 = 1 на ν, получим 1 𝑦1 + 𝑦2 + ⋯ + 𝑦𝑚 = = 𝑔 𝜈 (6) Игрок А стремится максимизировать значение ν или, что то же самое, 1 минимизировать 𝑔 = . Таким образом, приходим к следующей задаче: 𝜈 Требуется найти такие значение неотрицательных переменных 𝒚𝟏 , 𝒚𝟐 , … , 𝒚𝒎 , которые удовлетворяют ограничениям (5) и дают минимальное значение функции (6). Такая задача является задачей линейного программирования: 1 𝑔 = = 𝑦1 + 𝑦2 + ⋯ + 𝑦𝑚 → 𝑚𝑖𝑛 𝜈 𝑎11 𝑦1 + 𝑎21 𝑦2 + ⋯ + 𝑎𝑚1 𝑦𝑚 ≥ 1 𝑎12 𝑦1 + 𝑎22 𝑦2 + ⋯ + 𝑎𝑚2 𝑦𝑚 ≥ 1 … {𝑎1𝑛 𝑦1 + 𝑎2𝑛 𝑦2 + ⋯ + 𝑎𝑚𝑛 𝑦𝑚 ≥ 1 Оптимальная стратегия игрока В ищется аналогично: пусть игрок В придерживается своей оптимальной стратегии 𝑄 = {𝑞1 , 𝑞2 , … , 𝑞𝑚 }, а игрок А выбирает чистые стратегии, тогда средний проигрыш игрока В не может быть больше цены игры ν, т.е. 6 Лекция 5 (ММвТУиИО) 𝑎11 𝑞1 + 𝑎12 𝑞2 + ⋯ + 𝑎1𝑛 𝑞𝑛 ≤ 𝜈 𝑎21 𝑞1 + 𝑎22 𝑞2 + ⋯ + 𝑎2𝑛 𝑞𝑛 ≤ 𝜈 … {𝑎𝑚1 𝑞1 + 𝑎𝑚2 𝑞2 + ⋯ + 𝑎𝑚𝑛 𝑞𝑚 ≤ 𝜈 Вероятности 𝑞1 , 𝑞2 , … , 𝑞𝑛 удовлетворяют условию 𝑞1 + 𝑞2 + ⋯ + 𝑞𝑛 = 1 Поделив данное равенство и все неравенства предыдущей системы на ν и введя обозначения 𝑞1 𝑞2 𝑞𝑚 𝑥1 = , 𝑥2 = , …, 𝑥𝑚 = 𝜈 𝜈 𝜈 получим 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 1 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 1 … {𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑚 ≤ 1 1 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑚 = = 𝑓 𝜈 (7) (8) Цель игрока В состоит в минимизации проигрыша или в максимизации величины 1 𝑓 = . Таким образом, задача состоит в нахождении неотрицательных переменных 𝜈 𝑥1 , 𝑥2 , … , 𝑥𝑛 , дающих максимальное значение функции (8) при выполнении ограничений (7). 1 𝑓 = = 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑚 → 𝑚𝑎𝑥 𝜈 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 1 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 1 … {𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑚 ≤ 1 Сравнивая две задачи линейного программирования (5)-(6) и (7)-(8), видим, что для записи ограничений используется одна и та же матрица 𝑎11 𝑎12 … 𝑎1𝑛 𝑎21 𝑎22 … 𝑎2𝑛 𝐴=( … … … … ), 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 только в системе (7) используются строки матрицы А, а в системе (5) – столбцы. Т.е. задачи (6)-(5) и (8)-(7) являются парой взаимно двойственных задач. Пример 5.2. Предприятие может выпускать 3 вида продукции A1, A2, A3. Спрос на продукцию предприятия зависит от многих факторов и может находиться в одном из состояний В1, В2, В3, В4. Известна прибыль, которую приносит реализация каждого вида продукции при различных состояниях спроса: 7 Лекция 5 (ММвТУиИО) Состояния спроса В2 В3 3 6 10 4 7 5 В1 В4 Виды A1 3 8 продукции A2 9 2 A3 7 4 Требуется формализовать данную задачу. Решение. Эта экономическая задача сводится к игре предприятия (игрок А), которое должно определить вид выпускаемой продукции против спроса (игрок В). Платежная матрица: 3 3 6 8 A=(9 10 4 2) 7 7 5 4 Анализируя стратегии игроков, замечаем, что стратегия В1 доминирует над стратегией В2, т.к. все элементы столбца В1 меньше или равны соответствующих элементов столбца В2, поэтому столбец можно исключить из рассмотрения. В результате получаем платежную матрицу: 3 6 8 A=(9 4 2) 7 5 4 Определим верхнюю и нижнюю цену игры. В1 В2 В3 α A1 3 6 8 3 A2 9 4 2 2 A3 7 5 4 4 β 9 8 6 Нижняя и верхняя цена игры не совпадают: α = 4 < β = 6, поэтому матрица не имеет седловой точки и игра не имеет решения в чистых стратегиях. Найдем смешанные стратегии 𝑃 = {𝑝1 , 𝑝2 , 𝑝3 } и 𝑄 = {𝑞1 , 𝑞2 , 𝑞3 }. Введем обозначения 𝑦𝑖 = 𝑝𝑖 𝜈 , 𝑖 = 1,2,3; 𝑥𝑗 = 𝑞𝑗 𝜈 , 𝑗 = 1,2,3 и составим две задачи линейного программирования: Игрок А (предприятие) 𝑔 = 𝑦1 + 𝑦2 + 𝑦3 → 𝑚𝑖𝑛 3𝑦1 6𝑦1 8𝑦1 { 𝑦𝑖 + 9𝑦2 + 4𝑦2 + 2𝑦2 ≥ 0, + 7𝑦3 ≥ 1 + 5𝑦3 ≥ 1 + 4𝑦3 ≥ 1 𝑖 = 1,2,3 8 Лекция 5 (ММвТУиИО) Игрок B (спрос) 𝑓 = 𝑥1 + 𝑥2 + 𝑥3 → 𝑚𝑎𝑥 3𝑥1 + 6𝑥2 9𝑥1 + 4𝑥2 7𝑥1 + 5𝑥2 { 𝑥𝑖 ≥ 0, + 8𝑥3 ≤ 1 + 2𝑥3 ≤ 1 + 4𝑥3 ≤ 1 𝑗 = 1,2,3 РЕШЕНИЕ ЗАДАЧ ЗЛП Классификацию решения задач линейного программирования можно представить в виде следующей таблицы: Метод решения 1. Графический метод 2. Симплексный метод 3. Метод Гомори Примечание Используется при двух переменных (x1, x2) Формы записи: симплексная таблица Алгоритм решения: метод искусственного базиса Алгоритм решения: метод отсечений Целевая функция max, min max, min max, min ИТЕРАЦИОННЫЙ МЕТОД РЕШЕНИЯ МАТРИЧНЫХ ИГР Опишем эвристический метод отыскания решения матричной игры (цены игры и оптимальных смешанных стратегий), основанный на накопления опыта постепенной выработки игроками хороших стратегий в результате многих повторений конфликтных ситуаций. Основная идея этого метода заключается в том, чтобы смоделировать практическое «обучение» игроков в ходе самой игры, когда каждый из них на опыте учитывает поведение противника и старается отвечать на него наиболее выгодным для себя образом. Иными словами, всякий раз при возобновлении игры игрок выбирает наиболее выгодную для себя стратегию, опираясь на предыдущий выбор противника. Проиллюстрируем этот метод на примере игры, заданной матрицей 2 0 3 ( ) 1 3 −3 В этой игре нижняя цена игры равна 0, верхняя цена игры – 2. Следовательно, седловой точки нет. Опишем правила выбора ходов игроками, предположив для определенности, что начинает игрок А: ход игрока А – стратегия А1 - (2 𝟎 3) Игрок В, учитывая это, выбирает свою стратегию так, чтобы выигрыш игрока А был минимален, т.е. равен нулю: 9 Лекция 5 (ММвТУиИО) ход игрока В – стратегия В2 – ( ) 𝟑 Игрок А выбирает свою стратегию так, чтобы его выигрыш при стратегии В2 игрока В был максимален: ход игрока А – стратегия А2 - (1 3 −3) Игрок В выбирает свою стратегию так, чтобы «накопленный» выигрыш игрока А при стратегиях А1 и А2 был минимален: (2 0 3) + (1 3 −3) = (3 3 𝟎) 3 ход игрока В – стратегия В3 = ( ) −3 Игрок А выбирает свою стратегию так, чтобы его «накопленный» выигрыш при стратегиях В2 и В3 игрока В был максимален: 3 𝟑 ( )+( )=( ) 3 −3 ход игрока А – стратегия А1 = (2 0 3) Игрок В выбирает свою стратегию так, чтобы «накопленный» выигрыш игрока А при стратегиях А1, А2 и А1 был минимален: (3 3 0) + (2 0 3) = (5 𝟑 3) ход игрока В – стратегия В2 = ( ) 𝟑 и т.д. Разобьем последовательные ходы игроков А и В на пары (ход игрока А, ход игрока В) и запишем результаты в таблице, где: n i B1 B2 B3 ν*(n) k A1 A2 ν*(n) ν(n) 1 2 3 4 5 6 7 8 9 10 11 1 1 2 3 0,00 2 3,00 1,50 3 2 2 3 3 0,00 3 1,50 0,75 3 3 1 5 3 1,00 2 3 1,00 1,00 3 3 4 1 7 6 0,75 2 3 1,50 1,12 3 6 5 2 8 6 0,60 3 3 1,2 0,9 3 6 6 1 10 6 1,00 2 6 1,00 1,00 6 6 7 1 12 9 0,86 2 6 1,44 1,15 6 9 8 2 13 9 0,75 3 6 1,13 0,93 6 9 9 1 15 9 1,00 2 9 1,00 1,00 9 9 10 1 17 12 0,90 2 9 1,20 1,05 9 12 11 2 18 12 0,82 3 9 1,09 0,96 9 12 12 1 20 12 1,00 2 12 1,00 1,00 12 12 … 1-ый столбец – номер n шага (пары последовательных ходов игроков А и В); 2-ой столбец – номер i стратегии, выбранной игроком А; 3-ий столбец – «накопленный» суммарный выигрыш игрока А за первые n шагов при выборе игроком В стратегии В1; 10 Лекция 5 (ММвТУиИО) 4-ый столбец – «накопленный» суммарный выигрыш игрока А за первые n шагов при выборе игроком В стратегии В2; 5-ый столбец – «накопленный» суммарный выигрыш игрока А за первые n шагов при выборе игроком В стратегии В3; (минимальный из этих выигрышей выделяется полужирным шрифтом), 6-ой столбец – минимальный средний выигрыш игрока А, равный минимальному накопленному им выигрышу за первые n шагов, деленному на число этих шагов; 7-ой столбец – номер k стратегии, выбранной игроком В; 8-ой столбец – «накопленный» суммарный выигрыш игрока А за первые n шагов при выборе им стратегии А1; 9-ый столбец – «накопленный» суммарный выигрыш игрока А за первые n шагов при выборе им стратегии А2; (максимальный из этих выигрышей выделяется полужирным шрифтом), 10-ый столбец – максимальный средний выигрыш игрока А, равный максимальному накопленному им выигрышу за первые n шагов, деленному на число этих шагов; 11-ый столбец – среднее арифметическое минимального среднего выигрыша и максимального среднего выигрыша игрока А. Решение игры определяется приближенно по окончании любого из шагов. Например, за приближенную цену игры можно взять среднее арифметическое ν(n), полученное на n-м шаге. Смешанные стратегии противников определяются частотами появления чистых стратегий. Например, после 9-го шага имеем ν(9) = 1,00 При этом игрок А 6 раз использовал стратегию А1 и 3 раза стратегию А2. В свою очередь игрок В 6 раз применял стратегию В2, 3 раза стратегию В3, а стратегией В1 не пользовался вообще. Отсюда получаем, что 2 1 2 1 𝑃9 ≈ { , } , 𝑄9 ≈ {0, , } 3 3 3 3 Соответственно, после 10-го шага получаем ν(10) = 1,05 7 3 7 3 𝑃9 ≈ { , } , 𝑄9 ≈ {0, , } 10 10 10 10 Т.к. игра легко решается графически, полезно сравнить полученные результаты с точными: ν=1 2 1 2 1 𝑃 = { , }, 𝑄 = {0, , } 3 3 3 3 Сравнивая результаты, полученные на 9-м, 10-м, а также 11-м и 12-м шагах: ν(11) = 0,96 11 Лекция 5 (ММвТУиИО) 𝑃11 ≈ { 7 4 , }, 11 11 𝑄11 ≈ {0, 7 4 , } 11 11 ν(12) = 1,00 2 1 2 1 𝑃12 ≈ { , } , 𝑄11 ≈ {0, , } 3 3 3 3 можно заметить, что по мере увеличения числа шагов приближенные значения все меньше отличаются от точных. Замечания: 1) При увеличении числа шагов все три величины ν*(n), ν*(n) и ν(n)будут приближаться к цене игры ν, но среднее арифметическое ν(n) будет приближаться к ν сравнительно быстрее. 2) Хотя сходимость итераций весьма медленна, тем не менее, даже такой небольшой расчет дает возможность находить ориентировочное значение цены игры и доли чистых стратегий. 3) Сравнительно медленную скорость сходимости можно объяснить рядом причин. Укажем одну из них, психологически наиболее интересную. Если, к примеру, игрок А уже нашел свою оптимальную смешанную стратегию, то он не склонен останавливаться на ней – он продолжит попытки выиграть у противника В побольше, особенно если последний еще не достиг своего оптимума. Тем самым игрок А может невольно ухудшить свое положение. 4) Основные преимущества описанного метода: - проста и одновременно универсальность (с его помощью можно легко найти приближенное решение любой матричной игры); - объем и сложность вычислений сравнительно слабо растут по мере увеличения числа стратегий игроков (размеров матрицы игры). 12