Курс лекций по линейному программированию

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

- Симметричные  данные выше

- Несимметричные:

Соответствие  между прямой и двойственной задачами

Теорема № 1 двойственности

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

1. прямая и двойственная задачи имеют оитимальное решение, то значение их целевых функций на соотвующее оптимальное решение совпадают.
2. Целевая функция прямой задачи неограниченна сверху на непустом множестве планов, то двойственная задача имеет пустое множество допустимых решений.
3. Прямая и двойственная задачи могут иметь пустое множество допустимых решение
4. Если множество допустимых решений одной из двойственных задач пусто, то целевая функция другой задачи неограниченна.

 

Лемма: для любых  планов X и Y прямой и двойственной задач соответственно (прямая на максимум; двойственная на минимум) имеет место z(x)≤F(x), где z – целевая функция прямой, а F – целевая функция двойственной. 

Теорема № 2 двойственности

Пусть х^*=(х^*₁, …, х^*_n) и y^*=(y^*₁, …, y^*_m) – допустимые решения прямой и двойственной задач, соответственно. Для того чтобы x^* и y^* были оптимальными решениями необходимо и достаточно выполнение следующих условий:

1.)

2.)

Условия 1 и 2 позволяют, зная оптимальное решение одной  из задач, найти решение другой. На основании второй теоремы двойственности, формулируется критерии  оптимальности для допустимого решения задач.

Теорема:

Пусть х₁^*- допустимое решение прямой задачи, то вектор х^* является оптимальным решением прямой задачи в том и только в том случае, когда среди решений уравнения 1 при x_j^*≠0 найдётся хотя бы одно допустимое решение двойственной задачи и y_i^*=0 при выполнении условия

y_i – это не цены, это оценка цен, т.к. если ресурс дефицитные (полностью используется в производстве) то оценка совпадает с ценой, а если ресурс не дефицитный, то оценка = 0. 

Нахождение решения  двойственной задачи по таблице оптимального решения прямой. 

Пусть найдено  оптимальное решение прямой задачи х^*, которая определенна системой базисных векторов А_i, …, A_im через С_б обознач. вектор, состоящий из коэффициентов целевой функции при базисных переменных оптимального решения. Через Р^-1 обозначают матрицу, обратную матрице Р, составленную из компонент векторов А_i, …, A_im оптимального базиса. 

Теорема:

Если прямая задача имеет оптимальный план х*, то оптимальный план двойственной задачи y*=C_Б^.Р^-1. Решение двойственной задачи находится в симплексной таблице оптимального решения прямой на пересечении индексной строки и векторов столбцов исходного базиса прямой. 

Экономическая интерпретация.

Пусть имеются  m видов ресурсов, количества b₁, … ,b_m. На основе  этих ресурсов предполагают выпускать продукцию n различными способами, при этом за единицу времени применение j-ого способа расходуется а_ij единиц i-ого вида ресурсов, а выпускаемая, при этом, продукция имеет ценность ij. Как оценить имеющиеся ресурсы?

Пусть х=(х₁, … ,х_n) – вектор, компоненты которого – времена использования j-ого способа производства, то x_j≥0 ∑а_ijx_j≤b_i, если y_i – оценка ресурсов, используемых в единицу времени при j-ом способе производства.

Эта величина не может быть меньше ценности выпускаемой при тех же условиях продукции, то для любых х и у ценность всей выпускаемой продукции не превосходит суммарной оценки имеющихся ресурсовю

Z(x)≤F(Y)

Величина Δху=F(Y) – Z(X) характеризует потери в зависимости от плана х и выбранных ресурсных оценок у = > х и у надо выбирать так, чтобы величина потерь была наименьшей, а для этого достаточно план подобрать так, чтобы z(x) было как можно больше, а F(y) – как можно меньше. Отсюда возникает пара симметричных двойственных задач.

Из теоремы 1 двойственности следует, что оптимальному вектору оценок и оптимальному плану производства соответствуют нулевые производственные потери.

Из теоремы 2 двойственности следует, что если х*, у* - оптимальные решения прямой и двойственной задач соответственно, то справедливо соотношение:

Условие (*) интерпретируется: если оценка i-ого вида ресурса положительна в оптимальном плане, то ресурс используется полностью, если ресурс используется не полностью, то его оценка = 0.

Условие (**): если производство j-ого вида продукции включено в оптимальный план, то он в оптимальной оценке неубыточен. Если он убыточен (затратная оценка превосходит цену реализации) то этот продукт не производится в оптимальном плане.

∑a_ijy_i – затратная оценка производства единицы j-ого вида продукции. 

Лекция № 3: «Целочисленное программирование».

Примеры, показывающие необходимость применения целочисленных  методов.

Задача о расписании (назначении).

