Пример 2. Найти максимальное значение функции:

Найти максимальное значение функции:

F =Х₁-Х₂

При ограничениях:

-Х₁+Х₂<=2

Х₁-3Х₂ <=3

Х₁+Х₂ <=5

Х₁>=0, Х₂>=0

Решение

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

-Х₁+Х₂+ Х₃ =2

Х₁-3Х₂ +Х₃ =3

Х₁+Х₂ +Х₅=5

Таблица 1. Таблица 2

	-Х1	-Х2	С.ч.			-Х4	-Х2	С.ч
Х3	-1			Х3		-2
Х4		-3		Х1		-3
Х5				Х5	-1
F	-1			F		-2

Таблица 3. Таблица 4.

	-Х4	-Х5	С.ч.	Разделим на 4		-Х4	-Х5	С.ч
Х3				Х3	1/2	1/2
Х1				Х1	1/4	3/4	9/2
Х2	-1			Х2	-1/4	1/4	1/2
F				F	1/2	1/2

Результат Х₁=9/2, Х₂=1/2, Х₃=6, Х₄= Х₅=0

Максимальное значение F=4

Проверка:

Подставим значения переменных в исходный вид функции:

F =4,5-0,5=4

§4. Решение задачи ЛП двухфазным симплекс-методом

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

Пример 7. Следующую задачу ЛП решить двухфазным симплекс-методом:

min f(x)=x1-x2+1 (13)

при ограничениях

(14)

x₁, x₂, x₃≥0 (15)

Первая фаза (цель: при- помощи искусственного базиса и симплекс-метода определить базисные переменные из числа исходных переменных).

В систему (14) вводим искусственные переменные x₃≥0, x₅≥0, x₆≥0 (предварительно умножив обе части второго неравенства на -1), новую целевую функцию как сумму всех искусственных переменных, а старую присоединяем к ограничениям:

min z(x) = x₄ + x₅ + x₆ (16)

при ограничениях

(17)

Искусственные переменные x₄, x₅, x₆ выбираем в качестве базисных, а все остальные x₁, x₂, x₃ - небазисных. По правилу симплекс-метода исключаем базисные переменные из целевой функции (16) (при помощи уравнений системы (17), содержащих эти переменные):

z(x)= -2 x₁ - 15 x₂ - 5 x₃ + 15

или, что все равно

z(x)+2x₁+15 x₂+5 x₃=15 (19)

Начальное д.б.р.

x⁰=(x₁⁰, x₂⁰, x₃⁰, x₄⁰, x₅⁰, x₆⁰)=(0, 0, 0, 1, 3,11)

называется искусственным базисом. При помощи этого базиса, и выражений (19), (17) строим начальную симплекс-таблицу I-ой фазы.

	x1	x2	x3	x4	x5	x6
z
f		-1
x4			(1)
x5		-1		-1
x3

До конца I фазы роль нулевой строки играет строка для z, все остальное как в симплекс-методе (см. примеры 5,6). Следует только заметить, что строка для f не участвует в выборе ведущей строки.

Из (16) видно, что min z(x) = 0 и достигается при x₄= x₅ = x₆=0, те, задача (16)-(18) будет решена, если все искусственные переменные будут вытеснены из базиса, а z=0. Это и будет означать конец первой фазы и переход ко второй фазе.

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

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

В результате соответствующих преобразований получим вторую симплекс-таблицу.

	x1	x2	x3	x4	x5
z		-28		-40
f		-3		-3
x2
x5		-7		-10
x6		-21		-30

Из таблицы следует, что min z достигнут, однако искусственные переменные x₅ и x₆ еще не выведены из базиса. В такой ситуации правила симплекс-метода "не работают" (т.к. ввиду отсутствия в нулевой строке положительных оценок нельзя выбрать ведущий столбик). Задача здесь одна - вывести оставшиеся искусственные переменные из базиса. Выведем сначала x₅. Умножим все элементы этой строки на -1 (что допустимо, т.к. в нулевом столбике стоит 0). Введем в базис вместо x₅ переменную x₁. С этой целью строку для x₅ поделим на 7 и с "ведущим элементом" 1 выполним элементарные преобразования (как в симплекс-методе). В результате получим таблицу:

	x1	x2	x3	x6
z
f				9/7
x2				1/7
x1				10/7
x6

Остается в базисе еще x₆. Ее из числа базисных вывести нельзя, так как все элементы таблицы равны нулю, кроме 1 в столбике для x₆. Это говорит о том, что в системе (14) третье уравнение было "лишним" и потому последнюю строку таблицы можно вычеркнуть. Действительно, третье уравнение в (14) является линейной комбинацией первых двух (оно получается вычитанием второго уравнения, умноженного на 3, из первого уравнения, умноженного на 2),

