Графический метод решения задачи линейной оптимизации

Графический метод решения ЗЛП состоит из следующих этапов.

1. Строится область допустимых решений (ОДР) ЗЛП.

2. Строится вектор-градиент целевой функции в какой-нибудь точке Х_0, принадлежащей ОДР – .

3. Линия уровня C₁x₁+C₂x₂ = а (а – постоянная величина) - прямая, перпендикулярная вектору–градиенту – передвигается в направлении этого вектора в случае максимизации f(x_1,x₂) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точкой максимума f(x_1,x₂).

4. Для нахождения ее координат достаточно решить систему из двух уравнений прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение f(x_1,x₂), найденное в полученной точке, является максимальным.

При минимизации f(x_1,x₂) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая при своем движении не покидает ОДР, то соответствующий максимум или минимум f(x_1,x₂) не существует.

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

Пример. Для изготовления двух видов продукции А₁ и А₂ используют три вида ресурсов S₁, S₂, S₃, запасы которых составляют 18, 16 и 5 усл. ед. соответственно. Расход ресурсов на 1 ед. продукции приведен в таблице:

Виды ресурсов	Запасы ресурсов	Расходы ресурсов на 1 изд.
А1	А2
S1	18	1	3
S2	16	2	1
S3	5	-	1
	Прибыль	2 руб.	3 руб.

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

Решение. Составим экономико-математическую модель задачи.

Пусть надо выпустить изделий A₁ - x₁ шт., а изделий А₂ - x₂ шт. Тогда прибыль от реализации составит 2x₁ + 3x₂ и она должна быть максимальной. Получим целевую функцию: F=2x₁ + 3x₂→ max.

На одно изделие А₁ затрачивается 1 усл. ед. ресурса S₁, тогда на x₁ шт. затратится x₁ усл. ед. На одно изделие А₂ затрачивается 3 усл. ед. ресурса S₁, тогда на x₂ шт. затратится 3 x₂ усл. ед. На оба изделия затратится x₁+ 3 x₂ усл. ед. ресурса S₁. Так как всего в наличие 18 усл. ед., то получим первое ограничение: x₁ + 3x₂ £18. Аналогично получим остальные ограничения.

Запишем модель: найти максимальное значение функции F=2x₁ + 3x₂ при условиях

x1 + 3x2 £	18
2x1 + x2 £	16
x2 £	5
x1 ³ 0,	x2 ³ 0

Построим область допустимых значений:

1) первое ограничение по ресурсу S₁ x₁ + 3x₂ £ 18; прямая x₁ + 3x₂ = 18 проходит через точки (0; 6) (18; 0); неравенству соответствует полуплоскость, содержащая данную прямую и лежащая ниже неё (контрольная точка (0; 0), 0 + 3*0 < 18 принадлежит полуплоскости);

2) второе ограничение по ресурсу S₂ 2x₁ + x₂ £ 16: прямая 2x₁ + x₂ = 16 проходит через точки (0; 16) (8; 0); неравенству соответствует полуплоскость, содержащая данную прямую и лежащая ниже неё (контрольная точка (0; 0), 2*0 + 0 < 16 принадлежит полуплоскости);

3) неравенству x₂ £ 5 соответствует полуплоскость, содержащая прямую x₂ = 5 и лежащая ниже неё.

4) x₁ ³ 0 - правее ОX₂;

5) x₂ ³ 0 - выше ОX₁.

Рис. 1.

Вектор-градиент имеет координаты 

Построим линии уровня 2x₁ + 3 x₂ = а. При а = 0 получим прямую 2x₁ + 3x₂ = 0, проходящую через точки (0; 0) (3; -2). Так как задача на максимум, то передвигаем линию уровня в направлении градиента. Предельной точкой (последней из области допустимых решений, с которой соприкасается линия уровня) является точка С. Значит, в ней достигается максимум функции F.

Найдём её координаты. Для этого решим систему:

Таким образом, необходимо выпустить 6 шт. изделий А₁, 4 шт. изделий А₂, чтобы получить прибыль 24 ден.ед.

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

