Двойственность линейного программирования

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ОРЕНБУРГСКИЙ  ГОСУДАРСТВЕННЫЙ ИНСТИТУТ МЕНЕДЖМЕНТА 
 
 
 
 
 
 
 
 
 

Реферат 
 

по дисциплине  «Математические методы принятия управленческих решений»

на тему: «Двойственность линейного программирования» 
 

Выполнила студентка

очной формы обучения

специальности «Менеджмент организации»

третьего курса  32 группы  

Шумакова Ю. А.          

                                                                                                                 
 

Проверила

Кочетова Л.А. 
 
 
 

Оренбург

2009

 

     Содержание

    Введение………………………………………………………………..…….3

    1. Виды двойственных задач и  составление их математических 

    моделей……………………………………………………………………….4

    2. Основные теоремы двойственности……………………………………..6

    3. Решение двойственных задач…………………………………………….7

    4.Экономический  анализ задач с использованием  теории двойственности……………………………………………………………….….12

    5. Стратегическое планирование выпуска  изделий с учетом имеющихся  ресурсов…………………………………………………………………………..14

    Заключение…………………………………………………...……………..18

    Библиографический список……………………………………………......19 

 

     Введение

      Двойственность  в линейном программировании - принцип, заключающийся в том, что для каждой задачи линейного программирования можно сформулировать двойственную задачу.

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

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

 

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

    Различают симметричные, несимметричные и смешанные  двойственные задачи. 

    1. Виды двойственных задач и составление их математических моделей

      Симметричные двойственные задачи

    Дана  исходная задача

    L (x) = c1x1 + c2x2 +…+ cnxn  → max

    при ограничениях:

    a11x1 + a12x2 + … + a1nxn  ≤ b1      │ y1 ,

    a21x1 + a22x2 + … + a2nxn  ≤ b2      │ y2  ,

    ………………………………………

    am1x1 + am2x2 + … + amnxn  ≤ bm      │ ym  ,

    xj ≥0 , j = 1,n ,     i = 1,m.

    Задача  дана в неканоническом виде. Составим математическую модель двойственной задачи, для этого:

    - каждому неравенству системы  ограничений исходной задачи  приводим в соответствие переменную  yi ;

    - составляем целевую функцию, коэффициентами  которой являются свободные члены  системы ограничений исходной задачи;

    - составляем систему ограничений.  Коэффициенты системы ограничений  образуют транспонированную матрицу  коэффициентов системы ограничений  исходной задачи. Знаки неравенств меняются на противоположные;

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

    Математическая  модель двойственной задачи имеет вид

    S(y) = b1y1  + b2y2 +…+ bmym  → min

    при ограничениях:

    a11y1 + a12y2 + … + am1ym   ≤ c1      ,

    a12y1 + a21y2 + … + am2ym   ≤ c2      ,

    ………………………………………

    a1ny1 + a2ny2 + … + amnym   ≤ cn      ,

    yj ≥0 , i = 1,m ,     j = 1,n. 

      Несимметричные двойственные задачи 

    Дана  исходная задача

    L (x) = c1x1  + c2x2 +…+ cnxn  → max

    при ограничениях:

    a11x1 + a12x2 + … + a1nxn   = b1      │ y1 ,

    a21x1 + a22x2 + … + a2nxn   = b2      │ y2  ,

    ………………………………………

    am1x1 + am2x2 + … + amnxn   = bm      │ ym  ,

    xj ≥0 , j = 1,n .

    Задача  дана в каноническом виде. Составим математическую модель двойственной задачи.

    Для ее составления пользуемся тем же правилом, что и для составления симметричной задачи, с учетом следующих особенностей:

    - ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства ≥, если максимум, то  ≤ ;

    - переменные yi - произвольные по знаку.

    Математическая модель двойственной задачи имеет вид

    S(y) = b1y1  + b2y2 +…+ bmym  → min

    при ограничениях:

    a11y1 + a21y2 + … + am1ym   ≥ c1      ,

    a12y1 + a22y2 + … + am2ym   ≥ c2      ,

    ………………………………………

    a1ny1 + a2ny2 + … + amnxn   ≥ cn      ,

    yj ≥0 , i = 1,m ,     j = 1,n.

    yi – произвольные по знаку,  i = 1,m. 

      Смешанные двойственные задачи