Двойственные задачи линейного программирования

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

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

Математическая модель ЗЛП :

1.Максимум или минимум целевой функции(критерий оптимальности).

2.Система ограничений в форме линейных уравнений и неравенств.

3.Неотрицательность переменных.

Решение, удовлетворяющее системе ограничений и требованиям неотрицательности решений является допустимым, а решения, удовлетворяющие одновременно с этим и условиям min/max являются оптимизированными.

Общий вид ЗЛП

Max(min)F(x)=c1x1+c2x2+…cnxn

A11x1+a12x2+…a1nxn<=b1

A21x1+a22x2+…a2nxn<=b2

…

Am1x1+am2x2+…amnxn<=bnm, x1,x2,…xn>=0

Свойства ЗЛП:

1.Допустимое множество решений ЗЛП либо пустое, либо является выпуклым многогранником.

2.Если допустимое множество не пустое, а целевая функция ограничена сверху для максимизации, а снизу – для минимизации, то она имеет оптимальное решение.

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

Графический метод решения ЗЛП

Если число неизвестных равно 2, то ее можно решить графическим методом. Найти решение X=(x1,x2)? Удовлетворяющее условию max(min)z=c1x1+c2x2. При ограничениях сумм j от 1 до n (aij*xj)<=bj, x1, x2 >=0.

Каждое из неравенств 2 определяет на координатной плоскости полуплоскость, а система неравенств 2 и 3 в случае ее совместимости – пересечение плоскостей. Это будет выпуклое множество, которое может быть представлено как:

1.Выпуклый многоугольник.

2.Выпуклая неограниченная многоугольная область.

3.Отрезок.

4.Луч.

5.Одна точка.

6.Пустое множество.

Геометрическая интерпретация целевой функции:

Z=C₁X₁+C₂X₂ (1)

При фиксированных значениях Z=Z₀определяет линию z0=c1x1+c2x.

При изменении Z получим семейство параллельных прямых, называемых линиями уровня.

Вектор С=(С₁, С₂) с координатами при x1 и x2 перпендикулярен каждой из линий уровня.

Вектор С показывает направления наибольшего возрастания (убывания) целевой функции.

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

1.Задача имеет единственное решение.

2.Задача имеет бесконечное множество решений(альтернативный оптимум).

3.Целевая функция не ограничена, область допустимых решений – единственная точка(рис. 1).

Симплекс-метод

Построение начального опорного плана

Рассмотрим 3 случая.

1) Пусть система ограничений имеет вид

X_i+ _ijX_j=b_i, b_i=>0,(i=1,m)

X₀=(0,0,…,0,b_i)

Z(x0)=0.

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

_ijX_j<=b_i, b_i>=0

X_n+i>=0

Дополнительную переменную вводят с коэффициентом равным 0

_ijX_j+X_n+1=b_i, b_i>=0

X₀=(0,…,0,b₁,...,b_m)

_ijX_j>=b_i, b_i>=0

_ijX_j-X_n+i=b_i

M-задача

Max(min)Z= _jX_j-(+)M _i

Симплексные таблицы

Признак оптимальности опорного плана. Задача максимизации

Если для некоторого опорного плана все оценки dj неотрицательны, то такой план оптимален. Если же исходная задача на минимум и dj не положительны, то такой план оптимален.

Рассмотрим переход к нехудшему опорному плану на примере задачи ЛП на макс.

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

Max|dj|=|dj₀|

Если задача на минимум, то разрешающий столбец Max|dj|=|dj₀|

Переменную Xj_0,следует ввести в базис. Для определения переменной , выводимой из базиса, находят отношения: B_i/A_ij , A_ij >0

Min = B_i₀/A_i₀_j₀

НА пересечении разрешающей строки и разреш столбца находиться разр элемент.

1.Элементы строки I₀ новой таблицы равны соответствующим элементам разрешающей строки предыдущей таблицы деленной на разреш элемент.