Есть 3 самолета и 15 маршрутов. Известны затраты и прибыль от посылки каждого самолета на каждый маршрут. Требуется составить такое назначение направлений, что юы получить максимальную прибыль. Переменные – Гулиевы вектора (вектора, принимающие 0 или 1).

Задачи ЛП называются задачи целочисленного ЛП (ЦЛП), если на переменные задачи положено условие целочисленности.

А) полностью  целочисленная задача

Б) частично целочисленная  задача 

Разница, проявляемая  в методах решения.

Методы решения  трудоемки и существенно зависят  от размерности задачи. 

1. методом сечения  Гомори.

1-ый алгоритм  Гомори, аддитивный.

Идея: симплекс методом решается ослабленная задача (без условия целочисленности), затем  подбираются дополнительные линейные ограничения, обеспечивающие за конечное число шагов, получение оптимального целочисленного решения, либо установление его отсутствия.

Геометрическая  интерпретация: множество точек  с целочисленными координатами полностью  допустимых реш. заменяют на их выпуклую оболочку и применяя затем симплекс – метод к видоизмененной задаче получают опорное решение с целочисленными координатами, но из-за трудности построения оболочки «строятся» промежуточный многогранник, содержащий всю целочисленную оболочку, но угловые точки которого содержат хотя бы одну целочисленную компоненту. Такое построение осуществляется путем введения на каждом шаге дополнительного линейного ограничения, которое уменьшает исходный многогранник путем отсечения от него некоторой его части., не содержащий целочисленных ограничений. Кроме того ограничения строятся так что его плоскость проходит хотя бы через одну точку, имеющую хотя бы одно целочисленную компоненту.

Через конечное число шагов данный метод приводит к новой задаче, оптимальное решение  которой является оптимальным целочисленным  решением.

Пусть а- действительное число. Число [a] – целая часть числа а – это наибольшее целое, не превосходящее данного числа.

q_a- дробная часть числа – это разность между числом и его целой частью а-[a] 0≤q_a<1

основой метода является понятие правильного отсечения. Пусть х* - оптимальный план ослабленной задачи, который не является целочисленным. Неравенство αх≤β называется правильным отсечением или отсечением Гомори, если оно удовлетворяет условиям:

1. условие отсечения. Если х* оптимальный не целочисленный план, то он не удовлетворяет этому ограничению αх*>β
2. условие правильности. Для любого целочисленного плана х* αх*≤β
3. необходимое условие применения аддитивного компонента является целочисленность в системе ограничений элементов правых частей. Оно не выполняется если иррациональное или трансцендентное.

Алгоритм:

1. решается ослабленная задача. Если оптимальный план целочисленный , то он является решением целочисленной задачи, иначе переходим к шагу 2.
2. вводятся дополнительные линейные ограничения – правильное отсечение. Переходим к шагу 1, решая ослабленную задачу с дополнительными ограничениями.

 

Условие неразрешимости целочисленной задачи.

Задача не разрешима, если для дробного значения переменной задачи х_j все коэффициенты а_ij в данной строке симплекс – таблицы оптимального решения ослабленной задачи окажутся целыми. 

Схема алгоритма.

Пусть при решении  задачи получился оптимальный план, имеющий хотя бы 1 нецелочисленную  компоненту, тогда в симплекс – таблице оптимального решения выбираются значения базисной переменной задачи в наибольшей дробной частью. Если таких переменных несколько, то выбирается любая.

Этой переменной соответствует строка таблицы, называемая строкой производящей отсечение. Выписывается уравнение:

Т.к. коэффициенты целевой функции – целые числа, то значения целевой функции на целочисленном решении тоже должно быть целым. Представим каждый коэффициент строки в виде суммы целых и дробных частей, получим:

х_j^* = [x_j^*] + q_j     0<q_j<1

a_ij = [a_ij] + q_ij      0≤q_ij<1

переносим все  целые части коэффициентов в одну сторону, оставляя все дробные в другой.

x_j – [x_j] + ∑[q_ij]x_j=q_j+∑q_ijx_j

т.к. переменные x_m+1, … , x_n, принимают целочисленные значения, то правая часть уравнения является целочисленной, следовательно, в силу не отрицательности дробных частей и переменных задачи, получаем:

q_i+∑a_ijx_j≥0, => q_i-∑a_ijx_j≤q_j,

т.к. q_j<1, то заменяем в правой части q_j на 1 и получает неравенство q_i-∑a_ijx_j≤1

т.к. левая часть  неравенства должна принимать целые  значения, то необходимое условие  её целочисленности записывается в виде:

q_i-∑q_ij<1

Вводя остаточною переменную S_j получим выражение для переменной Гомори S_j.

q_j-∑q_ijx_j+S_j=0,