Для решения ЗЛП существует универсальный метод – метод последовательного улучшения плана или симплекс-метод, который состоит из двух вычислительных процедур: симплекс-метода с естественным базисом и симплекс-метода с искусственным базисом (М-метод).

Выбор конкретной вычислительной процедуры осуществляется после приведения исходной ЗЛП к каноническому виду.

Для применения симплекс-метода с естественным базисом ЗЛП должна содержать единичную подматрицу размером mxm – в этом случае очевиден начальный опорный план.

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

Базис	Сб	Р0	с1	с2	...	сm	cm+1	...	cn
Р1	Р2	...	Рm	Рm+1	...	Рn
Р1	с1	b1			...		a1m+1	...	a1n
Р2	с2	b2			...		a2m+1	...	a2n
...	...	...	...	...		...	...	...
Рm	сm	bm			...		amm+1	...	amn
		F0					Δm+1		Δn

В первом столбце таблицы "Базис" записывают базисные векторы данного опорного плана. Во втором столбце - коэффициенты целевой функции (с₁, с_2,…, с_m) при базисных переменных (напомним, что в базис входят только векторы, образующую единичную подматрицу). В третьем столбце Р₀ - правая часть ограничений задачи (базисные компоненты плана). Таким образом, перемножая элементы второго столбца таблицы со столбцом Р₀, и суммируя эти произведения, мы получаем значение целевой функции (F₀=с₁*b₁ + с₂*b₂+…+ с_m*b_m).

Первая строка симплексной таблицы содержит коэффициенты целевой функции нашей задачи и остается неизменной на протяжении всего решения (с₁, с_2,…, с_m).

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

После заполнения таблицы исходный опорный план проверяют на оптимальность. Для этого просматривают элементы последней (оценочной) строки. Возможны три варианта:

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

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

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

Переход от одного опорного плана к другому осуществляется исключением из исходного базиса какого-нибудь из векторов и введением в него нового вектора. В качестве вводимого в базис вектора берётся один из векторов, для которых . Пусть это будет вектор Р_k.

Для определения вектора, подлежащего исключению из базиса находят . Тогда выполняется условие неотрицательности значений опорного плана. Пусть этот минимум достигается при i=r. Тогда из базиса исключают вектор Р_r, а число называют разрешающим элементом.

Элементы новой симплекс-таблицы получают методом Жордана-Гаусса по формулам:

для i = r;

.

Значения нового опорного плана рассчитываются по формулам:

для i = r;

.

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

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

Метод искусственного базиса заключается в том, что для получения единичной подматрицы коэффициентов мы вводим в исходную задачу неотрицательные так называемые искусственные переменные и включаем их в целевую функцию с коэффициентом +М для задачи минимизации и с коэффициентом –М для задачи максимизации, где М>0 – сколь угодно большое число. Полученная задача называется расширенной по отношению к исходной. Искусственные переменные образуют начальное базисное решение. Применив симплекс-метод, необходимо вывести из базиса все искусственные переменные. Если удается доказать (или показать), что искусственные переменные полностью вывести из базиса невозможно, то это означает, что задача не имеет решения, то есть ее ограничения противоречивы.

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

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

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

Исходная задача	Двойственная задача

Две приведенные задачи образуют двойственную пару.

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

1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи — на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид "£", в задаче на минимум — вид "³";

2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи и аналогичная матрица А^т в двойственной задаче получаются друг из друга транспонированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи — числу переменных в исходной задаче;

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

5) если переменная x_j исходной задачи может принимать только положительные значения, то j -ое условие в системе ограничений двойственной задачи является неравенством вида "≥". Если же переменная может принимать как положительные, так и отрицательные значения, то j -ое условие представляет собой уравнение. И наоборот, если i -ое соотношение в системе ограничений исходной задачи является неравенством, то i -ая переменная двойственной задачи y_i. В противном случае переменная y_i может принимать как положительные, так и отрицательные значения.

В теории двойственности используются четыре пары двойственных задач (приведем их в матричной форме записи):

Исходная задача	Двойственная задача
Симметричные пары
1.	1.
2.	2.
Несимметричные пары
3.	3.
4.	4.

Первая теорема двойственности.

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

