23. Изложите постановку двойственных задач. Перечислите правила построения задачи, двойственной данной.

Каждой задаче Л.П. можно сопоставить определённым образом с ней связанную другую задачу которая называется двойственной по отношению к данной. Если исходная задача Л.П. состоит в минимизации л. Функции Когда заданны ограничения в форме неравенств

При условии не отрицательности Xi, то с ней связанна двойственная задача, состоящая в том что требуется максимизировать линейную функцию , при ограничениях:

Матрицы А и А` составленные из коэффициентов при переменных получаются друг из друга транспонированием. В правых частях системы ограничений каждой задачи стоят ограничения линейной функции взятой из другой задачи. В системе ограничений задачи1 (минимизация) ограничения неравенств типа >= , а в системе ограничений задачи А` (максимизация) все неравенства типа <= . Понятие двойственности является взаимным, т.е. если задачу 1` записать в форме аналогичной задаче 1, то двойственная к ней окажется исходная задача, поэтому задачи 1 и 1` называются взаимо двойственными или взаимно сопряженными.

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

24. Основные теоремы двойственности

Теорема 1. Если одна из Двойственной задачи имеет оптимальное решение x*=(x1*,….,xn*), то и другая имеет оптимальное решение u*=(u1*,…..,um*). При этом экстремальные значения целевых ф-й задач, совпадают, т.е.

если целевая ф-я одной из задач двойственной пары не ограничена, то другая задача не имеет решения. Теорема 2 Если какая-то переменная xj(j=1,n) оптимального решения исходной задачи положительна, то j-е ограничения Двойственной задачи ее оптимальным решением обращается в строгое равенство. Если оптимальное решение исходной задачи обращает какое-то i-e (i=1,m) ограничение в строгое неравенство, то в оптимальном решении Двойственной задачи, переменная u1, равна

25. Изложите правила построения двойственных задач.

Этап 1: 1)Просматриваем коэффициент F-строки, если все они неотрицательны, то переходят к к пункту 1 этапа 2. 2)Если в F-строке имеется отрицательн коэффиц , то выделяют столбец, содерж этот коэффиц 3) В выделенном столбце отыскивают отрицательное число и содерж его строку полагают разделяющей 4)вычисляют двойственные отношения 5)с найденным разреш элементом делают шаг обыкновенных жордановых исключений Этап 2:1)просматривают столбец свободных членов, если все Эл-ты столбца неотриц, то оптим решение доступно 2)если в столбец свободных членов есть отрицат Эл-ты, то среди них наход наименьший 3) разрешающий Эл-т наход по наименьшему двойственному отношению 4)с найденным разреш Эл-том делаю один шаг обыкновенных жордановых иключений

26. Изложите постановку и математическую модель транспортной задачи.

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

1-ая задача получила название транспортной по критерию стоимости, а 2-я по критерию времени. Теорема- транспортная задача имеет решение, если суммарный запас груза в пунктах отправления равен суммарному спросу в пунктах назначения.