Задачи оптимизации в экономике и финансах

Финансовый университет при Правительстве РФ Департамент анализа данных, принятия решений и финансовых технологий Методы оптимальных решений Лекция № 1: «Задачи оптимизации в экономике и финансах» Минкова Анастасия Сергеевна План лекции Функция спроса, эластичность функции спроса  Множество безубыточности  Функция предложения  Предельные величины в экономике  Функции нескольких переменных  Производственная функция  Функция полезности  Предельная полезность товара  Предельная норма замещения  2 Перечень учебной литературы: Основная    Методы оптимальных решений в экономике и финансах: учебник / И.А. Александрова [и др.]; под ред. В.М. Гончаренко, В.Ю. Попова. М.: Кнорус, 2014. Александрова И.А. Методы оптимальных решений. Руководство к решению задач: Учебное пособие / И.А. Александрова, В.М. Гончаренко. – М.: Финуниверситет, 2012 . Винюков И.А. Линейная алгебра: Учебное пособие. Ч. 4. Линейное программирование / И.А. Винюков, В.Ю. Попов, С.В. Пчелинцев; Под ред. В.Б. Гисина, С.В. Пчелинцева. – М.: Финуниверситет, 2013. 3 Перечень учебной литературы: Дополнительная    Исследование операций в экономике: Учебник для академического бакалавриата / Н.Ш. Кремер [и др.]; Финуниверситет; под ред. Н.Ш. Кремера. 3-е изд., перераб. и доп. – М.: Юрайт, 2014 Колемаев В.А. Математические методы и модели исследования операций. Учебник. М.: ЮНИТИ, 2008. Математика в экономике. Ч.2: Математический анализ: Учебник / А.С. Солодовников [и др.]. – 3-е изд., перераб. и доп. – М.: Финансы и статистика; Инфра-М, 2011 4 Методы оптимальных решений  Методы оптимальных решений является одним из разделов исследования операций – научной дисциплины, занимающейся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами  Цель исследования операций — количественное обоснование принимаемых решений по организации управления 5 Методы оптимальных решений  Математическая модель – модель, которая использует математические символы и методы для описания свойств и характеристик объекта или события  Экономико-математическая модель — математическое описание исследуемого экономического процесса или объекта 6 Математическое программирование • • Математическое программирование – математическая дисциплина, занимающаяся изучением экстремальных задач и разработкой методов их решения Задачи математического программирования делятся на задачи линейного и нелинейного программирования 7 Математическое программирование • • Если все функции f и φi линейные, то задача является задачей линейного программирования Если хотя бы одна из указанных функций нелинейна, то соответствующая задача является задачей нелинейного программирования 8 Функция спроса и ее эластичность Функция спроса D(p) определяет спрос (количество купленного товара) при цене p за единицу продукции  Эластичность спроса ЕD– относительное изменение спроса при относительном изменении цены товара  ∆D ⋅100% ED = D ∆p ⋅100% p 9 Функция спроса и ее эластичность  Если функция спроса дифференцируема, то под эластичностью понимается  ∆D ∆p  E D = lim  ÷  p  ∆p →0  D  Эластичность вычисляется по формуле D' ED = ⋅ p = (ln D)'⋅ p D 10 Эластичный и неэластичный спрос Спрос называется эластичным, если ED > 1 и неэластичным, если ED < 1  Если функция спроса не зависит от цены ( ED = 0 ), спрос – совершенно неэластичный  Если малое изменение цены приводит к значительному изменению спроса, то спрос совершенно эластичный ( ED = ∞ )  11 Эластичный и неэластичный спрос  Общая выручка (total revenue) TR (или R): R = p ⋅ D( p)  Если R ' = p '⋅D ( p ) + p ⋅ D ' ( p ) = D + p ⋅ D '  Эластичность выручки R' D + pD' D + pD' D' ER = ⋅ p = ⋅p= = 1 + ⋅ p = 1 + ED R pD D D 12 Эластичный и неэластичный спрос При эластичном спросе изменение цены приводит к изменению выручки в противоположном направлении, т.е. увеличение (уменьшение) цены приводит к уменьшению (увеличению) выручки  Если спрос неэластичен, то изменение цены вызывает изменение выручки в том же направлении, т.е. увеличение (уменьшение) цены приводит к увеличению (уменьшению) выручки  13 Задача 1 Функция спроса D( p ) = 8 − p Исследовать зависимость между эластичностью спроса и доходом от продажи товара 14 Решение    Функция спроса равна количеству реализованного товара , поэтому найдем функцию общего дохода: По экономическому смыслу: Рассмотрим поведение функции данном промежутке: на R’(p) R(p) 4 8 p 15 Решение Следовательно, функция при и убывает при  Найдем эластичность спроса:  возрастает Рассмотрим эластичный спрос: где - неположительная величина  R’(p) R(p) 4 8 p 16 Решение Функция возрастает при убывает при  Найдем эластичность спроса: и  Рассмотрим эластичный спрос: где - неположительная величина  При эластичном спросе функция возрастает при R’(p) R(p) 4 8 p 17 Решение Рассмотрим неэластичный спрос: где - неположительная величина  R’(p) При неэластичном спросе функция убывает при R(p) 4 8 p 18 Множество безубыточности  Общие издержки TC (total cost) компании состоят из фиксированных издержек FC (fixed cost), не зависящих от объемов произведенной продукции, и из переменных издержек VC (variable cost) TC = FC + VC  Множество, на котором общие издержки равны общей выручке (TC = ТR), называется множеством безубыточности 19 Задача 2 Пусть функция общих издержек 2 ТС = p + 8 p − 10 , а функция выручки равна ТR = 11 p Найти множество безубыточности общей 20 Решение   Множество безубыточности: TC = ТR Найдем корни уравнения и  5 p Т.о. производство убыточно при и прибыльно при 21 Функция предложения Функция предложения S(p) задает количество товара, которое поставщик может предложить по рыночной цене p  Рынок находится в равновесии, если покупатели могут купить столько товара, сколько им необходимо, а продавец может реализовать весь свой товар, который он собирается продать S(р0) = D(р0)  22 Задача 3 Пусть функция кратковременного спроса имеет вид D ( p ) = 18,9 − 0,225 p и функция кратковременного предложения S ( p ) = 17,4 + 0,15 p Найти эластичность кратковременного спроса в точке рыночного равновесия 23 Решение   В точке рыночного равновесия: S(р0) = D(р0) Найдем эластичность спроса: Вывод: Спрос является неэластичным 24 Задача 4 В каком отношении распределится налоговое бремя между потребителем и производителем, если 4 D( p) = ; S ( p) = 2 p − 2 p а величина дополнительного налога мала по сравнению с равновесной ценой? 25 Решение  Распределение налогового бремени между потребителем и производителем:  Найдем равновесную цену: S(р0) = D(р0) 26 Решение  Найдем производные от функции спроса и предложения при равновесной цене:  Распределение налогового бремени между потребителем и производителем: 27 Предельные величины в экономике Предельная величина определяется как ∆Y отношение относительного изменения ∆X ∆Y величины Y = Y ( X ) при изменении  ∆X величины X ∆Y MY = ∆X 28 Предельные величины в экономике  Если величина Y(X) является дифференцируемой функцией, то ∆Y MY = lim = Y '(X ) ∆X →0 ∆X 29 Задача об оптимизации прибыли  Необходимое прибыли условие максимизации МR = МС  Если функции выручки и дифференцируемы, то R' (q) = С ' (q )  издержек Функция прибыли: П (q ) = R (q ) − С (q ) R' (q) − С ' (q ) = 0 30 Задача 5 Пусть даны функция дохода 2 R(q ) = 1000q − q и функция затрат С (q ) = q − 196q + 5248q + 5000, 3 2 зависящие от количества товара q Найти максимум функции прибыли П (q ) 31 Решение   Найдем функцию прибыли: П (q) = R(q ) − С (q ) Найдем максимум функции прибыли: П’(q) П(q) 12 118 min max q 32 Решение   Точка максимума функции прибыли: Ответ: 33 Оптимизация налогообложения Предположим, что на продукцию компании вводится (дополнительный) фиксированный налог t на каждую единицу реализованного товара  Если ставка налога достаточно велика, то производство товара будет невыгодно, и это приведет его к остановке  Возникает вопрос о такой ставке налога, чтобы итоговый сбор был максимальным  34 Задача 6 Пусть доход от продажи (выручка): R(q ) = 54q − 4q 2 а затраты на выпуск продукта в зависимости от количества q: С (q ) = q 2 − 6q + 24 Найти величину налога t на каждую единицу продукта, чтобы налог T=tq от всей реализуемой продукции был максимальным, и весь налоговый сбор Как уменьшится количество выпускаемой продукции? 35 Решение Найдем объем производства без учета дополнительного налога  Найдем функцию прибыли:  П (q ) = R(q ) − С (q ) = 54q − 4q 2 − q 2 + 6q − 24 = = −5q 2 + 60q − 24  П 0 ' (q ) = −10q + 60 = 0 Из ее производной находим, что максимум прибыли достигается при объеме производства: q0 = 6 Решение  По причине введения дополнительного налога доход производителя уменьшится на величину Т = tq и составит R (T ) (q ) = 54q − 4q 2 − tq а его прибыль П (q) = R (T ) (q ) − С (q ) = 54q − 4q 2 − tq − q 2 + 6q − 24 = = −5q 2 + 60q − tq − 24 Решение В результате компания исходит из того, чтобы при реализации товара получить максимальную прибыль  Решим уравнение:  П ' (q ) = 60 − 10q − t = 0 q = 6 − t / 10 Общая налоговая выплата составит: T = tq = 6t − t 2 / 10  Решение T = tq = 6t − t 2 / 10  Вычислим максимум функции Т = T(t).  Из условия T’(t) = 0 следует, что 6−t /5 = 0 т.е. t = 30 Точка t = 30 является точкой максимума функции T(t). При этом весь налоговый сбор: 2 T (30) = 6 ⋅ 30 − 30 / 10 = 90 Решение Объем производства: q = 6 − 30 / 10 = 3  Таким образом, введение дополнительного налога уменьшает объем производства в 2 раза (с 6 до 3 ед. продукции)   Ответ: q0 = 6; t = 30; T (30) = 90; qt = 3 Функции нескольких переменных  Производственная функция – функция, выражающая объем продукции Q, полученной при использовании ресурсов X 1 , X 2 ,..., X n в количествах x1 , x2 ,..., xn соответственно Q = Q( x1 , x2 ,..., xn ) 41 Производственная функция  Производственная функция является непрерывной и определена на пространстве ресурсов: { } R = x = ( x1 , x2 ,..., xn ) ∈ R ; xi ≥ 0, i = 1,..., n n + n 42 Производственная функция  Производственная функция удовлетворяет условиям: 1. аксиома неотрицательности выпуска Q( x) ≥ 0(∀x ∈ R+n ) 2. производство невозможно в отсутствие ресурсов Q(0) = 0 3. аксиома монотонности n если x ≥ y ( ∀ x ∈ R Q( x) ≥ Q( y ), +) 43 Типы производственных функций 1. Линейная n Q( x) = ∑ ai xi , (ai > 0∀i = 0,..., n) i =1 2. Функция выпуск) Леонтьева (функция затраты-  x1 xn  Q( x) = min  ;...; , ai > 0(∀i ) an   a1 3. Производственная функция Кобба-Дугласа Q( x) = Ax1α1 ...xnα n , A, α i > 0(∀i ) 44 Производственная функция Двухфакторная производственная Кобба-Дугласа функция Q( K , L) = aK β L1− β , a > 0,0 < β < 1 45 Производственная функция Геометрическое место точек в пространстве факторов производства, в которых различные сочетания ресурсов дают одно и то же количество выпускаемой продукции, называют изоквантой 46 Оптимизация прибыли Задача 7 Для товаров X1 и X2 известны функции спроса: 1 q2 = 35 − p2 q1 = 54 − p1 2 Фирма-монополист имеет функцию издержек: С = 2q1 + 6q1q2 + 3q2 + 4 2 2 Вычислите максимальную прибыль фирмы в этих условиях и найдите соответствующий производственный план 47 Решение Найдем цены товаров X1 и X2 : p1 = 54 − q1 p2 = 70 − 2q2  Последовательно находим общую выручку: R (q1 , q2 ) = p1q1 + p2 q2 = (54 − q1 )q1 + (70 − 2q2 )q2 =  = − q1 − 2q2 + 54q1 + 70q2 2 2 Прибыль: 2 2 П (q1 , q2 ) = R(q1 , q2 ) − С (q1 , q2 ) = −3q1 − 5q2 + 54q1 + + 70q2 − 6q1q2 − 4  Решение  Критические точки функции П (q1 , q2 ) найдем из системы:  П 'q1 = −6q1 − 6q2 + 54 = 0   П 'q2 = −6q1 − 10q2 + 70 = 0 Решением системы является точка (5;4)  Найдем матрицу вторых производных G(П) функции П (q1 , q2 ) , которая не зависит от точки:   П q''1q1 G ( П ) =  ''  Пq q  21 П q''1q2   − 6 − 6  =  ''   П q2 q2   − 6 − 10  Решение  − 6 − 6   G (П ) =   − 6 − 10  имеет угловые миноры ∆1 = −6 < 0, ∆ 2 = (−6) ⋅ (−10) − (−6) 2 = 24 > 0  Поэтому точка (5;4) в силу выпуклости функции прибыли, является точкой ее глобального максимума и П max = П (5,4) = −3 ⋅ 52 − 5 ⋅ 4 2 + 54 ⋅ 5 + 70 ⋅ 4 − − 6 ⋅ 5 ⋅ 4 − 4 = 271  Ответ: q1 = 5; q2 = 4; П max = 271 Производственная функция  Пусть р > 0 – цена единицы выпускаемой продукции, а w = ( w1 , w2 ,..., wn ) > 0 - вектор цен на ресурсы 1. Функция дохода I ( x1 , x2 ,..., xn ) = pQ( x1 , x2 ,..., xn ) 2. Функция затрат С ( x1 , x2 ,..., xn ) = w1 x1 + ... + wn xn 3. Функция прибыли П ( x1 , x2 ,..., xn ) = pQ( x1 , x2 ,..., xn ) − w1 x1 − ... − wn xn 51 Производственная функция  Производитель решает оптимизационную задачу: П ( x1 , x2 ,..., xn ) → max  при условии xi ≥ 0 (i = 1,..., n) 52 Производственная функция * * * x = x x ( ,...,  Вектор ресурсов 1 n) является оптимальным производственным планом, максимальное значение производственной функции Q* = Q( x* ) - оптимальный выпуск 53 Производственная функция Теорема * * *  Для того, чтобы вектор x = ( x1 ,..., xn ) был оптимальным планом производства, необходимо и достаточно, чтобы он удовлетворял условиям:  ∂Q *  p ∂x x = w1 1  ...   p ∂Q x* = w n  ∂x n  xi* > 0 ( ) ( ) 54 Производственная функция  Производственный план x = ( x ,..., x ) называется рентабельным, если функция прибыли П (x) положительна * * 1 * n 55 Функция полезности  Функция полезности – функция, описывающая предпочтения потребителей на множестве товаров X 1 , X 2 ,..., X n и выражающая ценность набора товаров в количествах x1 , x2 ,..., xn соответственно U = U ( x1 , x2 ,..., xn ) 56 Функция полезности  Если U ( x1 , x2 ..., xn ) > U ( y1 , y2 ,..., yn ) для двух различных наборов x = ( x1 , x2 ,..., xn ) y = ( y1 , y2 ,..., yn ) , набор x является более полезным для потребителя, чем набор y 57 Бюджетное ограничение Пусть полные затраты производителя за некоторый период ограничены и определяются бюджетными ограничениями  Если стоимость единицы труда w и стоимость единицы капитальных ресурсов r, производитель может приобрести на рынке ресурсов любой набор из капитала К и труда L  С = r ⋅ K + w⋅ L 58 Бюджетная линия Бюджетная линия (или изокоста) – множество наборов факторов (К, L), имеющих одинаковую фиксированную стоимость  Уравнение изокосты:  C w K = − ⋅L r r 59 Предельная полезность товара  Предельной полезностью товара Xk называется частная производная функции U = U ( x1 , x2 ,..., xn ) по переменной xk U ' xk ∆U = lim ∆xk →∞ ∆x k 60 Предельная норма замещения  Предельной нормой замещения товара Xk товаром Xl для набора М = ( x1 , x2 ,..., xn ) называется отношение предельных полезностей товаров Xk и Xl MRS X k , X l ( M ) = ' xk ' xl U (M ) U (M ) 61 Предельная норма замещения  Изоклина для пары товаров Xk и Xl множество наборов товаров М = ( x1 , x2 ,..., xn ), для которых предельная норма замещения товара Xk товаром Xl постоянна MRS X k , X l ( M ) = const 62 Задача 8 Для функции полезности U ( x1 , x2 ) = Cx1 0 , 25 ⋅ x2 0 , 75 найти предельную полезность каждого товара и предельную норму замещения товара x1 товаром x2 в точке x1 = 16; x2 = 625 63 Решение  Найдем предельные полезности товаров x1 и x2:  Найдем предельную норму замещения товара x1 товаром x2: 64 Решение  Найдем предельную норму замещения товара x1 товаром x2  Предельная норма замещения в точке x1 = 16; x2 = 625 65 Задача 9 Для функции полезности U ( x1 , x2 ) = x1 ( x2 − 0,1x1 ) выяснить, является ли набор товаров ( x1 , x2 ) = (30;15) самым полезным из всех наборов, имеющих с ним равную стоимость, если p1 = 3; p2 = 10 66 Решение  Найдем предельные полезности товаров x1 и x2:  Найдем предельную норму замещения товара x1 товаром x2: 67 Решение  Найдем предельную товара x1 товаром x2  норму замещения Набор товаров является самым полезным из всех наборов, имеющих с ним равную стоимость, если 68 Решение  Следовательно, набор товаров ( x1 , x2 ) = (30;15) является самым полезным из всех наборов, имеющих с ним равную стоимость 69 Финансовый университет при Правительстве РФ Департамент анализа данных, принятия решений и финансовых технологий Методы оптимальных решений Лекция № 2: «Задачи линейного программирования» Минкова Анастасия Сергеевна План лекции Общая постановка задачи оптимизации  Задача математического программирования  Задача линейного программирования  Геометрия задачи линейного программирования; элементы теории выпуклых множеств  Графический метод решения задач линейного программирования  Симплекс-метод решения задач линейного программирования  71 Общая постановка задачи оптимизации  Пусть М – некоторое множество, точка X ∈ M , f(X) – функция на М. Тогда задача f ( X ) → max(min), X ∈ M называется задачей оптимизации  Множество М – допустимое множество, а функция f(X) – целевая функция 72 Общая постановка задачи оптимизации  Точка Xmax (Xmin), в которой достигается оптимальное значение называют оптимальным решением, множество всех оптимальных точек X* оптимальным множеством 73 Задача математического программирования  Если множество М является n подмножеством n-мерного пространства R (т.е. М ⊂ R n ), и его точка задается своими координатами X = ( x1 , x2 ,..., xn )  Целевая функция f ( X ) = f ( x1 , x2 ,..., xn ) n является некоторой функцией в R 74 Задача математического программирования  Тогда задача оптимизации f ( X ) = f ( x1 , x2 ,..., xn )  g1 ( x1 , x2 ,..., xn ) ≤ 0,  g ( x , x ,..., x ) ≤ 0,  2 1 2 n  ...   g m ( x1 , x2 ,..., xn ) ≤ 0, где допустимое множество М задается системой неравенств, g1 , g 2 ,..., g m - некоторые функции в R,n называется задачей математического программирования 75 Постановка задачи линейного программирования • Если функции f, g1, g2,…, gm линейны, то задача оптимизации имеет вид: ax(m in) f = c1 x1 + c2 x2 + . + cn xn + c0 → m Вместо знака «=» могут стоять знаки «≥» или «≤» 76 Постановка задачи линейного программирования • Нетривиальные ограничения ai1 x1 + ai 2 x2 + ... + ain xn • b1 , i = 1..., m • Тривиальные ограничения x j ≥ 0, j = 1,..., n • Целевая функция (линейная функция) имеет вид f = c1 x1 + c2 x2 + ... + cn xn + c0 • Система ограничений задает в n пространстве R выпуклое многогранное множество M 77 Задача линейного программирования • • • • • • Задачу линейного программирования можно записать в матричном виде Введем строку С = (с1, с2,…, сn), столбец X = (x1, x2,…, xn)Т, (m×n)-матрицу А = (aij), столбец В = (b1, b2,…, bm)Т Тогда задача линейного программирования будет иметь вид: f = СX + с0 → max  AX ≤ B  X ≥ 0 78 Задача линейного программирования План X*=(x1*,x2*,…,xn*), при котором целевая функция задачи принимает свое максимальное (минимальное) значение, называется оптимальным  Значение целевой функции при плане X обозначим F(X). Поскольку X* оптимальный план задачи, для любого X выполняется неравенство F (X) ≤ F (X*)  79 Задача линейного программирования • • Если система ограничений состоит только из уравнений и тривиальных неравенств задача ЛП имеет каноническую форму Если в системе ограничений имеются только неравенства – задача ЛП имеет стандартную форму 80 Приведение стандартной задачи линейного программирования к канонической  Если имеется стандартная задача линейного программирования, то для приведения ее к канонической достаточно для каждого из неравенств системы ограничений a1 x1 + a2 x2 + ... + an xn + b ≥ 0 ввести новую балансовую (дополнительную) переменную и заменить неравенство на эквивалентное ему уравнение a1 x1 + a2 x2 + ... + an xn + b = xn +1 где xn+1 – балансовая переменная, и неравенство xn+1 ≥ 0 81 Задача 1 Найти каноническую форму линейного программирования: задачи z = x1 + x2 + x3 → max 5 x1 + 10 x2 + 8 x3 ≤ 20 2 x + 4 x + 5 x ≥ 44  1 3 2  4 x1 + 2 x2 + x3 ≤ 25  xi ≥ 0, i = 1,2,3 82 Решение 1. Введем балансовые переменные в неравенства 1 – 3 и заменим их на эквивалентные им уравнения: 83 Решение 2. Запишем задачу программирования в форме: линейного канонической 84 Приведение канонической задачи линейного программирования к стандартной    Необходимо выделить в системе уравнений базисные и свободные переменные Выразить базисные переменные через свободные Исключить базисные переменные из целевой функции и ограничений в виде уравнений, преобразовать каждое из них в неравенство 85 Задача 2 Привести к стандартной форме задачу линейного программирования: 86 Решение 1. Выделим базисные и свободные переменные из системы ограничений: Используем метод Гаусса: 87 Решение 2. Запишем полученную систему уравнений: 3. Выразим базисные переменные: и подставим их в целевую функцию: 88 Решение 4. Запишем задачу линейного программирования в стандартной форме: или 89 Элементы теории выпуклых множеств   Множества, элементами которых являются точки, называются точечными Примеры точечных множеств на плоскости круг, прямая, луч, отрезок, угол, сектор, треугольник; в пространстве – шар, призма, параллелепипед 90 Элементы теории выпуклых множеств  Множество точек называется выпуклым, если оно содержит отрезок, их соединяющий 91 Элементы теории выпуклых множеств  Если существует хотя бы одна такая пара точек множества, что отрезок, соединяющий эти точки, не принадлежит целиком этому множеству, то оно называется невыпуклым 92 Элементы теории выпуклых множеств  Пересечение (общая часть) двух выпуклых множеств также является выпуклым множеством S = S1  S 2 93 Элементы теории выпуклых множеств   Среди точек выпуклого множества можно выделить внутренние, граничные и угловые точки Точка множества называется внутренней (точка N), если в некоторой ее окрестности содержатся точки только данного множества 94 Элементы теории выпуклых множеств  Точка области называется граничной (точка Р), если в любой ее окрестности содержатся как точки, принадлежащие данному множеству, так и точки, не принадлежащие ему 95 Элементы теории выпуклых множеств  Точка выпуклого множества называется угловой (или крайней), если через нее нельзя провести ни одного отрезка, состоящего только из точек данного множества, и для которого она была бы внутренней (точки A, B, C, D, E) 96 Элементы теории выпуклых множеств  Выпуклые многоугольники можно определить как выпуклые множества точек плоскости с конечным числом угловых точек  В пространстве выпуклое множество с конечным числом угловых точек называется выпуклым многогранником 97 Графический метод решения ЗЛП • Если задача задана в стандартной форме в R2 : f = c1 x1 + c2 x2 + c0 a11 x1 + a12 x2 ≤ b1 a x + a x ≤ b 2  21 1 22 2 ... a x + a x ≤ b m  m1 1 m 2 2  x1 ≥ 0, x2 ≥ 0 • Допустимой областью является выпуклая многоугольная область 98 Графический метод решения ЗЛП Теорема 1: Если в задаче линейного программирования допустимое множество непусто и целевая функция ограничена, то существует хотя бы одно оптимальное решение • Теорема 2: Если в задаче линейного программирования f ( X ) → max(min), X ∈ M допустимое множество М имеет хотя бы одну угловую точку, а целевая функция ограничена, то найдется угловая точка множества М, в которой принимает оптимальное значение данной задачи • 99 Графический метод решения задач линейного программирования 1. 2. Находим область допустимых решений (ОДР) для системы ограничений. Если ОДР – пустое множество, то задача не имеет решений Если ОДР является непустым множеством, строится вектор нормали n = (c1 ;c2 ) 100 Графический метод решения задач линейного программирования 3. Проводится линия уровня f, перпендикулярная вектору нормали n Линия уровня – прямая, на которой целевая функция принимает постоянное значение c1 x1 + c2 x2 = const Линия уровня определяет направление роста функции f 101 Графический метод решения задач линейного программирования 4. Перемещаем линию уровня в направлении вектора n, находим первую точку Xmin пересечения такой линии с ОДР. Тогда fmin = f(Xmin) – минимальное значение функции f на X 5. Продолжая перемещать линию уровня в направлении вектора n, находим Xmax – последнюю точку пересечения линии уровня с ОДР. Тогда fmax = f(Xmax) – максимальное значение функции f на X 102 Задача 1 Найти решение программирования: задачи линейного f = 4 x1 + 5 x2 → max 4 x1 + 6 x2 ≤ 24 3 x + 2 x ≤ 12  1 2   x1 + x2 ≤ 8  x j ≥ 0, j = 1,2  103 Решение 1. Изобразим на плоскости систему координат Ox1x2 Далее строим множество точек, соответствующее множеству решений основной системы ограничений Строим прямую l1 : 4 x1 + 6 x2 = 24 соответствующую первому неравенству системы ограничений 104 Решение Далее аналогично строятся прямые: l2 : 3x1 + 2 x2 = 12 (СD) l3 : x1 + x2 = 8 две другие (EF) Получаем ОДР в виде четырехугольника ОАМD, причем последнее ограничение не существенно 105 Решение 2. Находим координаты вектора нормали n и построим его Поскольку целевая функция имеет вид f = 4 x1 + 5 x2 , то n = ( 4;5) 106 Решение 3. Линия уровня f задается уравнением 4 x1 + 5 x2 = const Определим const = 0 и построим прямую 4 x1 + 5 x2 = 0 , проходящую через начало координат перпендикулярно вектору нормали n 107 Решение 4. Перемещаем линию уровня f по направлению вектора n Перемещение проводится до тех пор, пока у линии уровня не окажется только одна общая точка с ОДР Получаем точку M – точку экстремума целевой функции в ОДР 108 Решение Находим координаты точки экстремума и значение целевой функции в ней Точка М является точкой пересечения прямых l1и l2 Решаем систему уравнений 5. 4 x1 + 6 x2 = 24  3 x1 + 2 x2 = 12  x1 = 2,4   x2 = 2,4 М(2,4; 2,4) 109 Решение Точка М определяет оптимальное решение Xопт = (2,4; 2,4) При этом f max = f (Xопт) = f (2,4; 2,4) = 4∙2,4 + 5 ∙2,4 = 21,6 110 Задача 2 Найти решение задачи линейного программирования графическим методом: 111 Решение 1. По системе ограничений строим соответствующие прямые: l1 l2 l3 A n B X1 112 Решение Получаем ОДР, не ограниченную сверху. 2. Строим вектор нормали по целевой функции 3. Линия уровня задается уравнением l1 l2 l3 A n B X1 113 Решение 4. Перемещаем линию уровня по направлению вектора n Перемещение проводится до тех пор, пока у линии уровня не окажется только одна общая точка с ОДР Получаем точку В – точку минимума целевой функции в ОДР. Поскольку область сверху не ограничена, то l1 l2 l3 A n B X1 114 Решение 5. Находим координаты точки минимума и значение целевой функции в ней Точка В является точкой пересечения прямых l2 и l3 Решаем систему уравнений Точка В имеет координаты: В (2; 2) Ответ: 115 Задача 3 Найти решение задачи линейного программирования графическим методом: 116 Решение 1. Задача задана в канонической форме, приведем ее к стандартной форме. Выделим базисные и свободные переменные из системы ограничений: 117 Решение Запишем полученную систему уравнений: Выразим базисные переменные: и подставим их в целевую функцию: Задача линейного программирования: 118 Решение 1. По системе ограничений строим соответствующие прямые: Х4 l2 l1 A B X3 О С 119 Решение Строим вектор нормали по целевой функции 2. 3. Линия уровня задается уравнением Х4 l2 l1 A B n X3 О С 120 Решение Перемещаем линию уровня по направлению вектора n Точка В – точка минимума целевой функции. Отрезок [OА] – точки максимума целевой функции. 4. Х4 l2 l1 A B n X3 О С 121 Решение 5. Точка В (1; 1) Отрезок [OА]: O (0;0), А (0; 1,5) Найдем множество точек отрезка: 6. 7. Находим все координаты точек минимума и максимума из системы: Ответ: 122 Симплекс-метод Рассмотрим произвольную задачу линейного программирования, заданную в канонической форме: f = c1 x1 + c2 x2 + ... + cn xn + c0 → max a11 x1 + a12 x2 + ... + a1n xn = b1 a x + a x + ... + a x = b 2n n 2  21 1 22 2 ... a x + a x + ... + a x = b mn n m  m1 1 m 2 2  x1 ≥ 0, x2 ≥ 0,..., xn ≥ 0 123 Симплекс-метод С помощью эквивалентных преобразований систему ограничений и целевую функцию привели к виду: f = −γ r +1 xr +1 − γ r + 2 xr + 2 − ... − γ n xn + γ 0 → max  x1 + α1,r +1 xr +1 + α1,r + 2 xr + 2 + ... + α1n xn = β1   x2 + α 2,r +1 xr +1 + α 2,r + 2 xr + 2 + ... + α 2 n xn = β 2  ... x + α x + α r r , r +1 r +1 r , r + 2 xr + 2 + ... + α r , n xn = β r   x1 ≥ 0, x2 ≥ 0,..., xn ≥ 0 где β i ≥ 0, i = 1,..., r 124 Симплекс-метод  Целевую функцию переписываем в виде: f + γ r +1 xr +1 + γ r + 2 xr + 2 + ... + γ n xn = γ 0   Коэффициенты γ r +1 , γ r + 2 ,..., γ n называются оценками исходной задачи линейного программирования На основании значений оценок делается вывод об оптимальности допустимых решений задачи 125 Симплекс-метод  Запишем данные задачи в виде таблицы: x1 x2 β1 β2 xk βk xr f βr γ0 1 0 ... 0 ... 0 α1,r +1 ... α1 j 1 ... 0 ... 0 α 2,r +1 ... α 2 j ... α1n ... α 2 n ... ... ... ... ... ... ... α kn ... ... ... α rn ... γ n ... ... ... ... ... ... 1 ... ... ... ... ... ... ... ... 0 α k ,r +1 ... ... 1 α r ,r +1 0 γ r +1 ... ... ... α kj ... ... ... α rj ... γ j 126 Симплекс-метод 1. 2. Алгоритм решения задачи линейного программирования симплекс-методом: Если в последней строке нет отрицательных оценок, то оптимальное решение достигнуто Если в оценочной строке есть хотя бы одна отрицательная оценка, то решение может быть улучшено 127 Симплекс-метод Выбирается разрешающий столбец (возьмем столбец j), содержащий отрицательную оценку В качестве разрешающего элемента выбирается положительный элемент alj > 0, дающий минимум отношения элемента свободного столбца bi к aij :  bi  alj = min   aij > 0  a   ij  128 Симплекс-метод 3. 4. Если в симплекс-таблице имеется отрицательная оценка, а в соответствующем столбце нет положительных элементов, то исходная задача не имеет решения Если оптимальное решение найдено, но при этом у одной (или нескольких) свободной переменной оценка равна 0, задача имеет альтернативное решение Для его нахождения надо сделать шаг симплекс-метода, выбрав разрешающий элемент в свободном столбце с нулевой оценкой 129 Задача 4 Решить задачу линейного программирования симплекс-методом: 130 Решение:  Приведем систему к каноническому виду:  Выделим базисные переменные:  Перепишем целевую функцию: Решение:  Запишем начальную симплекс-таблицу: Базис bi x1 x2 x3 x4 x5 x3 2 1 -2 1 x4 18 3 1 1 x5 2 -1 1 1 z -1 -2 Базис bi x1 x2 x3 x4 x5 x3 2 1 -2 1 x4 18 3 1 1 x5 2 -1 1 1 z -1 -2 Базис x3 bi 6 x1 -1 x2 x3 1 x4 x5 2 x4 16 4 1 -1 x2 2 -1 1 1 z 4 -3 2 Базис x3 bi 6 x1 -1 x2 x3 1 x4 x5 2 x4 16 4 1 -1 x2 2 -1 1 1 z 4 -3 2 Базис x3 bi 10 x1 x2 x3 1 x4 0,3 x5 1,8 x1 4 1 0,3 -0,3 x2 6 1 0,3 0,8 z 16 0,8 1,3 Ответ: Задача 5 Решить задачу линейного программирования симплекс-методом  f = x1 + x2 + x3 → max 4 x + 6 x + 3 x ≤ 1 2 3  1 9 x1 + 5 x2 + 4 x3 ≤ 1 7 x + 3x + 6 x ≤ 1 2 3  1  x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 135 Решение:  Приведем систему к каноническому виду:  f = x1 + x2 + x3 → max 4 x + 6 x + 3 x + x ≤ 1 2 3 4  1 9 x1 + 5 x2 + 4 x3 + x5 ≤ 1 7 x + 3 x + 6 x + x ≤ 1 2 3 6  1  xi ≥ 0, i = 1,...,6  Перепишем целевую функцию: f − x1 − x2 − x3 = 0 Решение:  Запишем начальную симплекс-таблицу: Базис bi x1 x2 x3 x4 x5 x6 x4 1 4 6 3 1 x5 1 9 5 4 1 x6 1 7 3 6 1 f -1 -1 -1 1 1 1  1 min  ; ;  = 4 9 7 9 Базис bi x1 x2 x3 x4 x5 x6 x4 1 4 6 3 1 x5 1 9 5 4 1 x6 1 7 3 6 1 f -1 -1 -1 Базис bi x1 x2 x3 x4 x5 x6 x4 5/9 34/9 11/9 1 -4/9 x1 1/9 1 5/9 4/9 1/9 x6 2/9 -8/9 26/9 -7/9 1 f 1/9 -4/9 -5/9 1/9 5 1 1 1 min  ; ;  = 11 4 13  13 Базис bi x1 x2 x3 x4 x5 x6 x4 5/9 34/9 11/9 1 -4/9 x1 1/9 1 5/9 4/9 1/9 x6 2/9 -8/9 26/9 -7/9 1 f 1/9 -4/9 -5/9 1/9 Базис bi x1 x2 x3 x4 x5 x6 x4 6/13 54/13 1 -3/26 -11/26 x1 1/13 1 9/13 3/13 -2/13 x3 1/13 -4/13 1 -7/26 9/26 f 2/13 -8/13 1/26 5/26 1 1  1 min  ;  = 9 9  9 Базис bi x1 x2 x3 x4 x5 x6 x4 6/13 54/13 1 -3/26 -11/26 x1 1/13 1 9/13 3/13 -2/13 x3 1/13 -4/13 1 -7/26 9/26 f 2/13 -8/13 1/26 5/26 Базис bi x1 x2 x3 x4 x5 x6 x4 -6 1 -33/26 1/2 x2 1/9 13/9 1 1/3 -2/9 x3 1/9 4/9 1 -1/6 5/18 f 2/9 8/9 1/6 1/18 2   1 1 X =  0; ; ;0;0;0 , f = 9   9 9 * Спасибо за внимание! Финансовый университет при Правительстве РФ Департамент анализа данных, принятия решений и финансовых технологий Методы оптимальных решений Лекция № 3: «Транспортная задача» Минкова Анастасия Сергеевна Постановка транспортной задачи     Имеется m поставщиков A1 , A2, …, Am и n потребителей B1 , B2, …, Bn некоторого груза. Для каждого поставщика и потребителя заданы запасы ai ≥ 0, i = 1, 2, …, m и объем потребления bj ≥ 0, j = 1, 2, …, n. Известна стоимость перевозки единицы груза сij ≥ 0 от i-го поставщика к j-му потребителю. Требуется найти объемы всех перевозок xij от i-го поставщика к j-му потребителю, при которых общая стоимость минимальна. 2 Математическая постановка задачи Пусть X = (xij) – m×n матрица, где xij – объем перевозок от i-го поставщика к j-му потребителю.  Общие затраты на перевозку груза определяются функцией:  m n z ( X ) = ∑∑ cij xij i =1 j =1 3  Математическая постановка транспортной задачи определяется задачей линейного программирования: m n z ( X ) = ∑∑ cij xij → min i =1 j =1 при условиях m ∑x i =1 ij = b j , j = 1,..., n ij = ai , i = 1,..., m n ∑x j =1 xij ≥ 0 4 Постановка задачи  Любое неотрицательное решение задачи, определяемое матрицей X, называется планом транспортной задачи  План X*, при котором целевая функция принимает минимальное значение, называется оптимальным планом транспортной задачи 5 Постановка задачи  Транспортная задача называется задачей с правильным балансом, а ее модель закрытой, если суммарные запасы поставщиков равны суммарным запросам потребителей m n ∑a = ∑b i i =1  Если m n ∑a ≠ ∑b i =1 i j =1 j j =1 j , то задача называется задачей с неправильным балансом, а ее модель - открытой 6 Условие разрешимости транспортной задачи  Транспортная задача разрешима тогда и только тогда, когда суммарные запасы равны суммарным потребностям m n ∑a = ∑b i =1  i j =1 j Ранг матрицы системы ограничений транспортной задачи равен r (A) = m + n - 1 7 Основные этапы решения транспортной задачи 1. 2. 3. Построение начального опорного решения  метод северо-западного угла  метод минимального тарифа  метод Фогеля Оценки решения Улучшения решения 8 Задача 1 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную стоимость всех перевозок. B1 B2 B3 B4 ai A1 1 11 3 13 140 A2 12 4 8 2 160 A3 bj 3 5 14 6 100 80 40 150 130 9 Задача 1 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную стоимость всех перевозок. B1 B2 B3 B4 ai A1 1 11 3 13 140 A2 12 4 8 2 160 A3 bj 3 5 14 6 100 80 40 150 130 400 400 10 Задача 1 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную стоимость всех перевозок. B1 B2 B3 B4 ai A1 1 11 3 13 140 A2 12 4 8 2 160 A3 bj 3 5 14 6 100 80 40 150 130 400 400 400 11 1. Метод «северо-западного угла» B1 B2 B3 B4 ai 1 11 3 13 A2 12 4 8 2 A3 3 5 14 6 A1 bj 80 80 40 150 140 160 100 130 12 1. Метод «северо-западного угла» B1 B2 B4 ai 11 3 13 A2 12 4 8 2 A3 3 5 14 6 A1 bj 1 B3 80 40 80 40 150 140 160 100 130 13 1. Метод «северо-западного угла» B1 A1 B2 1 80 B3 11 40 B4 ai 3 13 20 A2 12 4 8 2 A3 3 5 14 6 bj 80 40 150 140 160 100 130 14 1. Метод «северо-западного угла» B1 A1 B2 1 80 11 40 A2 12 A3 3 bj B3 B4 ai 3 13 8 2 14 6 20 4 130 80 5 40 150 140 160 100 130 15 1. Метод «северо-западного угла» B1 A1 B2 1 80 11 40 A2 12 A3 3 bj B3 B4 3 13 8 2 20 4 130 80 ai 5 40 30 14 150 6 140 160 100 130 16 1. Метод «северо-западного угла» B1 A1 B2 1 80 11 40 A2 12 A3 3 bj B3 B4 3 13 8 2 20 4 130 5 30 14 6 100 80 ai 40 150 140 160 100 130 17 1. Метод «северо-западного угла» B1 A1 B2 1 80 11 40 A2 12 A3 3 bj B3 B4 3 13 8 2 20 4 130 5 30 14 6 100 80 Начальный опорный план: ai 40 150 140 160 100 130  80 40 20 0    X =  0 0 130 30   0 0 0 100    z(X) = 1·80 + 11·40 + 3·20 + 8·130 + 2·30 + 6·100 = 2280 18 2. Метод минимального тарифа B1 A1 B3 B4 ai 1 11 3 13 12 4 8 2 3 5 14 6 80 A2 A3 bj B2 80 40 150 140 160 100 130 19 2. Метод минимального тарифа B1 A1 B3 B4 ai 1 11 3 13 12 4 8 2 80 A2 130 3 A3 bj B2 80 5 40 14 150 6 140 160 100 130 20 2. Метод минимального тарифа B1 A1 1 B3 11 B4 ai 3 13 8 2 60 80 12 A2 4 130 3 A3 bj B2 80 5 40 14 150 6 140 160 100 130 21 2. Метод минимального тарифа B1 A1 1 B3 11 80 B4 ai 3 13 8 2 60 12 A2 4 130 3 A3 bj B2 80 5 40 14 150 6 140 160 100 130 22 2. Метод минимального тарифа B1 A1 1 B3 11 80 B4 3 13 4 8 2 30 130 3 A3 80 ai 60 12 A2 bj B2 5 40 14 150 6 140 160 100 130 23 2. Метод минимального тарифа B1 A1 1 B3 11 80 B4 3 13 4 8 2 30 130 3 A3 80 ai 60 12 A2 bj B2 5 40 14 150 6 140 160 100 130 24 2. Метод минимального тарифа B1 A1 1 B3 11 80 B4 3 13 4 8 2 30 130 3 A3 5 14 6 10 80 ai 60 12 A2 bj B2 40 150 140 160 100 130 25 2. Метод минимального тарифа B1 A1 1 B3 11 80 B4 3 13 4 8 2 30 130 3 A3 5 14 6 10 80 ai 60 12 A2 bj B2 40 150 140 160 100 130 26 2. Метод минимального тарифа B1 A1 1 B3 11 80 B4 3 13 4 8 2 30 130 3 A3 5 10 80 ai 60 12 A2 bj B2 14 6 90 40 150 140 160 100 130 27 2. Метод минимального тарифа B1 A1 1 B3 11 80 B4 ai 3 13 8 2 60 12 A2 4 30 130 3 A3 bj B2 5 10 80 Начальный опорный план: 14 6 90 40 150 140 160 100 130  80 0 60 0    X =  0 30 0 130   0 10 90 0    28 z(X) = 1·80 + 4·30 + 5·10 + 14·90 + 3·60 + 2·130 = 1950 < 2280 3. Метод Фогеля B1 B2 B3 B4 ai A1 1 11 3 13 140 A2 12 4 8 2 160 A3 bj 3 5 14 6 100 40 150 130 Разности по строкам 80 Разности по строкам 29 3. Метод Фогеля B1 B2 B3 B4 ai Разности по строкам 11 3 13 140 2 A2 12 4 8 2 160 2 A3 bj 3 5 14 6 100 2 Разности по строкам A1 1 80 40 150 130 2 1 5 4 30 3. Метод Фогеля B1 B2 B3 ai A1 1 A2 12 4 8 2 160 2 A3 bj 3 5 14 6 100 2 Разности по строкам 11 B4 Разности по строкам 3 13 140 2 140 80 40 150 130 2 1 5 4 31 3. Метод Фогеля B1 B2 B3 ai A1 1 A2 12 4 8 2 160 2 A3 bj 3 5 14 6 100 2 Разности по строкам 11 B4 Разности по строкам 3 13 140 2 140 80 40 150 130 2 1 5 4 - - - 32 3. Метод Фогеля B1 B2 B3 ai A1 1 A2 12 4 8 2 160 2 2 A3 bj 3 5 14 6 100 2 2 Разности по строкам 11 B4 Разности по строкам 3 13 140 2 - 140 80 40 150 130 2 1 5 4 9 1 6 4 - - 33 3. Метод Фогеля B1 B2 B3 ai A1 1 A2 12 4 8 2 160 2 2 A3 bj 3 5 14 6 100 2 2 Разности по строкам 11 B4 Разности по строкам 3 13 140 2 - 140 80 40 150 130 2 1 5 4 9 1 6 4 - - 34 3. Метод Фогеля B1 B2 B3 ai A1 1 A2 12 4 8 2 160 2 2 A3 bj 3 5 14 6 100 2 2 Разности по строкам 11 B4 Разности по строкам 3 13 140 2 - 140 80 80 40 150 130 2 1 5 4 9 1 6 4 - - 35 3. Метод Фогеля B1 B2 B3 ai A1 1 A2 12 4 8 2 160 2 2 A3 bj 3 5 14 6 100 2 2 Разности по строкам 11 B4 Разности по строкам 3 13 140 2 - 140 80 80 40 150 130 2 1 5 4 9 1 6 4 - - 36 3. Метод Фогеля B1 B2 B3 ai A1 1 A2 12 4 8 2 160 2 2 2 A3 bj 3 5 14 6 100 2 2 1 Разности по строкам 11 B4 Разности по строкам 3 13 140 2 - - 140 80 80 40 150 130 2 1 5 4 9 1 6 4 - 1 6 4 - 37 3. Метод Фогеля B1 B2 B3 ai A1 1 A2 12 4 8 2 160 2 2 2 A3 bj 3 5 14 6 100 2 2 1 Разности по строкам 11 B4 Разности по строкам 3 13 140 2 - - 140 80 80 40 150 130 2 1 5 4 9 1 6 4 - 1 6 4 - 38 3. Метод Фогеля B1 B2 A2 12 A3 bj 3 Разности по строкам A1 1 B3 11 B4 ai 3 13 140 2 - - 8 2 160 2 2 2 14 6 100 2 2 1 140 4 10 5 Разности по строкам 80 80 40 150 130 2 1 5 4 9 1 6 4 - 1 6 4 - 39 3. Метод Фогеля B1 B2 A2 12 A3 bj 3 Разности по строкам A1 1 B3 11 B4 ai 3 13 140 2 - - 8 2 160 2 2 2 14 6 100 2 2 1 140 4 10 5 80 80 40 150 130 2 1 5 4 9 1 6 4 - 1 6 4 - Разности по строкам - 40 3. Метод Фогеля B1 B2 A2 12 A3 bj 3 Разности по строкам A1 1 B3 11 B4 ai 3 13 140 2 - - - 8 2 160 2 2 2 2 14 6 100 2 2 1 1 140 4 10 5 Разности по строкам 80 80 40 150 130 2 1 5 4 9 1 6 4 - 1 6 4 - 1 - 4 41 3. Метод Фогеля B1 B2 A2 12 A3 bj 3 Разности по строкам A1 1 B3 11 B4 ai 3 13 140 2 - - - 8 2 160 2 2 2 2 6 100 2 2 1 1 140 4 10 130 5 Разности по строкам 14 80 80 40 150 130 2 1 5 4 9 1 6 4 - 1 6 4 - 1 - 4 42 3. Метод Фогеля B1 B2 A2 12 A3 bj 3 Разности по строкам A1 1 B3 11 B4 ai 3 13 140 2 - - - 8 2 160 2 2 2 2 6 100 2 2 1 1 140 4 10 130 5 Разности по строкам 14 80 80 40 150 130 2 1 5 4 9 1 6 4 - 1 6 4 - 1 - 4 43 3. Метод Фогеля B1 B2 A2 12 A3 bj 3 Разности по строкам A1 1 B3 11 B4 ai 3 13 140 2 - - - 8 2 160 2 2 2 2 6 100 2 2 1 1 140 4 20 10 130 5 Разности по строкам 14 80 80 40 150 130 2 1 5 4 9 1 6 4 - 1 6 4 - 1 - 4 44 3. Метод Фогеля B1 B2 A2 12 A3 bj 3 Разности по строкам A1 1 B3 11 B4 ai 3 13 140 2 - - - 8 2 160 2 2 2 2 6 100 2 2 1 1 140 4 20 80 10 130 5 Разности по строкам 14 20 80 40 150 130 2 1 5 4 9 1 6 4 - 1 6 4 - 1 - 4 45 3. Метод Фогеля B1 B2 A2 12 A3 bj 3 Разности по строкам A1 1 B3 11 B4 ai 3 13 140 2 - - - 8 2 160 2 2 2 2 6 100 2 2 1 1 140 4 20 80 10 130 5 Разности по строкам 14 20 80 40 150 130 2 1 5 4 Начальный опорный план: 𝑋 = 0 1 6 4 80 9 1 6 4 - 1 - 4 20 20 140 0 10 130 0 0 z(X) = 3·80 + 5·20 + 4·20 + 8·10 + 3·140 + 2·130 = 1180 < 1950 46 Решение транспортной задачи методом потенциалов  Теорема Если опорный план X = (xij) транспортной задачи является оптимальным, то существуют потенциалы поставщиков ui, i = 1,…, m и потребителей vj, j = 1,…, n, удовлетворяющие условиям: ui + vj = сij при xij > 0 (для занятых клеток), Δij = ui + vj - сij ≤ 0 при xij = 0 (для свободных клеток). 47 Метод потенциалов B1 1 A1 bj B3 B4 11 ai 3 13 8 2 140 12 A2 A3 B2 4 20 10 3 80 5 130 14 6 20 80 40 150 ui 140 160 100 130 vj 48 Метод потенциалов B1 1 A1 B3 B4 11 ai 3 13 8 2 140 12 A2 A3 B2 4 20 10 3 80 bj 5 130 14 6 20 80 40 150 ui 140 160 100 130 vj ui + vj = сij 49 Метод потенциалов B1 1 A1 B3 B4 11 ai 3 13 8 2 140 12 A2 A3 B2 4 20 10 3 80 bj vj ui + vj = сij 130 5 14 6 20 80 40 150 130 4 8 2 ui 140 160 100 50 Метод потенциалов B1 1 A1 B3 B4 11 ai 3 13 8 2 140 12 A2 A3 B2 4 20 10 3 80 bj vj ui + vj = сij 130 5 14 6 20 80 40 150 130 4 8 2 ui 140 160 100 1 51 Метод потенциалов B1 1 A1 B3 B4 11 ai 3 13 8 2 140 12 A2 A3 B2 4 20 10 3 80 130 5 14 6 20 bj 80 40 150 130 vj 2 4 8 2 ui + vj = сij ui 140 160 100 1 52 Метод потенциалов B1 1 A1 B3 B4 11 3 13 8 2 140 12 A2 A3 B2 4 20 10 3 80 130 5 14 6 20 bj 80 40 150 130 vj 2 4 8 2 ui + vj = сij ai ui 140 -5 160 100 1 53 Метод потенциалов B1 A1 1 B3 B4 11 3 13 8 2 140 -4 12 A2 A3 B2 4 20 10 3 80 130 5 14 6 20 bj 80 40 150 130 vj 2 4 8 2 Δij = ui + vj - сij ai ui 140 -5 160 100 1 54 Метод потенциалов B1 A1 1 -4 B3 3 13 8 2 140 - 12 4 20 10 3 80 B4 11 12 A2 A3 B2 130 5 14 6 20 bj 80 40 150 130 vj 2 4 8 2 Δij = ui + vj - сij ai ui 140 -5 160 100 1 55 Метод потенциалов B1 A1 1 -4 B3 3 140 - 12 8 10 3 13 - 16 4 20 80 B4 11 12 A2 A3 B2 2 130 5 14 6 20 bj 80 40 150 130 vj 2 4 8 2 Δij = ui + vj - сij ai ui 140 -5 160 100 1 56 Метод потенциалов B1 A1 A2 A3 B2 1 -4 B3 11 12 8 10 3 13 - 16 4 20 80 3 140 - 12 - 10 B4 2 130 5 14 6 20 bj 80 40 150 130 vj 2 4 8 2 Δij = ui + vj - сij ai ui 140 -5 160 100 1 57 Метод потенциалов B1 A1 A2 A3 B2 1 -4 B3 11 12 8 10 3 2 130 5 20 13 - 16 4 20 80 3 140 - 12 - 10 B4 14 6 -5 bj 80 40 150 130 vj 2 4 8 2 Δij = ui + vj - сij ai ui 140 -5 160 100 1 58 Метод потенциалов B1 A1 A2 A3 B2 1 -4 B3 11 12 8 10 3 2 130 5 20 13 - 16 4 20 80 3 140 - 12 - 10 B4 14 -5 6 -3 bj 80 40 150 130 vj 2 4 8 2 Δij = ui + vj - сij ai ui 140 -5 160 100 1 59 Метод потенциалов B1 A1 A2 A3 B2 1 -4 B3 11 3 140 - 12 12 B4 4 13 - 16 8 План 10 130 оптимален! 5 14 2 20 - 10 3 80 20 -5 -3 bj 80 40 150 130 vj 2 4 8 2 Δij = ui + vj - сij 6 ai ui 140 -5 160 100 1 60 Метод потенциалов B1 A1 A2 A3 B2 1 -4 11 3 4 20 - 10 3 13 - 16 8 10 5 20 B4 140 - 12 12 80 B3 2 130 14 -5 6 -3 ai ui 140 -5 160 100 1 40 150 0 130 140 0 Оптимальный план: 𝑋 ∗ = 0 20 10 130 2 4 8 20 2 0 0 80 vj bj 80 z(X*) = 3·80 + 5·20 + 4·20 + 8·10 + 3·140 + 2·130 = 1180 61 Алгоритм решения методом потенциалов 1. 2. Строим начальное опорное решение X Находим потенциалы ui и vj, соответствующие данному опорному решению, решая систему уравнений ui + vj = сij для занятых клеток 62 Алгоритм решения методом потенциалов 3. Вычисляем оценки для свободных клеток по формулам Δij = ui + vj – сij. Если Δij ≤ 0 для всех свободных клеток, то полученное решение является оптимальным X* = X Вычисляем значение целевой функции z(X*), и решение задачи заканчивается на данном шаге 63 Алгоритм решения методом потенциалов 4. Если имеется хотя бы одна свободная клетка с положительной оценкой, то опорное решение не является оптимальным Для улучшения плана перевозок находим клетку таблицы, которой соответствует наибольшая положительная оценка, и строим цикл, включающий данную свободную клетку и занятые клетки 64 Алгоритм решения методом потенциалов 5. В вершинах цикла расставляем поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой Делаем переход по циклу на величину, равную минимуму перевозок по всем клеткам со знаком «-» Получаем новый переходим к пункту 2 опорный план, 65 Открытая модель транспортной задачи  Модель транспортной задачи называется m n открытой, если ∑ a ≠ ∑ b (суммарные i =1 i j =1 j запасы не равны суммарным потребностям) 66 Открытая модель транспортной задачи Открытую модель можно свести к закрытой: m n i =1 j =1 1. Если ∑ ai > ∑ b j , то вводят фиктивного m n i =1 j =1 потребителя Вn+1 с потребностью bn+1 = ∑ ai − ∑ b j и нулевыми тарифами перевозок в столбце m n ai < ∑ b j ,то вводят фиктивного 2. Если ∑ i =1 j =1 поставщика А m+1 с запасом n m j =1 i =1 am+1 = ∑ b j − ∑ ai и нулевыми тарифами перевозок в строке 67 Задача 2 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную стоимость всех перевозок. B1 B2 B3 B4 ai A1 3 7 4 7 100 A2 10 13 24 7 100 A3 bj 8 19 12 18 200 90 80 30 170 68 Задача 2 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную стоимость всех перевозок. B1 B2 B3 B4 ai A1 3 7 4 7 100 A2 10 13 24 7 100 A3 bj 8 19 12 18 200 90 80 30 170 m i =1 370 n ∑a > ∑b i j =1 400 j 69 Метод минимального тарифа B1 B4 B5 ai 7 4 7 10 13 24 7 8 19 12 18 A3 bj B3 3 A1 A2 B2 90 80 30 170 100 100 200 30 70 Метод минимального тарифа B1 A1 A2 B3 B4 B5 ai 3 7 4 7 10 13 24 7 8 19 12 18 90 A3 bj B2 90 80 30 170 100 100 200 30 71 Метод минимального тарифа B1 A1 A2 B3 B4 B5 ai 3 7 4 7 10 13 24 7 8 19 12 18 90 A3 bj B2 90 80 30 170 100 100 200 30 72 Метод минимального тарифа B1 A1 A2 3 B3 7 90 B4 B5 ai 4 7 10 10 13 24 7 8 19 12 18 A3 bj B2 90 80 30 170 100 100 200 30 73 Метод минимального тарифа B1 A1 A2 3 B3 7 90 B4 B5 ai 4 7 10 10 13 24 7 8 19 12 18 A3 bj B2 90 80 30 170 100 100 200 30 74 Метод минимального тарифа B1 A1 A2 3 B3 7 90 B4 B5 ai 4 7 24 7 18 10 10 13 100 8 A3 bj B2 90 19 80 12 30 170 100 100 200 30 75 Метод минимального тарифа B1 A1 A2 3 B3 7 90 B4 B5 ai 4 7 24 7 18 10 10 13 100 8 A3 bj B2 90 19 80 12 30 170 100 100 200 30 76 Метод минимального тарифа B1 A1 A2 3 B3 7 90 B4 B5 ai 4 7 24 7 18 10 10 13 100 8 A3 bj B2 19 12 20 90 80 30 170 100 100 200 30 77 Метод минимального тарифа B1 A1 A2 3 B3 7 90 B4 B5 ai 4 7 24 7 18 10 10 13 100 8 A3 bj B2 19 12 20 90 80 30 170 100 100 200 30 78 Метод минимального тарифа B1 A1 A2 3 B3 7 90 B4 B5 ai 4 7 24 7 18 10 10 13 100 8 A3 bj B2 19 12 20 90 80 30 70 170 100 100 200 30 79 Метод минимального тарифа B1 A1 A2 3 B3 7 90 B4 B5 ai 4 7 24 7 18 10 10 13 100 8 A3 bj B2 19 12 20 90 80 30 70 170 100 100 200 30 80 Метод минимального тарифа B1 A1 A2 3 B3 7 90 B4 B5 ai 4 7 24 7 18 10 10 13 100 8 A3 bj B2 19 80 90 80 12 20 30 70 170 100 100 200 30 81 Метод минимального тарифа B1 A1 A2 3 B3 7 90 B4 B5 ai 4 7 24 7 18 10 10 13 100 8 A3 bj B2 19 80 90 80 12 20 30 70 170 100 100 200 30 82 Метод минимального тарифа B1 A1 A2 3 B3 7 90 B4 B5 ai 4 7 24 7 18 10 10 13 100 8 A3 bj B2 19 80 90 80 12 20 30 70 170 30 30 100 100 200 Метод минимального тарифа B1 A1 A2 3 B3 7 90 B4 B5 ai 4 7 24 7 18 10 10 13 100 8 A3 bj B2 19 80 90 80 12 20 30 Начальный опорный план: 70 30 170 90 0 𝑋= 0 0 80 100 100 200 30 10 0 0 0 100 0 20 70 30 z(X) = 3·90 + 19·80 + 12·20 + 4·10 + 7·100 + 18·70 + 0·30 = 4030 84 Метод потенциалов B1 A1 A2 3 B3 7 90 B4 B5 ai 4 7 24 7 18 10 10 13 100 8 A3 bj B2 19 80 90 80 12 20 30 70 170 30 ui 100 100 200 30 vj 85 Метод потенциалов B1 A1 A2 3 B3 7 90 B4 B5 ai 4 7 24 7 18 10 10 13 100 8 A3 bj B2 19 80 90 80 12 20 30 70 170 30 ui 100 100 200 30 vj 86 Метод потенциалов B1 A1 A2 3 vj B3 7 90 B4 B5 ai 4 7 24 7 18 10 10 13 100 8 A3 bj B2 19 80 90 12 20 70 30 80 30 170 30 19 12 18 ui 100 100 200 87 Метод потенциалов B1 A1 A2 3 vj B3 7 90 B4 B5 ai 4 7 24 7 18 10 10 13 100 8 A3 bj B2 19 80 90 12 20 70 30 80 30 170 30 19 12 18 ui 100 100 - 11 200 88 Метод потенциалов B1 A1 A2 3 vj B3 7 90 B4 B5 4 7 24 7 18 10 10 13 100 8 A3 bj B2 19 80 90 12 20 70 30 80 30 170 30 19 12 18 ai ui 100 -8 100 - 11 200 89 Метод потенциалов B1 A1 A2 B2 3 B3 7 90 B4 B5 4 7 24 7 18 10 10 13 100 8 A3 19 80 12 20 70 30 bj 90 80 30 170 30 vj 11 19 12 18 ai ui 100 -8 100 - 11 200 90 Метод потенциалов B1 A1 A2 B2 3 90 B3 7 4 10 4 10 - 10 13 7 -8 24 19 B5 3 7 100 -23 -5 8 B4 12 - 11 18 A3 3 bj 90 80 30 170 30 vj 11 19 12 18 80 20 70 30 ai ui 100 -8 100 - 11 200 91 Улучшение опорного плана транспортной задачи Цикл – последовательность клеток таблицы транспортно задачи, в которой две и только две соседние клетки расположены в одной строке или одном столбце  Цикл изображается в виде замкнутой ломанной линии, соединяющей вершины цикла, расположенные в клетках таблицы  92 Улучшение опорного плана транспортной задачи  Для построения нового опорного плана в таблице выбирается свободная клетка с максимальной положительно оценкой и формируется цикл, одной из вершин которого является выбранная клетка, остальные клетки занятые 93 Метод потенциалов B1 A1 A2 B2 3 90 B3 7 4 10 4 10 - 10 13 7 -8 24 19 B5 3 7 100 -23 -5 8 B4 12 - 11 18 A3 3 bj 90 80 30 170 30 vj 11 19 12 18 80 20 70 30 ai ui 100 -8 100 - 11 200 94 Метод потенциалов B1 A1 A2 B2 3 90 B3 7 4 10 4 10 - 10 13 7 -8 24 19 B5 3 7 100 -23 -5 8 B4 12 - 11 18 A3 3 bj 90 80 30 170 30 vj 11 19 12 18 80 20 70 30 ai ui 100 -8 100 - 11 200 95 Цикл 10 80 + - - + 20 10 70 + - - + 30 Δ = min (80, 10) = 10 96 Метод потенциалов B1 A1 A2 3 90 B3 B4 B5 ai 7 4 7 13 24 7 18 10 10 100 8 A3 bj B2 19 70 90 80 12 30 30 70 170 30 ui 100 100 200 30 vj 97 Метод потенциалов B1 A1 A2 B2 3 90 B3 B4 B5 ai 7 4 7 13 24 7 18 10 10 100 8 A3 19 70 12 30 70 30 bj 90 80 30 170 30 vj 15 19 12 18 ui 100 - 12 100 - 11 200 98 Метод потенциалов B1 A1 A2 B2 3 90 B3 7 10 10 -6 4 -4 13 -5 8 B4 B5 7 -1 - 12 ui 100 - 12 24 7 100 - 11 100 - 23 - 11 19 12 18 A3 7 bj 90 80 30 170 30 vj 15 19 12 18 70 ai 30 70 30 200 99 Метод потенциалов B1 A1 A2 B2 3 90 B3 7 10 10 -6 4 -4 13 -5 8 B4 B5 7 -1 - 12 ui 100 - 12 24 7 100 - 11 100 - 23 - 11 19 12 18 A3 7 bj 90 80 30 170 30 vj 15 19 12 18 70 ai 30 70 30 200 z(X) = 3·90 + 7·10 + 19·70 + 12·30 + 18·70 + 7·100 = 3990 < 4030 100 Метод потенциалов B1 A1 A2 B2 3 90 B3 7 10 10 -6 4 -4 13 -5 8 B4 B5 7 -1 - 12 ui 100 - 12 24 7 100 - 11 100 - 23 - 11 19 12 18 A3 7 bj 90 80 30 170 30 vj 15 19 12 18 70 ai 30 70 30 200 z(X) = 3·90 + 7·10 + 19·70 + 12·30 + 18·70 + 7·100 = 3990 < 4030 101 Метод потенциалов B1 A1 A2 B2 3 90 B3 7 10 10 -6 4 -4 13 -5 8 B4 B5 7 -1 - 12 ui 100 - 12 24 7 100 - 11 100 - 23 - 11 19 12 18 A3 7 bj 90 80 30 170 30 vj 15 19 12 18 70 ai 30 70 30 200 z(X) = 3·90 + 7·10 + 19·70 + 12·30 + 18·70 + 7·100 = 3990 < 4030 102 Цикл 90 - + + - 10 70 20 70 80 - + + - Δ = min (90, 70) = 70 103 Метод потенциалов B1 A1 3 20 bj B3 B4 B5 ai 7 4 7 13 24 7 18 80 10 A2 A3 B2 100 8 19 70 90 12 30 80 30 70 170 30 ui 100 100 200 30 vj 104 Метод потенциалов B1 A1 3 20 B3 B4 B5 7 4 7 13 24 7 18 80 10 A2 A3 B2 100 8 19 70 12 30 70 30 bj 90 80 30 170 30 vj 8 12 12 18 ai ui 100 -5 100 - 11 200 105 Метод потенциалов B1 A1 A2 A3 B2 3 20 B3 7 80 10 - 13 4 3 B5 7 6 -5 ai ui 100 -5 13 24 7 100 - 11 100 - 12 - 23 - 11 8 70 B4 19 -7 12 30 18 70 30 bj 90 80 30 170 30 vj 8 12 12 18 200 z(X) = 3·20 + 7·80 + 8·70 + 12·30 + 18·70 + 7·100 = 3500 < 3990 106 Метод потенциалов B1 A1 A2 A3 B2 3 20 B3 7 80 10 - 13 4 3 B5 7 6 -5 ai ui 100 -5 13 24 7 100 - 11 100 - 12 - 23 - 11 8 70 B4 19 -7 12 30 18 70 30 bj 90 80 30 170 30 vj 8 12 12 18 200 z(X) = 3·20 + 7·80 + 8·70 + 12·30 + 18·70 + 7·100 = 3500 < 3990 107 Новый опорный план B1 3 A1 20 A2 B2 B3 7 80 10 - 13 4 3 B5 7 6 -5 ai ui 100 -5 13 24 7 100 -11 100 - 12 - 23 - 11 8 A3 70 B4 19 -7 12 30 18 70 30 bj 90 80 30 170 30 vj 8 12 12 18 200 z(X) = 3·20 + 7·80 + 8·70 + 12·30 + 18·70 + 7·100 = 3500 < 4130 108 Цикл 20 20 70 - + - + + - + - 70 90 50 Δ = min (20, 70) = 20 109 Метод потенциалов B1 3 A1 bj B3 7 B4 4 80 10 A2 A3 B2 B5 ai 7 7 18 20 13 24 100 8 19 90 90 12 30 80 30 50 170 30 ui 100 100 200 30 vj 110 Метод потенциалов B1 3 A1 B3 7 B4 4 80 10 A2 A3 B2 B5 ai 7 7 18 20 13 24 100 8 19 90 12 30 50 30 bj 90 80 30 170 30 vj 8 18 12 18 ui 100 -11 100 -11 200 111 Метод потенциалов B1 B2 3 A1 -6 A2 10 - 13 A3 7 80 8 90 B3 13 -6 B4 4 -3 B5 7 20 24 7 - 23 100 ai - 11 - 11 19 12 18 50 30 - 1 30 bj 90 80 30 170 30 vj 8 18 12 18 ui 100 -11 100 -11 200 112 Метод потенциалов B1 B2 3 A1 -6 A2 10 - 13 A3 7 80 8 90 B3 4 -3 13 -6 B4 B5 7 20 ai - 11 24 7 - 23 100 План - 11 оптимален! 19 12 18 -1 30 50 30 bj 90 80 30 170 30 vj 8 18 12 18 ui 100 -11 100 -11 200 113 Метод потенциалов B1 B2 3 A1 -6 A2 10 - 13 A3 bj vj 90 7 13 -6 -3 B5 7 20 24 7 - 23 100 80 30 18 12 ai - 11 - 11 19 12 18 50 30 - 1 30 Оптимальный план: 8 B4 4 80 8 90 B3 ui 100 -11 100 -11 200 170 0 80 30 0 20    X =  0 0 0 100  18 90 0 030 50  z(X) = 8·90 + 7·80 + 12·30 + 7·100 + 7·20 + 18·50 = 3380 < 3500 114 Задача 3 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную стоимость всех перевозок B1 B2 B3 B4 ai A1 1 13 12 3 60 A2 2 16 4 6 125 A3 bj 13 4 17 16 75 100 100 50 50 115 Задача 3 Решите транспортную задачу методом потенциалов. В ответе укажите минимальную стоимость всех перевозок B1 B2 B3 B4 ai A1 1 13 12 3 60 A2 2 16 4 6 125 A3 bj 13 4 17 16 75 100 100 50 50 m i =1 300 n ∑a < ∑b i j =1 260 j 116 Метод минимального тарифа B1 A1 A2 A3 A4 bj 100 B2 B3 B4 ai 1 13 12 3 2 16 4 6 13 4 17 16 100 50 60 125 75 40 50 117 Метод минимального тарифа B1 A1 A2 A3 A4 bj B2 B3 B4 1 13 12 3 2 16 4 6 13 4 17 16 40 100 ai 100 50 60 125 75 40 50 118 Метод минимального тарифа B1 A1 B3 B4 ai 1 13 12 3 2 16 4 6 13 4 17 16 60 A2 A3 A4 bj B2 40 100 100 50 60 125 75 40 50 119 Метод минимального тарифа B1 A1 B3 B4 ai 1 13 12 3 2 16 4 6 13 4 17 16 60 A2 A3 A4 bj B2 40 100 100 50 60 125 75 40 50 120 Метод минимального тарифа B1 A1 A2 B3 B4 ai 1 13 12 3 2 16 4 6 13 4 17 16 60 40 A3 A4 bj B2 40 100 100 50 60 125 75 40 50 121 Метод минимального тарифа B1 A1 A2 B3 B4 ai 1 13 12 3 2 16 4 6 13 4 17 16 60 40 A3 A4 bj B2 40 100 100 50 60 125 75 40 50 122 Метод минимального тарифа B1 A1 A2 B3 B4 ai 1 13 12 3 2 16 4 6 13 4 17 16 60 40 A3 75 A4 bj B2 40 100 100 50 60 125 75 40 50 123 Метод минимального тарифа B1 A1 A2 B3 B4 ai 1 13 12 3 2 16 4 6 13 4 17 16 60 40 A3 75 A4 bj B2 40 100 100 50 60 125 75 40 50 124 Метод минимального тарифа B1 A1 A2 B3 B4 ai 1 13 12 3 2 16 4 6 4 17 16 60 40 50 13 A3 75 A4 bj B2 40 100 100 50 60 125 75 40 50 125 Метод минимального тарифа B1 A1 A2 B3 B4 ai 1 13 12 3 2 16 4 6 4 17 16 60 40 50 13 A3 75 A4 bj B2 40 100 100 50 60 125 75 40 50 126 Метод минимального тарифа B1 A1 A2 B3 B4 ai 1 13 12 3 2 16 4 6 60 40 50 13 A3 10 4 17 16 75 A4 bj B2 40 100 100 50 60 125 75 40 50 127 Метод минимального тарифа B1 A1 A2 B3 B4 ai 1 13 12 3 2 16 4 6 60 40 50 13 A3 10 4 17 16 75 A4 bj B2 40 100 100 50 60 125 75 40 50 128 Метод минимального тарифа B1 A1 A2 B3 B4 ai 1 13 12 3 2 16 4 6 60 40 25 50 13 A3 10 4 17 16 75 A4 bj B2 40 100 100 50 60 125 75 40 50 z(X) = 1·60 + 2·40 + 16·25+ 4·75 + 4·50 + 6·10 = 1100 129 Метод потенциалов B1 A1 A2 A3 B3 B4 ai 1 13 12 3 2 16 4 6 60 40 25 13 50 10 4 17 16 75 A4 bj B2 40 100 100 50 ui 60 125 75 40 50 vj 130 Метод потенциалов B1 A1 A2 A3 B2 1 60 B3 13 2 2 40 B4 12 -9 16 25 3 2 4 50 6 10 13 - 23 75 4 17 - 25 16 - 22 A4 -4 10 bj 100 100 50 50 vj 2 16 4 6 -2 40 ai ui 60 -1 125 75 -12 40 -6 131 Метод потенциалов B1 A1 A2 A3 B2 1 60 B3 13 2 2 40 B4 12 -9 16 25 3 2 4 50 6 10 13 - 23 75 4 17 - 25 16 - 22 A4 -4 10 bj 100 100 50 50 vj 2 16 4 6 -2 40 ai ui 60 -1 125 75 -12 40 -6 132 Метод потенциалов B1 A1 A2 A3 B2 1 60 B3 13 2 2 40 B4 12 -9 16 25 3 2 4 50 6 10 13 - 23 75 4 17 - 25 16 - 22 A4 -4 10 bj 100 100 50 50 vj 2 16 4 6 -2 40 ai ui 60 -1 125 75 -12 40 -6 133 Цикл 25 35 10 - + - + + - + - 40 25 15 Δ = min (25, 40) = 25 134 Новый опорный план B1 A1 A2 A3 B3 B4 ai 1 13 12 3 2 16 4 6 60 40 50 13 35 4 17 16 75 A4 bj B2 25 100 100 15 50 ui 60 125 75 40 50 vj 135 Новый опорный план B1 A1 A2 A3 B2 1 60 B3 13 -8 2 40 B4 12 -9 16 2 4 50 - 10 3 6 35 13 - 13 75 4 17 - 15 16 - 12 A4 -4 bj 100 100 50 50 vj 2 6 4 6 -2 25 15 ai ui 60 -1 125 75 -2 40 -6 z(X) = 1·60 + 2·40 + 4·75 + 4·50 + 6·35 = 850 < 1100 136 Новый опорный план B1 A1 A2 A3 B2 1 60 B3 13 -8 2 40 B4 12 -9 16 2 4 50 - 10 3 6 35 13 - 13 75 4 17 - 15 16 - 12 A4 -4 bj 100 100 50 50 vj 2 6 4 6 -2 25 15 ai ui 60 -1 125 75 -2 40 -6 z(X) = 1·60 + 2·40 + 4·75 + 4·50 + 6·35 = 850 < 1100 137 Новый опорный план B1 A1 A2 A3 B2 1 60 B3 13 -8 2 40 B4 12 -9 16 2 4 50 - 10 3 6 35 13 - 13 75 4 17 - 15 16 - 12 A4 -4 bj 100 100 50 50 vj 2 6 4 6 -2 25 15 ai ui 60 -1 125 75 -2 40 -6 z(X) = 1·60 + 2·40 + 4·75 + 4·50 + 6·35 = 850 < 1100 138 Цикл 25 60 40 35 - + - + + - + - 35 75 Δ = min (35, 60) = 35 139 Новый опорный план B1 A1 A2 A3 1 B3 13 B4 12 25 ai 3 35 2 16 4 6 4 17 16 75 50 13 75 A4 bj B2 25 100 100 15 50 ui 60 125 75 40 50 vj 140 Новый опорный план B1 A1 A2 A3 B2 1 25 B3 13 - 10 B4 12 3 35 -9 План 50 - 12 -2 оптимален! 13 4 17 16 2 75 16 75 - 11 4 - 13 6 - 12 A4 -2 bj 100 100 50 50 vj 1 3 3 3 25 15 ai ui 60 125 1 75 1 40 -3 141 Новый опорный план B1 A1 A2 A3 A4 B2 1 25 B3 13 - 10 2 75 B4 12 35 -9 16 4 50 - 12 3 6 -2 13 - 11 75 4 17 - 13 16 - 12 -2 25 100 100 bОптимальный j план: 50 vj 3 1 3 15 ai ui 60 125 1 75 1 40 -3 0 0 35   25 50   X =  75 0 50 0   0 3 75 0 0    z(X) = 1·25 + 2·75 + 4·75 + 4·50 + 3·35 = 780 < 850 142 Транспортные задачи с дополнительными ограничениями В некоторых транспортных задачах наложены дополнительные ограничения на перевозку грузов. 1. Если в закрытой задаче перевозки от поставщика Ai к потребителю Bj не могут быть осуществлены (стоит блокировка), для определения оптимального решения задач предполагают, что тариф перевозки единицы груза равен сколь угодно большому числу М.  143 Транспортные задачи с дополнительными ограничениями 2. Если дополнительным условием в задаче является обеспечение перевозки от поставщика Ai к потребителю Bj в точности aij единиц груза, в клетку AiBj записывают указанное число aij, а эту клетку считают свободной со сколь угодно большим тарифом М. 144 Транспортные задачи с дополнительными ограничениями 3. Если от поставщика Ai к потребителю Bj должно быть перевезено не менее aij единиц груза, то запасы пункта Ai и потребности Bj полагают меньше фактических на aij единиц. После нахождения оптимального плана перевозку в клетке AiBj увеличивают на aij единиц. 145 Транспортные задачи с дополнительными ограничениями 4. Если от поставщика Ai к потребителю Bj требуется перевезти не более aij единиц груза, то вводят дополнительного потребителя Bn+1 = Bij, которому записывают те же тарифы, что и для Bj, за исключением тарифа в i–й строке, который считают равным сколь угодно большому числу М. Потребности пункта Bj считают равными aij, а потребности Bij полагают равными bj - aij. 146 Задача 4 Найти решение транспортной задачи, если из А1 в В4 должно быть перевезено не менее 40 ед. груза, из А2 в В3 должно быть перевезено не более 50 ед. груза, а из А3 в В1 не менее 60 ед. груза. B1 B2 B3 B4 ai A1 12 14 11 20 90 A2 3 4 5 9 155 A3 bj 2 18 14 12 125 100 75 75 120 147 Задача 4 Найти решение транспортной задачи, если из А1 в В4 должно быть перевезено не менее 40 ед. груза, из А2 в В3 должно быть перевезено не более 50 ед. груза, а из А3 в В1 не менее 60 ед. груза. B1 B2 B3 B4 ai A1 12 14 11 20 90 A2 3 4 5 9 155 A3 bj 2 18 14 12 125 100 75 75 120 370 370 370 148 Метод наименьшего тарифа Найти решение транспортной задачи, если из А1 в В4 должно быть перевезено не менее 40 ед. груза, из А2 в В3 должно быть перевезено не более 50 ед. груза, а из А3 в В1 не менее 60 ед. груза. B1 B2 B3 B4 B5 A1 12 14 11 20 11 A2 3 4 5 9 M A3 2 18 14 12 14 bj 40 75 50 80 ai 50 155 65 25 149 Метод наименьшего тарифа B1 B2 B3 B4 B5 A1 12 14 11 20 11 A2 3 4 5 9 M A3 2 18 14 12 14 bj 40 40 75 50 80 ai 50 155 65 25 150 Метод наименьшего тарифа B1 B2 B3 B4 B5 A1 12 14 11 20 11 A2 3 4 5 9 M A3 2 18 14 12 14 bj 40 40 75 50 80 ai 50 155 65 25 151 Метод наименьшего тарифа B1 B2 B3 B4 B5 A1 12 14 11 20 11 A2 3 4 5 9 M A3 2 18 14 12 14 bj 75 40 40 75 50 80 ai 50 155 65 25 152 Метод наименьшего тарифа B1 B2 B3 B4 B5 A1 12 14 11 20 11 A2 3 4 5 9 M A3 2 18 14 12 14 bj 75 40 40 75 50 80 ai 50 155 65 25 153 Метод наименьшего тарифа B1 B2 B3 B4 B5 A1 12 14 11 20 11 A2 3 4 5 9 M A3 2 14 12 14 bj 75 50 18 40 40 75 50 80 ai 50 155 65 25 154 Метод наименьшего тарифа B1 B2 B3 B4 B5 A1 12 14 11 20 11 A2 3 4 5 9 M A3 2 14 12 14 bj 75 50 18 40 40 75 50 80 ai 50 155 65 25 155 Метод наименьшего тарифа B1 B2 B3 B4 B5 A1 12 14 11 20 11 A2 3 4 5 9 M A3 2 12 14 bj 75 50 30 18 14 40 40 75 50 80 ai 50 155 65 25 156 Метод наименьшего тарифа B1 B2 B3 B4 B5 A1 12 14 11 20 11 A2 3 4 5 9 M A3 2 12 14 bj 75 50 30 18 14 40 40 75 50 80 ai 50 155 65 25 157 Метод наименьшего тарифа B1 B2 A1 12 A2 3 A3 2 bj B3 14 B4 11 B5 20 11 25 4 75 5 50 9 M 12 14 30 18 14 40 40 75 50 80 ai 50 155 65 25 158 Метод наименьшего тарифа B1 B2 A1 12 A2 3 A3 2 bj B3 14 B4 11 B5 20 11 25 4 75 5 50 9 M 12 14 30 18 14 40 40 75 50 80 ai 50 155 65 25 159 Метод наименьшего тарифа B1 B2 A1 12 A2 3 A3 2 bj B3 14 B4 11 B5 20 11 25 4 75 5 50 9 M 12 14 30 18 14 40 25 40 75 50 80 ai 50 155 65 25 160 Метод наименьшего тарифа B1 B2 A1 12 A2 3 A3 2 bj B3 14 B4 11 B5 20 11 25 4 75 5 50 9 M 12 14 30 18 14 40 25 40 75 50 80 ai 50 155 65 25 161 Метод наименьшего тарифа B1 B2 A1 12 A2 3 A3 2 bj B3 14 B4 11 B5 20 25 4 75 25 5 50 11 9 M 12 14 30 18 14 40 25 40 75 50 80 ai 50 155 65 25 162 Метод потенциалов B1 B2 A1 12 A2 3 A3 2 B3 14 B4 11 B5 20 25 4 75 25 5 50 11 9 M 12 14 30 18 14 40 25 bj 40 75 50 80 25 vj -1 4 5 9 ai ui 50 11 155 65 3 163 Метод потенциалов B1 A1 A2 A3 B2 12 -2 14 1 3 -4 B4 11 B5 4 9 30 18 - 11 -6 ui 50 11 M 155 -M 14 14 - 11 3 11 25 5 50 ai 20 25 5 75 2 40 B3 12 25 bj 40 75 50 80 25 vj -1 4 5 9 65 164 Метод потенциалов B1 A1 A2 A3 B2 12 -2 14 1 3 -4 B4 11 B5 4 9 30 18 - 11 -6 ui 50 11 M 155 -M 14 14 - 11 3 11 25 5 50 ai 20 25 5 75 2 40 B3 12 25 bj 40 75 50 80 25 vj -1 4 5 9 65 165 Метод потенциалов B1 A1 A2 A3 B2 12 -2 14 1 3 -4 B4 11 B5 4 9 30 18 - 11 -6 ui 50 11 M 155 -M 14 14 - 11 3 11 25 5 50 ai 20 25 5 75 2 40 B3 12 25 bj 40 75 50 80 25 vj -1 4 5 9 65 166 Цикл 25 50 + - - + 30 25 25 + - - + 55 Δ = min (50, 25) = 25 167 Метод потенциалов B1 B2 A1 12 A2 3 A3 2 bj B3 14 B4 11 B5 20 25 25 4 75 5 25 18 9 M 12 14 55 14 40 40 11 25 75 50 80 ai ui 50 155 65 25 vj 168 Метод потенциалов B1 B2 A1 12 A2 3 A3 2 B3 14 B4 11 B5 20 25 25 4 75 11 5 25 9 M 12 14 55 18 14 40 25 bj 40 75 50 80 25 vj -1 4 5 9 5 ai ui 50 6 155 65 3 169 Метод потенциалов B1 B2 12 B3 14 B4 B5 11 ai 20 11 50 A1 - 7 25 -4 - 5 25 3 4 5 9 M 155 A2 - 4 75 5-M 25 55 2 18 14 12 14 65 A3 40 25 - 11 -6 -6 bj 40 75 50 80 25 vj -1 4 5 9 5 ui 6 3 170 Метод потенциалов B1 B2 12 B3 14 B4 B5 11 ai 20 11 50 A1 - 7 25 -4 - 5 25 3 4 5 9 M 155 A2 - 4 75 5-M 25 55 2 18 14 12 14 65 A3 40 25 - 11 -6 -6 План оптимален! bj 40 75 50 80 25 vj -1 4 5 9 5 ui 6 3 171 Метод потенциалов B1 B2 12 B3 B5 ai 20 11 50 A1 - 7 25 -4 - 5 25 3 4 5 9 M 155 A2 - 4 75 5-M 25 55 2 18 14 12 14 65 A3 40 25 - 11 -6 -6 bj vj 40 -1 14 B4 75 4 11 50 Оптимальный план: 5 80 ui 6 3 25 0 50 40   0   9 5 X =  0 75 25 55  100 0 0 25   z(X) = 2·100 + 4·75 + 11·50 + 5·25 + 9·55 + 20·40 + 12·25 = 2770172 Финансовый университет при Правительстве РФ Департамент анализа данных, принятия решений и финансовых технологий Методы оптимальных решений Лекция № 4: «Взаимно-двойственные задачи» Минкова Анастасия Сергеевна План лекции Постановка взаимно-двойственных задач линейного программирования  Основная теорема двойственности  Нахождение двойственной задачи  Постановка задачи целочисленного программирования  Графический метод  Метод Гомори  2 Двойственная задача Исходная задача линейного программирования называется прямой  Каждой задаче линейного программирования можно определенным образом поставить в соответствие двойственную задачу (по отношению к исходной)  Эти две задачи тесно связаны между собой и образуют единую пару двойственных задач  3 Характеристики двойственных задач В одной задаче ищется максимум целевой функции, в другой – минимум  Коэффициенты при переменных целевой функции одной из задач являются свободными членами системы ограничений другой задачи  В задаче на максимум целевой функции все неравенства системы ограничений имеют знак «≤», а в задаче на минимум – знак «≥»  4 Характеристики двойственных задач    Каждому из m ограничений прямой задачи соответствует переменная двойственной задачи Каждому из n переменных прямой задачи соответствует ограничение двойственной задачи Матрица числовых коэффициентов при переменных системы ограничений одной задачи транспонирована по отношению к матрице числовых коэффициентов при переменных системы ограничений другой задачи 5 Математические модели симметричных двойственных задач 6 Алгоритм составления двойственной задачи 1. 2. Строим расширенную матрицу по заданным ограничениям и целевой функции исходной задачи Если в исходной задаче ищется максимум (минимум) линейной функции, то двойственная задача будет задачей на минимум (максимум) 7 Алгоритм составления двойственной задачи 3. 4. Найти матрицу А1т, транспонированную к матрице А1 Строка тривиальных ограничений переходит в столбец нетривиальных ограничений без изменения знака неравенства (соответственно с изменением знака) 8 Алгоритм составления двойственной задачи 5. 6. Если на переменную в исходной задаче тривиальное ограничение отсутствует, то соответствующее ограничение в двойственной задаче будет типа уравнения («~» переходит в «=») Столбец нетривиальных ограничений переходит в строку тривиальных ограничений с изменением знака неравенства (соответственно без изменения знака), а «=» переходит в «~» 9 Алгоритм составления двойственной задачи 7. Сформулировать двойственную задачу на основании полученной матрицы А1т и условия неотрицательности переменных 10 Задача 1 Составить задачу, следующей задаче: двойственную F = − x1 + 2 x2 → max 2 x1 − x2 ≥ 1  − x1 + 4 x2 ≤ 24   x1 − x2 ≤ 3 x + x ≥ 5  1 2  x j ≥ 0, j = 1,2 11 Решение Поскольку исходная задача на максимум, приведем все неравенства системы ограничений к виду «≤» Первое и четвертое неравенства умножим на -1 1. − 2 x1 + x2 ≤ −1 − x + 4 x ≤ 24  1 2   x1 − x2 ≤ 3 − x1 − x2 ≤ −5 12 Решение 2. 3. Составим системы расширенную матрицу  − 2 1 −1    − 1 4 24  A1 =  1 − 1 3     −1 −1 − 5  −1 2 F    Найдем матрицу А1т, транспонированную к матрице А1  − 2 − 1 1 − 1 − 1   Т A1 =  1 4 −1 −1 2   − 1 24 3 − 5 Z    13 Решение  − 2 − 1 1 − 1 − 1   Т A1 =  1 4 −1 −1 2   − 1 24 3 − 5 Z    4. Сформулируем двойственную задачу Z = − y1 + 24 y2 + 3 y3 − 5 y4 → min 2 y1 − y2 + y3 − y4 ≥ −1   y1 + 4 y2 − y3 − y4 ≥ 2  y ≥ 0, k = 1,2,3,4  k 14 Первая теорема двойственности  Основное неравенство теории двойственности Пусть имеется пара двойственных задач I и II. Для любых допустимых решений X = (x1, x2,…, xn) и Y = (y1, y2,…, ym) исходной и двойственной задач справедливо неравенство n m F ( X ) ≤ Z (Y ) или ∑ с j x j ≤ ∑ bi yi j =1 i =1 15 Достаточный признак оптимальности  Теорема Если X*=(x1*,x2*,…,xn*) и Y*=(y1*,y2*,…,ym*) – допустимые решения взаимно двойственных задач, для которых выполняется равенство F ( X * ) = Z (Y * ) , то X* – оптимальное решение исходной задачи I, а Y* – двойственной задачи II 16 Первая теорема двойственности  Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных функций равны: Fmax = Z min или F ( X * ) = Z (Y * )  Если линейная функция одной из задач не ограничена, то условия другой задачи противоречивы 17 Первая теорема двойственности Экономический смысл теоремы  План производства X*=(x1*,x2*,…,xn*) и набор цен (оценок) ресурсов Y*=(y1*,y2*,…,ym*) оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при «внешних» (заранее известных) ценах c1,c2,…,cn , равна затратам на ресурсы по «внутренним» (определяемым из решения задачи) ценах y1, y2,…,ym  18 Первая теорема двойственности Экономический смысл теоремы  Предприятию безразлично, производить ли продукцию по оптимальному плану X*=(x1*,x2*,…,xn*) и получить максимальную прибыль (выручку) Fmax, либо продать ресурсы по оптимальным ценам Y*=(y1*, y2*,…,ym*) и возместить от продажи равные ей минимальные затраты на ресурсы Zmin  19 Вторая теорема двойственности (теорема равновесия)  Оптимальные решения X * = ( x1* , x2* ,..., xn* ) и Y * = ( y1* , y2* ,..., ym* ) пары двойственных задач связаны между собой равенствами:  m  * *  ∑ aik yi − ck  ⋅ xk = 0, k = 1,2,..., n   i =1  n  a x* − b  ⋅ y * = 0, i = 1,2,..., m ik k i i  ∑   k =1 20 Финансовый университет при Правительстве РФ Департамент анализа данных, принятия решений и финансовых технологий Методы оптимальных решений Задачи целочисленного программирования Постановка задачи  Необходимо найти минимальное (максимальное) значение линейной функции n z = ∑ c j x j + с0 → min(max) j =1 при линейных ограничениях n ∑a x j =1 ij j … ,m = bi , i = 1,  … ,n и условии: x j ≥ 0, x j ∈ Z , j = 1,  22 Методы решения ЗЦП  Графический метод  Метод Гомори 23 Графический метод решения задачи целочисленного программирования 1. 2. 3. Находим область допустимых решений (ОДР) по заданной системе ограничений. Если ОДР – пустое множество, то задача не имеет решений Если ОДР является непустым множеством, строится вектор нормали n = (c1 ;c2 ) Проводится линия уровня f, перпендикулярная вектору нормали n ( c1 x1 + c2 x2 = const ) 24 Графический метод решения задачи целочисленного программирования 4. Перемещаем линию уровня в направлении вектора нормали, рассматриваем только целочисленные решения: находим первую точку Xmin пересечения такой линии с ОДР. fmin = f(Xmin) 5. Продолжая перемещать линию уровня в направлении вектора n, находим Xmax – последнюю точку пересечения линии уровня с ОДР с целочисленными координатами. fmax = f(Xmax) 25 Задача 2 Решить задачу целочисленного программирования графическим методом  f = 3 x1 + 2 x2 → max  x + x ≤ 13  1 2  x1 − x2 ≤ 6  − 3 x1 + x2 ≤ 9  x1 ≥ 0, x2 ≥ 0   x1 , x2 ∈ Z 26 Решение 1. По системе ограничений соответствующие прямые, не условие на целочисленность: l3 X2 𝑙1 : 𝑥1 + 𝑥2 = 13 𝑙2 : 𝑥1 − 𝑥2 = 6 13 𝑙3 : −3𝑥1 + 𝑥2 = 9 строим учитывая B A 9 l2 С X1 -3 О 6 D 13 l1 -6 27 Решение Строим вектор нормали 𝑛 = (3; 2) по целевой функции 𝑓 = 3𝑥1 + 2𝑥2 3. Линия уровня задается уравнением 2. 3𝑥1 + 2𝑥2 = const l3 X2 13 B A 9 l2 С n X1 -3 О D 13 6 l1 -6 f 28 Решение 4. Перемещаем линию уровня по направлению вектора нормали и рассматриваем в качестве возможных решений только точки с целочисленными координатами l3 X2 13 B A 9 l2 E n С X1 -3 О 6 D 13 l1 -6 f 29 Решение 5. Находим координаты точки максимума: т. Е имеет целочисленные координаты: 𝐸(9; 4) Точка С - точка пересечения прямых l2 и l3 (не целочисленное решение) 𝑥1 = 9,5 𝑥1 + 𝑥2 = 13 � � 𝑥2 = 3,5 𝑥1 − 𝑥2 = 6 Следовательно: 𝑋𝑚𝑎𝑎 = (9; 4) 𝑧𝑚𝑎𝑎 = 𝑧 9; 4 = 3 ∙ 9 + 2 ∙ 4 = 35 30 Метод Гомори Определение оптимального плана исходной задачи целочисленного программирования без учета целочисленности переменных  Если в найденном плане все числа являются целыми, то данный план является оптимальным планом задачи целочисленного программирования  31 Метод Гомори  Если в найденном плане переменная xk является дробной, то к системе ограничений добавляется неравенство {} ~ ~ ∑ {aij }⋅ x j ≥ bi n j =1  {a} - дробная часть числа а 32 Задача 3 Решить задачу методом Гомори: z = x1 + 5 x2 + 3 → max − x1 + x2 ≤ 2   x1 + x2 ≤ 7  x ≥ 0, x ≥ 0 2 1 33 Решение   Приведем систему к каноническому виду: −𝑥1 + 𝑥2 + 𝑥3 = 2 �𝑥1 + 𝑥2 + 𝑥4 = 7 𝑥𝑖 ≥ 0, 𝑖 = 1, … , 4 Перепишем целевую функцию: 𝑧 − 𝑥1 − 5𝑥2 = 3 Запишем начальную симплекс-таблицу (не учитывая условие целочисленности):  Базис bi x1 x2 x3 x4 x3 2 -1 1 1 x4 7 1 1 1 z 3 -1 -5 Решение Базис bi x1 x2 x3 x4 x3 2 -1 1 1 x4 7 1 1 1 z 3 -1 -5 𝑚𝑚𝑚 2 7 ; =2 1 1 Базис bi x1 x2 x3 x4 x2 2 -1 1 1 x4 5 2 -1 1 z 13 -6 5 Решение Базис bi x1 x2 x3 x4 x2 2 -1 1 1 x4 5 2 -1 1 z 13 -6 5 Базис bi x1 x2 x3 x4 x2 9/2 1 1/2 1/2 x1 5/2 1 -1/2 1/2 z 28 2 3 5 9 𝑋𝑚𝑚𝑚 = ( ; ; 0; 0) 2 2 𝑧𝑚𝑚𝑚 = 28 Решение Полученное решение не учитывает целочисленность переменных, следовательно решение не является оптимальным  Дробные части у переменных 𝑥1 и 𝑥2 одинаковые, поэтому вводим ограничение по любой строке таблицы:  Базис bi x1 x2 x3 x4 x2 9/2 1 1/2 1/2 x1 5/2 1 -1/2 1/2 z 28 2 3 1 1 9 1 𝑥2 + 𝑥3 + 𝑥4 ≥ 2 2 2 Решение 1 1 9 1 𝑥2 + 𝑥3 + 𝑥4 ≥ 2 2 2  1 1 1 𝑥3 + 𝑥4 ≥ 2 2 2 𝑥3 + 𝑥4 ≥ 1 Приведем полученное ограничение к канонической форме: 𝑥3 + 𝑥4 − 𝑥5 = 1 −𝑥3 − 𝑥4 + 𝑥5 = −1 Решение  Добавим ограничение к последней таблице: Базис bi x2 x1 −𝑥3 − 𝑥4 + 𝑥5 = −1 x1 x2 x3 x4 x5 9/2 1 1/2 1/2 1 -1/2 -1 1/2 -1 x5 5/2 -1 z 28 2 3 1  Решение Полученная задача решается двойственным симплекс методом: Базис bi x1 x2 x3 x4 x2 9/2 1 1/2 1/2 x1 1 -1/2 -1 1/2 -1 x5 5/2 -1 z 28 2 3 2 3 𝑚𝑚𝑚 ; =2 −1 −1 x5 1/2 x5 1 Базис bi x1 x2 x3 x4 x2 4 1 x1 1 1 1 1 -1/2 x3 3 1 z 26 1 2 -1  Решение Получаем оптимальное решение задачи целочисленного программирования: Базис bi x1 x2 x3 x4 x2 4 1 x1 1 1 1 1 -1/2 x3 3 1 z 26 1 2 𝑋𝑚𝑚𝑚 = 3; 4 𝑧𝑚𝑚𝑚 = 26 x5 1/2 -1 Финансовый университет при Правительстве РФ Департамент анализа данных, принятия решений и финансовых технологий Методы оптимальных решений Лекция № 5: «Теория игр» Минкова Анастасия Сергеевна План лекции Основные понятия теории игр  Нижняя и верхняя цена игры  Игры с седловой точкой  Решение игр в смешанных стратегиях  Теорема фон Неймана  Доминирующие и доминируемые стратегии  Решение игр методами линейного программирования  2 Теория игр Игра – математическая модель конфликтной ситуации  Игроки – стороны, участвующие в конфликте  Выигрыш – исход конфликта  Стратегия – выбор нескольких вариантов действий для достижения своих целей каждого из игроков  Классификация игр Парная игра – игра, в которой участвует два игрока Множественная игра – игра, в которой число игроков больше двух 2. Игра с нулевой суммой (антагонистическая игра) – игра, в которой выигрыш одного из игроков равен проигрышу другого 1. Классификация игр 3. 4. Коалиционная игра – игра, в которой участники множественной игры объединяют свои усилия по достижению лучшего результата В противном случае игра – бескоалиционная Статические и динамические игры (параметры изменяются во времени) Теория игр Ход игрока – выбор и осуществление одного из предусмотренных правилами действий  Личный ход – сознательный выбор игроком одного из возможных действий  Случайный ход – случайно выбранное действие  Цель теории игр – определение оптимальной стратегии для каждого игрока  Теория игр Для нахождения решения игры необходимо выбрать стратегию для каждого игрока, которая удовлетворяет условию оптимальности – один из игроков должен получать максимальный выигрыш, когда второй придерживается своей стратегии  Второй игрок при этом должен иметь минимальный проигрыш, если первый придерживается своей стратегии  Платежная матрица Пусть игрок A располагает m стратегиями A1 , A2, …, Am и игрок B имеет n стратегий B1 , B2, …, Bn  Выигрыш игрока A при выборе стратегий Ai и Bj обозначим aij  Платежная матрица (матрица игры):  𝑎11 𝑎21 … 𝑎𝑚1 𝑎12 𝑎22 … 𝑎𝑚2 … 𝑎1𝑛 … 𝑎2𝑛 … … … 𝑎𝑚𝑚 Нижняя цена игры  Пусть αi – наименьший выигрыш игрока A при выборе им стратегии Ai для всех возможных стратегий игрока B: α i = min α ij  j=1, n Тогда гарантированный выигрыш игрока A при любой стратегии игрока B равен: α = max α i = max min α ij i =1, m α – нижняя цена игры. i =1, m j=1, n Верхняя цена игры  Число β – верхняя цена игры: β = min max α ij j=1, n i =1, m  β - гарантированный проигрыш игрока B Если α = β = v, то v – чистая цена (или цена игры).  Тогда пара оптимальных стратегий Ai и Bj, для которой aij = v называется седловой точкой платежной матрицы  Задача 1 Найдите седловую точку в игре с матрицей выигрышей А. В ответе указать чистую цену игры  2 10 25 0     13 14 19 6  А= − 5 3 − 2 − 4    18 5 − 3 − 5    Решение:   2 10 25 0     13 14 19 6  А= − 5 3 − 2 − 4    18 5 − 3 − 5    Нижняя цена игры: α1 = min (2; 10; 25; 0) = 0 α2 = min (13; 14; 19; 6) = 6 α3 = min (-5; 3; -2; -4) = - 5 α4 = min (18; 5; -3; -5) = - 5 α = max (0; 6 ; -5; -5) = 6  2 10 25 0     13 14 19 6  А= − 5 3 − 2 − 4    18 5 − 3 − 5     Верхняя цена игры: β1 = max (2; 13; -5; 18) = 18 β2 = max (10; 14; 3; 5) = 14 β3 = max (25; 19; -2; -3) = 25 β4 = max (0; 6; -4; -5) = 6 β = min (18; 14 ; 25; 6) = 6  2 10 25 0     13 14 19 6  А= − 5 3 − 2 − 4    18 5 − 3 − 5    Получаем: α = β = 6 v=6 Седловая точка - (A2,B4) Решение игры в смешанных стратегиях Если α < β, то применение чистых стратегий не дает оптимального решения игры  Оптимальное решение можно получить случайным образом путем чередования чистых стратегий – в смешанных стратегиях    Смешанная стратегия SА игрока А – применение чистых стратегий A1 , A2, …, Am с вероятностями р1 , р2, …, рm 𝐴1 𝑆𝐴 = 𝑝1 𝐴2 𝑝2 … 𝐴𝑚 … 𝑝𝑚 𝐵1 𝑆𝐵 = 𝑞1 𝐵2 𝑞2 … 𝐵𝑛 … 𝑞𝑛 m ∑p i =1 i =1 Для игрока B аналогично: n ∑q j =1 j =1 Решение игры в смешанных стратегиях Оптимальное решение игры – пара оптимальных стратегий SА*, SВ* в общем случае смешанных, которые обладают свойством:  Если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей  Решение игры в смешанных стратегиях Выигрыш, соответствующий оптимальному решению называется ценой игры v α≤v≤β  Теорема фон Неймана: Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий  Задача 2 Найдите решение игры в смешанных стратегиях. В ответе указать среднюю цену игры 1,5 3   А =   2 1 1,5 3   А =   2 1 Решение: Найдем нижнюю и верхнюю цену игры: α = 1,5, β = 2, α ≠ β  Средний выигрыш игрока А равен цене игры v, если он использует оптимальную смешанную стратегию s* =  A1 A 2   А  p*  1 p*2  игрок B использует чистую стратегию B1 (т.е. первый столбец платежной матрицы) 1,5𝑝1∗ + 2𝑝2∗ = 𝑣 1,5 3   А =   2 1 Средний выигрыш игрока А также равен цене игры v, если игрок B применяет стратегию B2 (т.е. второй столбец платежной матрицы): 3𝑝1∗ + 𝑝2∗ = 𝑣  Получаем систему уравнений для игрока А: * *  1,5 p1 + 2 p2 = v  * * 3 + p p  1 2 =v  p* + p* = 1 2  1 1,5 p1* + 2 p2* = v  * * 3 + p p  1 2 =v  p* + p* = 1 2  1 𝑝2∗ = 1,5𝑝1∗ �3𝑝1∗ + 𝑝2∗ = 𝑣 𝑝1∗ = 1 − 𝑝2∗ 𝑝2∗ 𝑝2∗ ) = 1,5(1 − � 3𝑝1∗ + 𝑝2∗ = 𝑣 𝑝1∗ = 1 − 𝑝2∗ 1,5𝑝1∗ + 2𝑝2∗ = 3𝑝1∗ + 𝑝2∗ 3𝑝1∗ + 𝑝2∗ = 𝑣 � 𝑝1∗ = 1 − 𝑝2∗  * 3  p2 = 5  2 *  p1 = 5  v=9  5 1,5 3   А =  2 1   Составим аналогичную систему для игрока В: 1,5q + 3q = v  *  2 q + q2 = v  q + q* = 1 2  * 1 * 1 * 1 * 2 4𝑞2∗ = 𝑞1∗ �2𝑞1∗ + 𝑞2∗ = 𝑣 𝑞1∗ = 1 − 𝑞2∗ 1,5𝑞1∗ + 3𝑞2∗ = 2𝑞1∗ + 𝑞2∗ �2𝑞1∗ + 𝑞2∗ = 𝑣 𝑞1∗ = 1 − 𝑞2∗  * 1  q2 = 5  4 * q1 = 5  v=9  5 Ответ: pопт 9 2 3 4 1 = ( ; ), qопт = ( ; ), v = 5 5 5 5 5 Задача 3 Найдите решение игры в смешанных стратегиях графическим способом. В ответе указать среднюю цену игры  4 2  А =   3 5 Решение:  4 2  А =   3 5 Найдем нижнюю и верхнюю цену игры: α = 3, β = 4, α ≠ β  На оси Оx отложим единичный отрезок A1A2  Прямая x = 0 соответствует стратегии A1 игрока A, а прямая x = 1 соответствует стратегии A2  y Пусть игрок В примет стратегию В1  Отложим на прямых x=0иx=1 N В1 соответствующие выигрыши и В2 v обозначим точки В1  Сделаем аналогично S A* для второй стратегии А1 p1* В2 игрока В p2*  В2 В1 x А2  4 2  А =   3 5 y Точки, лежащие на ломаной линии В2NВ1 показывают В2 минимальный N В 1 выигрыш игрока A В1 при использовании В2 v им любой смешанной стратегии S A* x  В точке N А2 А1 * минимальный * p 1 p2 выигрыш достигает  4 2 максимума, поэтому  А =   3 5  существует стратегия y S A* = ( p 1* ; p2* )  В2 Ордината точки N равна цене игры v В N 1  Найдем уравнения прямой В1В1 x−0 y−4 = 1− 0 3 − 4  Уравнение прямой В2В2 x−0 y−2 = 1− 0 5 − 2 В2 В1 v S A* А1 p2 * p1* x А2  4 2  А =   3 5 Получаем систему уравнений:  y = −x + 4   y = 3x + 2 1 p =x= 2 1 * * p1 = 1 − p2 = 2 * 2 7 v= y= 2 1  x = 2  7 y = 2  Определим аналогично геометрическим способом оптимальную стратегию игрока В  Поменяем местами игроков А и В и вместо максимума найдем минимум верхней границы   Найдем уравнения прямой A1A1 x−0 y−4 = 1− 0 2 − 4  Уравнение прямой A2A2. y А2 А1 M А2 А1 v x −0 y −3 = 1− 0 5 − 3 S B* В1 q2* x q1* В2  4 2  А =   3 5  Получаем систему уравнений:  y = −2 x + 4   y = 2x + 3 1  x = 4  7 y = 2  1 q =x= 4 3 * * q1 = 1 − q2 = 4 * 2 7 v= y= 2 Ответ: pопт 3 1 7 1 1 = ( ; ), qопт = ( ; ), v = 4 4 2 2 2 Доминирующие и доминируемые стратегии  Если в платежной матрице A все элементы i-й строки не меньше соответствующих элементов k-й строки, aij ≥ akj , j = 1, 2, …, n, а по крайней мере один строго больше, то i-я строка – доминирующая, а k-я строка – доминирумая Доминирующие и доминируемые стратегии Игроку А не выгодно применять стратегии, которым соответствуют доминируемые строки, а игроку В – доминирующие столбцы.  При решении игры можно уменьшить размер платежной матрицы с помощью удаления из нее доминируемых строк и доминирующих столбцов.  Задача 4 Найти решение игры в смешанных стратегиях, предварительно упростив ее. В ответе указать среднюю цену игры 7  5 А= 5  2  6 5 4 2  4 3 2 3 6 6 3 5  3 3 2 4  Решение: 7  5 А= 5  2  6 5 4 2  4 3 2 3 6 6 3 5  3 3 2 4  Найдем нижнюю и верхнюю цену игры: α = 3, β = 4, α ≠ β  Строка А2 доминируемая относительно строки А1  Строка А4 доминируемая строки А3.  Для игрока А они не выгодны   7 6 5 4 2   Остается матрица: А =  5 6 6 3 5  7 6 5 4 2  А =  5 6 6 3 5 Для игрока В при сравнении:  В1 и В4 исключим столбец В1  В2 и В4 исключим столбец В2  В3 и В4 исключим столбец В3  4 2 Остается матрица: А =    3 5  4 2  А =   3 5  Решим полученную задачу аналитическим способом. Для игрока А: 4 p + 3 p = v  2 p + 5 p = v  p + p* = 1 2  * 1 * 1 * 1 * 2 * 2  * 1  p2 = 2  1 *  p1 = 2  v=7  2  Для игрока В:  * 1 q 2 = 4  3 * q1 = 4  v= 7  2 4q1* + 2q2* = v  * * 3q1 + 5q2 = v  q* + q* = 1 2  1 Ответ: pопт  4 2  А =   3 5 3 1 7 1 1 = ( ;0; ;0), qопт = (0;0;0; ; ), v = 2 2 2 4 4 7  5 А= 5  2  6 4 6 3 5 3 6 3 4 2 3 2 2  3 5  4  4 А =  3 2  5 Приведение матричной игры к задаче линейного программирования Пусть игрок A обладает Ai стратегиями i = 1, 2, …, m и игрок B имеет Bj стратегий j = 1, 2, …, n  Оптимальная стратегия SA* обеспечивает игроку A при любой стратегии игрока B средний выигрыш, не меньший, чем цена игры v, и при оптимальной стратегии игрока B выигрыш равный цене игры v   Пусть v > 0, тогда для оптимальной стратегии SA* все средние выигрыши не меньше цены игры v:  a11 p1 + a21 p2 + ... + am1 pm ≥ v a p + a p + ... + a p ≥ v  12 1 22 2 m2 m  … …  a1n p1 + a2 n p2 + ... + amn pm ≥ v  Пусть pj v = x j , тогда:  a11 x1 + a21 x2 + ... + am1 xm ≥ 1 a x + a x + ... + a x ≥ 1  12 1 22 2 m2 m  …  a1n x1 + a2 n x2 + ... + amn xm ≥ 1 Цель игрока A – максимизировать свой гарантированный выигрыш.  Рассмотрим  m m ∑ x =∑ j =1  j j =1 pj 1 m 1 = ∑ pj = v v j =1 v m Поскольку v → max , то ∑ x j → min j =1  Получаем задачу программирования:  f = x1 + x2 + ... + xm → min  a x + a x + ... + a x ≥ 1 m1 m  11 1 21 2 a12 x1 + a22 x2 + ... + am 2 xm ≥ 1  …  a1n x1 + a2 n x2 + ... + amn xm ≥ 1   x1 ≥ 0, x2 ≥ 0,..., xm ≥ 0  Решением задачи будет стратегия SA* игрока A линейного оптимальная Для определения оптимальной стратегии SВ*игрока B следует учесть, что игрок B стремится минимизировать гарантированный выигрыш игрока A  Тогда задача линейного программирования будет иметь вид:   ϕ = y1 + y2 + ... + yn → max  a y + a y + ... + a y ≤ 1 1n n  11 1 12 2  a21 y1 + a22 y2 + ... + a2 n yn ≤ 1  …  am1 y1 + am 2 y2 + ... + amn yn ≤ 1   y1 ≥ 0, y2 ≥ 0,..., ym ≥ 0 где yj = qj v Задача 5 Найти решение игры с линейного программирования 1 2 0   А = 1 0 1  2 1 0   помощью Решение:  1 2 0   А = 1 0 1  2 1 0   Найдем нижнюю и верхнюю цену игры: α = 0, β = 1, α ≠ β  Решим задачу для второго игрока В с помощью линейного программирования:  ϕ = y1 + y2 + y3 → max y + 2y ≤1 2  1  y1 + y3 ≤ 1 2 y + y ≤ 1 2  1  y1 ≥ 0, y2 ≥ 0, y3 ≥ 0 где yj = qj v ϕ = y1 + y2 + y3 → max y + 2y ≤1 2  1  y1 + y3 ≤ 1 2 y + y ≤ 1 2  1  y1 ≥ 0, y2 ≥ 0, y3 ≥ 0  1 2 0   А = 1 0 1  2 1 0   Приведем полученную систему к каноническому виду: ϕ = y1 + y2 + y3 → max   y1 + 2 y2 + y4 = 1   y1 + y3 + y5 = 1 2 y + y + y = 1 2 6  1  yi ≥ 0, i = 1,6 ϕ = y1 + y2 + y3 → max   y1 + 2 y2 + y4 = 1   y1 + y3 + y5 = 1 2 y + y + y = 1 2 6  1  yi ≥ 0, i = 1,6  1 2 0   А = 1 0 1  2 1 0   ϕ − y1 − y2 − y3 = 0 Решим полученную задачу линейного программирования симплекс-методом: Базис bi y1 y2 y3 y4 y5 y6 y4 1 1 2 1 y5 1 1 1 1 y6 1 2 1 1 φ -1 -1 -1  1 1 1 min  ;  =  2 1 2 Базис bi y1 y2 y3 y4 y5 y6 y4 1 1 2 1 y5 1 1 1 1 y6 1 2 1 1 φ -1 -1 -1 Базис bi y1 y2 y3 y4 y5 y6 y2 1/2 1/2 1 1/2 y5 1 1 1 1 y6 1/2 3/2 -1/2 1 φ 1/2 -1/2 -1 1/2 Базис bi y1 y2 y3 y4 y5 y6 y2 1/2 1/2 1 1/2 y5 1 1 1 1 y6 1/2 3/2 -1/2 1 φ 1/2 -1/2 -1 1/2 Базис bi y1 y2 y3 y4 y5 y6 y2 1/2 1/2 1 1/2 y3 1 1 1 1 y6 1/2 3/2 -1/2 1 φ 3/2 1/2 1/2 1 3  1  y =  0; ;1, ϕ max = 2  2  * Поскольку  yj = qj v и q1 q2 q3 1 1 + = (q1 + q2 + q3 ) = y1 + y 2 + y3 = + v v v v v то 2 v= 3 2 q = y ⋅v = 0⋅ = 0 3 * 1 * 1 1 2 1 q = y ⋅v = ⋅ = 2 3 3 2 2 * * q3 = y3 ⋅ v = 1 ⋅ = 3 3 * 2 * 2 3  1  y * =  0; ;1, ϕ max = 2  2  Базис bi y1 y2 y3 y4 y5 y6 y2 1/2 1/2 1 1/2 y3 1 1 1 1 y6 1/2 3/2 -1/2 1 φ 3/2 1/2 1/2 1 1 2 1 p = x ⋅v = ⋅ = 2 3 3 * 1 * 1 v= 2 3 2 2 p = x ⋅ v = 1⋅ = 3 3 2 * * p3 = x3 ⋅ v = 0 ⋅ = 0 3 * 2 * 2 Ответ: pопт 2 1 2   1 2 =  0; ; , qопт =  ; ;0 , v = 3 3 3   3 3