Если же целевая функция одной из пары двойственных задач не ограничена (для исходной – сверху, для двойственной – снизу), то другая задача вообще не имеет планов.

Вторая теорема двойственности.

План исходной задачи и план двойственной задачи являются оптимальными планами этих задач тогда и только тогда, когда для любых i и j выполняются равенства:

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

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

Пример. а) составить для данной задачи линейного программирования двойственную задачу; б) решить исходную задачу симплексным методом; в) по решению исходной найти решение двойственной задачи.

Решение

а) Число переменных в двойственной задаче равно числу уравнений в системе, т. е. 3. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений, т. е. 6, 24, 30. Коэффициенты целевой функции исходной задачи являются свободными членами двойственной.

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

б) Приведем задачу к каноническому виду. Для этого в левую часть первого неравенства вводим дополнительную переменную с коэффициентом +1. В целевую функцию переменная входит с коэффициентом 0 (т. е. не входит). Получаем

Преобразованную систему уравнений запишем в векторной форме:

,

где ; ; ; ; ; ; .

Поскольку среди векторов P₁, P₂, P₃, P₄, P₅, P₆ имеются три единичных вектора, для данной задачи можно непосредственно записать опорный план. Таковым является с единичным базисом .

Составим симплексную таблицу для I итерации:

Б
				-2	2				6	3
					-4					-
	F0=132	-2		-9

Вычислим оценки разложений векторов по базису опорного решения по формуле , где z_j находится как скалярное произведение вектора P_j (j=1,m) на вектор С_б=(с₁, с₂,...,с_m):

Оценки векторов, входящих в базис, всегда равны нулю.

Значение F₀ равно скалярному произведению вектора P₀ на вектор С_б: F₀ =6*0+24*3+30*2=132.

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

Чтобы перейти к новому опорному решению, в базис можно ввести любой из векторов P₁ и P₃. Для определения вектора, подлежащего выводу из базиса, находят для всех a_ij>0.

Для вектора P₁ получим , для вектора P₃ получим (в таблице записаны в двух последних столбцах).

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

Далее выполним преобразование Жордана с элементом =2: 1) разделим всю 1-ю строку на 2 (на месте элемента получим 1) и запишем её в новую симплексную таблицу; 2) остальные элементы столбца нужно «занулить», для этого полученную 1-ю строку сначала умножим на -1 и сложим со второй, результат запишем во вторую строку новой симплексной таблицы, а затем умножим на 4 и сложим с третьей строкой, результат запишем в третью строку новой симплексной таблицы.

Получим симплексную таблицу для II итерации.

Б
			1/2	-1				1/2	-
			1/2	3				-1/2
				-3					-
		5/2	-6				9/2

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

Определим номер вектора, выводимого из базиса. Для этого вычислим параметр для второго столбца, он равен 7. Следовательно, из базиса выводим вектор . Выполним преобразование Жордана с элементом =3:

Б
			2/3			1/3		1/3
			1/6			1/3		-1/6
			9/2					3/2
		7/2					7/2

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

.

Ответ: при .

в) Оптимальное решение двойственной задачи находим по формуле:

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

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

Пусть имеется m поставщиков А₁, А₂,..., А_m однородного груза в количествах соответственно а₁, а₂,..,.а_m единиц и n потребителей В₁, В₂,..., В_n этого груза, потребность которых составляет соответственно b₁, b₂..., b_n единиц.

Известны стоимости перевозок (тариф) единицы груза от i -го поставщика к j -му потребителю - с_ij (i=1,m; j=1,n).

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

Возможны три ситуации:

1) количество груза у всех поставщиков равно потребности в данном грузе всех потребителей:

или .

2) количество груза у всех поставщиков больше потребности в данном грузе всех потребителей:

или .

3) количество груза у всех поставщиков меньше потребности в данном грузе всех потребителей:

или .

В первом случае модель задачи называется закрытой, во втором и третьем – открытой.

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

В случае превышения запаса над потребностью вводится фиктивный (n + 1)-й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю.

Аналогично вводится фиктивный (m + 1)-й пункт отправления с запасом груза и тарифы полагаются равными нулю. Этим задача сводится к закрытой транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи.