Вычеркивая столбик для x₆ и строку для z приходим к таблице,

	x1	x2	x3
f				9/7
x2				1/7
x1				10/7

содержащей только элементы исходной задачи (13)-(15) и с базисными переменными изчисла исходных переменных.

Таким образом, задача I фазы выполнена.

Вторая фаза (цель: применяя обычный симплекс-метод к полученной в результате I фазы таблице, получить оптимальное решение исходной задачи).

Д.б.р. для последней таблицы есть

x⁰=(0, 1, 0)

Заметим, что это вырожденное д.б.р., так как в нем базисная переменная x₁ - 0. То есть здесь мы можем получить зацикливание.

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

Теперь можно привести алгоритм двухфазного симплекс-метода:

1) привести задачу ЛП к канонической форме;

2) ввести в ограничения искусственные переменные и составить новую целевую функцию z;

3) исключить из новой целевой функции все искусственные переменные;

4) используя искусственные переменные в качестве базисных, построить начальную симплекс-таблицу;

5) использовать симплекс-метод, исключая из таблиц столбики для искусственных переменных по мере их выхода из базиса до тех пор, пока min z=0 и все искусственные переменные не будут выведены из базиса;

6) вычеркнуть строчку для z и перейти ко второй фазе;

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

П р и м е ч а н и я к двухфазному симплекс-методу

1. Если в результате первой фазы окажется, что min z > 0, то система ограничений исходной задачи (в канонической форме) несовместна. Во всех остальных случаях первая фаза разрешима.

2. Если min z= 0 и в таблице остались искусственные переменные, то, используя элементарные преобразования, эти переменные следует вывести из числа базисных, а вместо них ввести исходные переменные (см. пример 7).

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

2.1.4 Задачи для закрепления полученных знаний

В задачах 1 и 2 найти оптимальные решения геометрическим и симплексным методами.

1) F(x)=x₁+2x₂àmax 2) F(x)=x₁+2x₂àmax

4x₁+3x₂ <=24 -3x₁+4x₂ <=12

-x₁+x₂ <=3 3x₁+4x₂ <=30

x₁>=0, x₂>=0 x₁>=0, x₂>=0

2.1.5. Двойственная задача

Определение:

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

1. В одной задаче ищется максимум, а в другой минимум целевой функции.
2. Коэффициенты при переменных в линейной форме одной задачи являются свободными членами системы ограничений другой задачи и, наоборот, свободные члены системы ограничений одной задачи являются коэффициентами при переменных в линейной форме другой задачи.
3. В каждой задаче система ограничений задаётся в виде неравенств, причём все они одного смысла, а именно: в задаче, в которой ищется максимум линейной формы, все неравенства вида "<=", а в задаче, в которой находится минимум линейной формы, противоположного смысла, т.е.">=".
4. Коэффициенты при переменных систем ограничений описываются матрицами, транспонированными относительно друг друга.
5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.
6. Условия не отрицательности переменных сохраняются в обеих задачах.

Отсюда вытекает правило составления задачи, двойственной к исходной.

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

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

Прямая или исходная	Двойственная
f = max (I)	φ = min (II)

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

Прямая или исходная	Двойственная
f = max (II)	φ = min (II`)

Свойство двойственности является взаимным, т.е. если к задачам (I`) и (II`) записать двойственные, то они совпадут с задачами (I) и (II) соответственно. Любую задачу внутри двойственной пары можно назвать прямой или исход­ной, тогда другая будет двойственной к ней.

Исходная задача. Найти максимум целевой функции:

F=C₁X₁+C₂X₂+...+C_nX_n (2.6)

При ограничениях:

A₁₁X₁+A₁₂X₂+...+A_1nX_n<=B₁

A₂₁X₁+A₂₂X₂+...+A_2nX_n<=B₂

... (2.7)

A_m1X₁+A_m2X₂+...+A_mnX_n<=B_m

X_J>= 0

_J=1..n

Max(F)=?

Двойственная задача: Найти минимум целевой функции:

Z=B₁Y₁+B₂Y₂+...+B_mYm (2.8)

A₁₁Y₁+A₂₁Y₂+...+A_m1Y_n>=C₁

A₁₂Y₁+A₂₂Y₂+...+A_2nY_n>=C₂

... (2.9)

A_1nY₁+A_2nY₂+...+A_mnY_m>=C_m

Y_J>=0

_J=1..m

Min(Z)=?

2.1.6Основные теоремы двойственности

Теорема 1.

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

Fmax=Zmin или Fmin=Zmax