Основные результаты линейного программирования

Стандартная форма задач линейного программирования

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

Правила перевода к стандартной форме следующие.

1) Максимизация целевой функции

Z=c₁X₁+c₂X₂+...+c_nX_n

равносильна минимизации функции

Zⁱ= –c₁X₁–c₂X₂–...–c_nX_n.

2) Ограничения в виде неравенств, например X₁+X₂-X₃≤ 6, могут быть приведены к стандартной форме X₁+X₂-X₃+X₄= 6, где новая переменная X₄ неотрицательна.

3) Если некоторая переменная X_k может принимать любые значения, а требуется, чтобы она была неотрицательна, то ее можно привести в виду X_k=X_k*–X_k**, где X_k*≥0, X_k**≥0. Таким образом, приведение задачи к стандартной форме может потребовать дополнительных неотрицательных переменных.

Исходя из вышесказанного, упражнение № 7, который мы рассмотрели ранее, может быть приведен к следующему виду: минимизировать функцию Z= 2X₁–4X₂ при ограничениях

3X₁+4X₂+X₃ =1700,

2X₁+5X₂ +X₄=1600

X_i>=0, i=1,2,...,4.

Задача состоит из двух уравнений с четырьмя неизвестными. Любое неотрицательное решение при этих ограничениях является допустимым. Интересными решениями таких уравнений являются такие, когда два неизвестных приравниваются нулю. Если такое решение единственное, оно называется БАЗИСНЫМ. Если оно также и допустимое – это БАЗИСНОЕ ДОПУСТИМОЕ РЕШЕНИЕ. Для общей задачи линейного программирования с N переменными и M уравнениями (N>M), базисные решения ограничений могут быть получены, если приравнять нулю (N–M) переменных. Эти переменные получили название небазисных переменнных. Остальные переменные образуют БАЗИС.

В рассмотренной задаче возможны 6 комбинаций небазисных переменных (табл. 11).

Таблица 11

№	Значения переменных	Точки многоугольника
X1	X2	X3	X4
					O
				–525
					A
	566,7			466,7	C
			–700
					B

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

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

1. Если ограничения имеют допустимые решения, то они имеют и базисное решение.

2. Допустимая область является выпуклым множеством.

3. Базисные допустимые решения соответствуют вершинам выпуклого множества.

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

3.5. Симплекс – метод при заданном допустимом базисном решении

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

Рассмотрим сначала алгоритм решения задач подобного типа на примере, а затем сформулируем общие закономерности.

Повторим условия упражнения №7: максимизировать функцию Z=2 X₁ +4 X₂ при ограничениях: X₁ ≥0, X₂ ≥0,3 X₁ +4 X₂ ≤1700, X₁ +5 X₂ ≤1600.

В стандартной форме с неотрицательными дополнительными переменными X₃ и X₄ ограничения и целевая функция принимают вид

3X₁+4X₂+X₃ =1700, (34)

2X₁+5X₂ +X₄ =1600, (35)

–2X₁–4X₂ =Z. (36)

Очевидно, что набор X₁ = X₂ =0, X₃ =1700, X₄ =1600 образует базисное решение. Функция Z, имеющая нулевое значение, выражается через небазисные переменные, которые также имеют нулевые значения. Зададим себе вопрос, каким образом можно уменьшить значение функции Z? Поскольку в уравнении целевой функции коэффициенты при X₁ и X₂ отрицательны, а сами X₁ и X₂ должны быть неотрицательны по ограничениям, то любое увеличение значений X₁ и X₂ будет приводить к уменьшению функции Z. Для упрощения алгоритма решения задачи увеличивается значение только одной из переменных. В качестве таковой может выступать любая, но предпочтение следует отдавать переменной с большим по модулю коэффициентом, то есть переменной X₂. Однако, при увеличении значения X₂ будут изменяться значения X₃ и X₄ в силу необходимости выполнения ограничений (34-36). Все переменные должны оставаться неотрицательными. Таким образом, существует предел увеличения X₂. Поскольку 3X₁+4X₂+X₃ =1700, X₃ обращается в ноль при X₂ =1700/4=425 (напоминаем, что X₁ =0). Из (35) X₄ =0 при X₂ =1600/5=320. Таким образом, X₂ не может увеличиваться сверх 320, в противном случае переменные приобретают отрицательные значения.

Проведем ряд преобразований с уравнениями (34)-(36). Цель преобразований – сделать переменную X₂ базисной с коэффициентом единица в уравнении (35) и исключив переменную из всех остальных уравнений.

Разделив (35) на 5, получим

2/5 X₁ + X₂ +1/5 X₄ =320 (37)

Если теперь умножить (37) на 4 и вычесть результат из (34), получим

7/5 X₁ + X₃ –4/5 X₄ =420.

Если теперь (37) умножить на (–4) и вычесть результат из выражения целевой функции (36), получим

–2/5 X₁ +4/5 X₄ = Z +1280.

Таким образом, ограничения и целевая функция принимают вид

7/5 X₁ + X₃ –4/5 X₄ =420, (38)

2/5 X₁ + X₂ +1/5 X₄ =320, (39)

–2/5 X₁ +4/5 X₄ = Z +1280. (40)

Переменная X₂ исключена отовсюду, кроме (39), куда она входит с коэффициентом единица, что является канонической формой для базиса X₂ и X₃, представляющего базисное допустимое решение. Небазисными переменными в каноноческом виде стали X₁ и X₄. В данном случае их можно приравнять нулю. Теперь значение целевой функции можно уменьшить, увеличивая только X₁. Для ограничения (38) X₃ =0 при X₁ =300; для ограничения (39) X₂ =0 при X₁ =800. Исходя из этого, максимальное увеличение X₁ составляет 300.

Разделив (38) на коэффициент при X₁=7/5, получим

X₁+5/7X₃–4/7X₄=300. (41)

Теперь исключим X₁ из другого ограничения и целевой функции, вычитая выражение (41), умноженное на 2/5 и минус 2/5, из соответствующих ограничений, получим каноническую форму задачи для базиса X₁ и X₂:

X₁ +5/7 X₃ – 4/7 X₄ =300,

X₂ –2/7 X₃ + 3/7 X₄ =200, (42)

2/7 X₃ + 4/7 X₄ = Z +1400.

Дальнейшее увеличение X₃ и X₄ не приведет к снижению целевой функции и при X₃=X₄ =0 функция Z имеет минимальное значение –1400 при допустимом базисном решении X₁ =300; X₂ =320.

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

Таблица 12

Итерация	Базис	Значение	X1	X2	X3	X4
	X3 X4			5^0	*	*
–Z		–2	–4	*	*
	X3 X2		7/5^0 2/5	*	*	–4/5 1/5
–Z		–2/5	*	*	4/5
	X1 X2		*	*	5/7 –2/5	–4/7 3/7
–Z		*	*	3/7	4/7

Примечание. Знаком [⁰] в таблице отмечены коэффициенты, которые на очередной итерации собираемся обратить в базисные переменные; знаком [*] отмечены переменные, которые должны иметь нулевое значения в отличии от тех, которые обращаются в ноль при проведении преобразований.

Дата добавления: 2014-01-07