Решение транспортной задачи включает следующие этапы:

1. Нахождение первоначального опорного плана (метод северо-западного угла, метод минимальной стоимости). При этом число заполненных клеток должно быть равно m+n-1.

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

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

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

2. Проверка опорного плана на оптимальность, например, методом потенциалов.

Пример. Четыре предприятия используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырьё сосредоточено в трёх пунктах, а запасы соответственно равны 160, 140 и 170 ед. Тарифы перевозок заданы матрицей

.

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Исходные данные задачи запишем в виде таблицы, а опорный план получим методом минимального элемента.

Минимальный тариф, равный 1, находится в клетке (1,3).

х₁₃ = min(A1,B3)=A1=160.

Запишем это значение в соответствующую клетку и временно исключим из рассмотрения строку А1.

Теперь потребности пункта B3 считаем равными 190-160=30 ед. В оставшейся части таблицы наименьший тариф находится в клетке (3,2) и равен 2.

х₃₂ = min(A3,B2)=B2=50.

Внесём значение в соответствующую клетку и исключим из рассмотрения столбец B2.

Запасы пункта А3 считаем равными 170-50=120 ед.

В оставшейся части (строки А2, А3 и столбцы В1, В3, В4) минимальный тариф равен 3 и находится в клетке (3,3).

х₃₃ = min(A3,B3)=В3=30.

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

Потребности   Запасы	B1=120	B2=50	B3=190	B4=110
β1=2	β2=2	β3=3	β4=6
A1=160	α1=-2			1 160
A2=140	α2=2	4 120			8 20
A3=170	α3=0		2 50	3 30	6 90

Число заполненных клеток равно 6 и m+n-1=3+4-1=6 – план невырожденный.

Оптимальный план найдём методом потенциалов.

В оптимальном плане транспортной задачи заполненным клеткам отвечают равенства , а пустым – неравенства . Тогда, получим

, положим , тогда .

(Обычно равным нулю принимают потенциал строки или столбца с наибольшим числом заполненных клеток.)

Теперь проверим пустые клетки на выполнение неравенства .

Запишем систему неравенств:

.

Для клетки (1, 4) неравенство не выполняется, значит в неё нужно "ввезти" груз. Строим цикл.

Цикл перерасчёта таблицы - это последовательность ячеек, начинающаяся и заканчивающаяся в одной и той же клетке, с вершинами, лежащими в занятых клетках, кроме одной.

Вершина цикла – клетка, в которой происходит поворот под прямым углом.

"Перемещаем" груз по следующим правилам:

1. Каждой из клеток, связанных циклом присваивается знак: пустой ячейке " + ", остальным - поочерёдно знаки " - " и " + ".

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

В нашем примере цикл образуют четыре ячейки: (1,4) – пустая, для которой не выполняется неравенство, и клетки (1,3), (3,3), (3,4) – заполненные.

х = min (160, 90)=90. Значит в плюсовые клетки "завозим" 90 ед. груза, из минусовых "вывозим". Получим новый опорный план:

Потребности   Запасы	B1=120	B2=50	B3=190	B4=110
β1=0	β2=2	β3=3	β4=4
A1=160	α1=-2			1 70	2 90
A2=140	α2=4	4 120			8 20
A3=170	α3=0		2 50	3 120

Расставим потенциалы и проверим пустые клетки на выполнение неравенства :

Для клетки (2,2) неравенство не выполняется. Значит, строим цикл с вершиной в этой клетке.

х = min (50, 70, 20)=20. Значит в плюсовые клетки "завозим" 20 ед. груза, из минусовых "вывозим". Получим новый опорный план:

Потребности   Запасы	B1=120	B2=50	B3=190	B4=110
β1=1	β2=2	β3=3	β4=4
A1=160	α1=-2			1 50	2 110
A2=140	α2=3	4 120	5 20
A3=170	α3=0		2 30	3 140

Полученный план является оптимальным (неравенство выполняется для всех пустых клеток).

Ответ: ,

=50*1+110*2+120*4+20*5+30*2+140*3=1330.

Вариант № 1