Главная | Обратная связь

Построение двойственной задачи линейного программирования. Экономический смысл двойственных оценок.

С каждой задачи ЛП тесно связана другая задача, которая называется двойственной.

Первоначальная задача - исходная.

Связь двойственной и исходной задачи - 5 свойств:1:Коэфициенты лин целевой ф двойственной задачи - столбец свободных членов исходной задачи в систем лин ограничений.2:Столбец свободных членов системы ограничений двойственной задачи есть коэфиц лин целевой ф исходной задачи.3:Матрицы системы ограничений (из коэф a_ij при неизвестных) двойственной задачи есть транспонированная матрица системы ограничений исходной (матрица А^Т – трансп-ая к матрице А, -в исходной матрице поменять местами соотв строки и столбцы).4: Если в исходной задачи все ограничения – неравенства имеет вид ≤, то в двойственной задаче они меняются на противоположные.5:Если в исходной задаче требовалось найти max линейно цел функции, то в двойственной задаче min лин цел ф.

Если исходная задача имеет вид: Z=p₁*x₁+p₂*x₂+…+p_n*x_n àmax a_m1*x₁+a_m2*x₂+…+a_mn*x_n≤b_m ; x_j≥0 (j=1,2,...,n)

то двойственная задача принимает вид:g=в₁*у₁+в₂*у₂+…+в_my_màmin a₁₂+a₂₂*y₂+…+a_m2*y_m≤p₂ a_1n*y₁+a_2n*y₂+…+a_mn*y_m≥p_n y_j≥0 (j=1,2,...,m)

Пример: Построить двойственную задачу лин прогр след исходы: Z=2x₁+3x₂àmax (исходная) ₁+x₂≤6; 3x₁+x₂≤12; X₁+2x₂≤10 (2-ая) ЗЛП:g=6y₁+12y₂+10y₃à min y₁+3y₂+y₃≥2 y₁+y₂+2y₃≥3 y1,y ₂ , y₃ ≥0

ЭК СМЫСЛ ДВОЙСТВЕННЫХ ОЦЕНОК.

Эк смысл двойств оценок раскрывается в основных свойствах двойственности, их 3.

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

Пример: Произвести анализ (2-ых) оценок (см усл из примера 2)опт план: =(1,0,1).

1: увеличить первый(третий) ресурс на 1 ед., то суммарная прибыль увелич на 1-у денж. ед.

Но увеличение второго ресурса не влияет на рост прибыли, так как у₂=0

2: Max оценка в оптимальн плане (2-ой) задачи - ресурсы 1-го и 3-го типа, значит они дефицитные.

Ресурс 2-го типа менее дефицитен,т.к. его компоненты min в плане.

3 Нормы заменяемости ресурсов 1-го и 3-го типа: - т.е. потеря одной единицы 1-го типа может быть скомпенсирована одной ед ресурса 3-го типа. При сохранении этой пропорции суммарная прибыль останется на прежнем уровне.

15. Получение оптимального плана двойственной [2-ой] задачи. Экономический смысл двойственных оценок.

Оптимальный план двойственной(2-ой) задачи можно получить любым из известных способов реш задач линейных программ.

Но быстрый его поиск с помощью теорий двойственности:

Теорема 1:Если разрешима одна из (2-ых) задач, то разрешима и другая при чём значения их линейно целевых ф после подстановки в них компонентов оптимального плана равны между собой..Теорема 2: Если при подстановке компонентов min плана исходной задачи в систему ограничений, ограничения номер i выполняется как строгое неравенство, то компонента с тем же номером i оптимального плана (2-ой) задачи = 0. Теорема 3:Если компоненты с номером i оптимального плана исходной задачи «+», то огранич с тем же номером i (2-ой) задачи выполн как строгое равенство.

Пример:Получить оптимальный план (2-ой) задачи (перд билет-условие).

Решение: (2-ой) задача к исходной: Z=2x₁+3x₂àmax (исходная) ₁+x₂≤6; 3x₁+x₂≤12; X₁+2x₂≤10 (2-ая) ЗЛП:g=6y₁+12y₂+10y₃à min y₁+3y₂+y₃≥2 y₁+y₂+2y₃≥3 y1,y ₂ , y₃ ≥0

(Продолжение) Оптим план (2,4) ; Z= 16. Подставим его компоненты в систему ограничений(исходной): ;(2)3*2+4=10 ; 2+2*4=10

(2 теорема)В ограничении (2) выполн как строгое неравенство, то в (2-ой) задаче у₂=0

(3 теорема)Т.к.1-ая и 2-ая компоненты опт плана исходной задачи «+» х₁=2>0, х₂=4>0, то 1 и 2-ое ограничение (2-ой) задачи выполн как строгие равенства: ; y₁+y₂+2y₃=3; у₂=0 опт план: =(1,0,1)

(1 теорема) Значение ЗЛП (2-ой) задачи g(y)=6*1+12*0+10*1= Z(x), то полученый план оптимальный.

ЭК СМЫСЛ ДВОЙСТВЕННЫХ ОЦЕНОК.

Эк смысл двойств оценок раскрывается в основных свойствах двойственности, их 3.

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

Пример: Произвести анализ (2-ых) оценок (см усл из примера 2)опт план: =(1,0,1).

1: увеличить первый(третий) ресурс на 1 ед., то суммарная прибыль увелич на 1-у денж. ед.

Но увеличение второго ресурса не влияет на рост прибыли, так как у₂=0

2: Max оценка в оптимальн плане (2-ой) задачи - ресурсы 1-го и 3-го типа, значит они дефицитные.

Ресурс 2-го типа менее дефицитен,т.к. его компоненты min в плане.

3 Нормы заменяемости ресурсов 1-го и 3-го типа: - т.е. потеря одной единицы 1-го типа может быть скомпенсирована одной ед ресурса 3-го типа. При сохранении этой пропорции суммарная прибыль останется на прежнем уровне.

16. Основные понятия теории игр.

Теория игр – изучает математические модели принятия решений в конфликтных ситуациях.

До настоящего момента рассматривались задачи, в которых отсутствовали неконтролируемые факторы(y), (детерминированные случаи).

Теперь перейдем к решению задач с неконтролируемыми факторами.

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

1. Внешние или объективные обстоятельства (природа)

2. Сознательные или субъективные действия противника

Исследованием таких задач занимается теория игр. Довольно часто к теории игр относят лишь 2 случай(так называемые конфликтные ситуации). Но операции, на которые также воздействует природа, тоже занимается теория игр. ТИ представляет собой математическую теорию для решения подобного рода задач. Ее цель-это выработка рекомендаций по разумному поведению участников конфликта. Конфликт представляется в виде математической модели, которая и называется игрой. Игры бывают парные, в которые присутствуют 2 участника, и множественные, в которых присутствуют более 2 участников. Участники(игроки)в процессе игры придерживаются определенных стратегий. Стратегией называется совокупность правил, определяющий поведение игрока в зависимости от сложившейся ситуации. Игра называется конечной, если число возможных стратегий для каждого игрока конечно. В противном случае игра явл. Бесконечной. То есть для начала будем заниматься исследованием игр(конфликтных ситуаций),которые бывают 2 типов:

1. Антагонистические

2. С не противоположными интересами