2.Все элементы столбцы J₀ равны 0, за исключением разрешающего элемента.

3.Все остальные элементы новой таблицы высчитываются по правилу: произведение главной диагонали минус произведение побочной диагонали деленной на разрешающий элемент.

Три признака:

1.Альтернативный оптимум (признак бесконечности множества оптимальных планов). Если в индексной строке последней симплексной таблицы (содержащей оптимальный план) имеется хотя бы одна нулевая оценка, соответствующая свободной переменной, то задача ЛП имеет бесконечное множество оптимальных планов.

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

3.Признак несовместности системы ограничений. Если в оптимальном плане М-задачи не все искусственные переменные равны 0, то система ограничений исходной задачи несовместна.

Двойственные задачи линейного программирования

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

Прямая - maxZ = Xj>=0

Двойственная minZ = Xj>=0

Пара двойственных задач может быть экономически интерпретирована:

Прямая – Сколько и какой продукции Xj надо произвести чтобы при заданных стоимостях единицы продукции Cj объемах ресурсов Bi и нормах расхода Aij максимизироваит выпуск продукции в стоимостном выражениии.

Двойственная – Какова должна быть оценка единицы каждого из ресурсов чтобы при заданных Bi Cj Aij минимизировать общую оценку затрат на все ресурсы.

Правила построения :

1.Упорядочивается запись исходной задачи, т.е. если целевая функция задачи максимизируется, то ограничения неравенства должны быть > или =(для минимиз < или =) Достигается умножением ограничений на -1.

2.Если прямая задача решается на максимум, то двойственная на минимум.

3.Каждому ограничению прямой задачи соответствует переменная двойственной задачи и наоборот.

4.Матрица системы ограничений двойственной задачи получается из матрицы системы ограничений прямой задачи путем транспонирования.

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

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

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

Транспортная задача

Представим транспортную задачу по критерию стоимости в виде таблицы

Поставщики	ПОТРЕБИТЕЛИ	Запас груза
B₁	B₂	…	B_n
А₁	X₁₁c₁₁	X₁₂c₁₂	…	X_1nc_1n	a₁
…	…				…
А_m	…				a_n
Потребность в грузе	b₁

В таблице указаны поставщики А1… , у которых имеется в наличии соответственно а₁… единиц однородного груза. Данный груз должен быть доставлен n потребителям, в количествах в₁… единиц, заданы стоимости с_ij перевозок груза от i поставщика j потребителю. Требуется спланировать перевозки(указать, сколько единиц груза должно быть отправлено от I того поставщика j потребителю, так чтобы максимально удовлетворить спрос потребителя и чтобы суммарные затрата на перевозки были при этом минимальными).

c₁– цена.

Задачи, где суммарные запасы грузов поставщиков равны суммарным потребностям, называются закрытыми.

_I != _I – то задача открытая.

При решении транспортных задач важное значение имеет теорема о ранге матрицы:

Ранг матрицы транспортной задачи на 1 меньше числа уравнений(r=m+n-1).

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

1.Определение исходного опорного плана.

2.Оценка этого плана.

3.Переход к следующему плану путем однократной замены одной из базисных переменных на свободную.

Существуют различные способы реализации этапов решения транспортной задачи:

- правило северо-западного угла

- правило минимального элемента

- метод Фогеля4

- метод потенциалов

Метод потенциалов

Перейдем к построению оптимального плана перевозок. По данному опорному плану, у которого число занятых клеток m+n-1. Каждому поставщику и каждому потребителю передается число, называемое потенциалом. Потенциалы выбираются так, чтобы их сумма для каждой загруженной грузом клетки была равна тарифу перевозки единицы груза. Так если клетка (I,k) – базисная(занятая), то u_i +v_k=C_ik где у итое потенциал итого поставщика.

Тогда вычисляем оценки свободных клеток по формуле: S_ij=C_ij-(U_i+V_j)

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