Курс лекций по линейному программированию (стр. 2 из 6)
Теория двойственности
Двойственные задачи в ЛП играют важную роль, т.к. на основании результатов их решения проводится экономический анализ полученных результатов. Допустимые решения прямой и двойственной задач практически не связанны между собой, но их оптимальные решения таковы, что зная одно их них можно сразу найти другое.
| Прямая задача | Двойственная задача |
| Сколько и какой продукции необходимо произвести, чтобы при заданных ценах на реализацию запасов, имеющих ресурсов и при заданном способе производства получить максимальную прибыль от реализации произведенной продукции. Z=CX→max AX≤B X≥0 | Какова должна быть оценка цены единицы каждого вида ресурсов, что бы при заданных их количественных величин стоимости реализации производства из них продукции и заданном способе производства минимизировать общую стоимость затрат. F=BY→min ATY≥c Y≥0 |
Формально
| Определить вектор Х, удовлетворяющий ограничениям и обеспечивающий максимальный целевой функции z. X=(x1, … ,xn) Anx1+…+a1nxn≤bn ………… Amx1+…+amnxv≤bn | Оценим ресурсы, необходимые для производства продукции при заданном способе производства. За единицу стоимости ресурсов принимается единица стоимости выпускаемой продукции. Yi обозначим стоимость единицы i-ого вида ресурсов, то стоимость ресурсов, затраченных на изготовление j-ого вида продукции =  и по т. должна быть ≥ стоимости изначального продукта.  , тогда двойственная задача и задаче планирования производства планируется следующим образом: Определить вектор Y=(y1, … ,ym), удовлетворяющий ограничениям: a11y1+ … + a1mym≥0 ………… an1yi+ … + anmym≥0 и обеспечивающий минимум целевой функции. F=b1y1+…+bmym |
Виды моделей двойственных задач:
- Симметричные данные выше
- Несимметричные:
| Z=cx→min AX=B X≥0 | V = YB→max YAT≤C |
Соответствие между прямой и двойственной задачами
1. Целевая функция исследуется по максимуму 2. Коэффициент целевой функции прямой задачи 3. Матрица ограничений 4. Столбец правых частей целевой задачи  5. знаки соотношения правых и левых частей: а.) неравенство (i-ое ограничение) б.) равенство (i-ое ограничение) 6. Число ограничений 7. Переменные а.) xj≥0 б.) на xj нет ограничений на знак | 1. Целевая функция исследуется на минимум 2. Столбец свободных членов двойственной задачи 3. Транспонированная матрица 4. Коэффициент целевой функции 5. Переменные (ограничения) а.) yi≥0 б.) на yi нет ограничений на знак 6. Количество переменных 7. ограничения а.) j-ое ограничение неравенство б.) j-ое ограничение равенство |
Теорема № 1 двойственности
Для любой пары даойственных задач имеет место один из следующих задач:
1) прямая и двойственная задачи имеют оитимальное решение, то значение их целевых функций на соотвующее оптимальное решение совпадают.
2) Целевая функция прямой задачи неограниченна сверху на непустом множестве планов, то двойственная задача имеет пустое множество допустимых решений.
3) Прямая и двойственная задачи могут иметь пустое множество допустимых решение
4) Если множество допустимых решений одной из двойственных задач пусто, то целевая функция другой задачи неограниченна.
Лемма: для любых планов X и Y прямой и двойственной задач соответственно (прямая на максимум; двойственная на минимум) имеет место z(x)≤F(x), где z – целевая функция прямой, а F – целевая функция двойственной.
Теорема № 2 двойственности
Пусть х*=(х*1, …, х*n) и y*=(y*1, …, y*m) – допустимые решения прямой и двойственной задач, соответственно. Для того чтобы x* и y* были оптимальными решениями необходимо и достаточно выполнение следующих условий:
1.)
2.)
Условия 1 и 2 позволяют, зная оптимальное решение одной из задач, найти решение другой. На основании второй теоремы двойственности, формулируется критерии оптимальности для допустимого решения задач.
Теорема:
Пусть х1*- допустимое решение прямой задачи, то вектор х* является оптимальным решением прямой задачи в том и только в том случае, когда среди решений уравнения 1 при xj*≠0 найдётся хотя бы одно допустимое решение двойственной задачи и yi*=0 при выполнении условия
yi – это не цены, это оценка цен, т.к. если ресурс дефицитные (полностью используется в производстве) то оценка совпадает с ценой, а если ресурс не дефицитный, то оценка = 0.
Нахождение решения двойственной задачи по таблице оптимального решения прямой.
Пусть найдено оптимальное решение прямой задачи х*, которая определенна системой базисных векторов Аi, …, Aim через Сб обознач. вектор, состоящий из коэффициентов целевой функции при базисных переменных оптимального решения. Через Р-1 обозначают матрицу, обратную матрице Р, составленную из компонент векторов Аi, …, Aim оптимального базиса.
Теорема:
Если прямая задача имеет оптимальный план х*, то оптимальный план двойственной задачи y*=CБ.Р-1. Решение двойственной задачи находится в симплексной таблице оптимального решения прямой на пересечении индексной строки и векторов столбцов исходного базиса прямой.
Экономическая интерпретация.
Пусть имеются m видов ресурсов, количества b1, … ,bm. На основе этих ресурсов предполагают выпускать продукцию n различными способами, при этом за единицу времени применение j-ого способа расходуется аij единиц i-ого вида ресурсов, а выпускаемая, при этом, продукция имеет ценность ij. Как оценить имеющиеся ресурсы?
Пусть х=(х1, … ,хn) – вектор, компоненты которого – времена использования j-ого способа производства, то xj≥0 ∑аijxj≤bi, если yi – оценка ресурсов, используемых в единицу времени при j-ом способе производства.
Эта величина не может быть меньше ценности выпускаемой при тех же условиях продукции, то для любых х и у ценность всей выпускаемой продукции не превосходит суммарной оценки имеющихся ресурсовю
Z(x)≤F(Y)
Величина Δху=F(Y) – Z(X) характеризует потери в зависимости от плана х и выбранных ресурсных оценок у = > х и у надо выбирать так, чтобы величина потерь была наименьшей, а для этого достаточно план подобрать так, чтобы z(x) было как можно больше, а F(y) – как можно меньше. Отсюда возникает пара симметричных двойственных задач.
Из теоремы 1 двойственности следует, что оптимальному вектору оценок и оптимальному плану производства соответствуют нулевые производственные потери.
Из теоремы 2 двойственности следует, что если х*, у* - оптимальные решения прямой и двойственной задач соответственно, то справедливо соотношение:
Условие (*) интерпретируется: если оценка i-ого вида ресурса положительна в оптимальном плане, то ресурс используется полностью, если ресурс используется не полностью, то его оценка = 0.
Условие (**): если производство j-ого вида продукции включено в оптимальный план, то он в оптимальной оценке неубыточен. Если он убыточен (затратная оценка превосходит цену реализации) то этот продукт не производится в оптимальном плане.
∑aijyi – затратная оценка производства единицы j-ого вида продукции.
Лекция № 3: «Целочисленное программирование».
Примеры, показывающие необходимость применения целочисленных методов.
Задача о расписании (назначении).
Есть 3 самолета и 15 маршрутов. Известны затраты и прибыль от посылки каждого самолета на каждый маршрут. Требуется составить такое назначение направлений, что юы получить максимальную прибыль. Переменные – Гулиевы вектора (вектора, принимающие 0 или 1).
Задачи ЛП называются задачи целочисленного ЛП (ЦЛП), если на переменные задачи положено условие целочисленности.
А) полностью целочисленная задача
Б) частично целочисленная задача
Разница, проявляемая в методах решения.
Методы решения трудоемки и существенно зависят от размерности задачи.
1. методом сечения Гомори.
1-ый алгоритм Гомори, аддитивный.
Идея: симплекс методом решается ослабленная задача (без условия целочисленности), затем подбираются дополнительные линейные ограничения, обеспечивающие за конечное число шагов, получение оптимального целочисленного решения, либо установление его отсутствия.
Геометрическая интерпретация: множество точек с целочисленными координатами полностью допустимых реш. заменяют на их выпуклую оболочку и применяя затем симплекс – метод к видоизмененной задаче получают опорное решение с целочисленными координатами, но из-за трудности построения оболочки «строятся» промежуточный многогранник, содержащий всю целочисленную оболочку, но угловые точки которого содержат хотя бы одну целочисленную компоненту. Такое построение осуществляется путем введения на каждом шаге дополнительного линейного ограничения, которое уменьшает исходный многогранник путем отсечения от него некоторой его части., не содержащий целочисленных ограничений. Кроме того ограничения строятся так что его плоскость проходит хотя бы через одну точку, имеющую хотя бы одно целочисленную компоненту.