1. Методы решения зцлп

Методы решения ЗЦЛП делятся на две основные группы:

1 - методы отсечений

2 - комбинаторные методы.

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

* , (2.32)

где - коэффициенты дополнительных ограничений,

- правые части дополнительных ограничений

* Данное ограничение отсекает от допустимой области часть, бесперспективную для поиска решения задач ЦЛП.

Рис. 2.12

После ввода дополнительного ограничения ЗЦЛП вновь решается методами линейного программирования.

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

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

Коэффициенты ив методе Гомори определяются так:

(2.33)

где ,это целые частии .

Пример 2.16:

Найти max

Итерация №0 Таблица 2.47

базис	ЗН	х1	х2	х3	х4	х5
х3	2	1	-2	1	0	0
х4	2	-2	1	0	1	0
х5	3	1	1	0	0	1
	0	-1	-2	0	0	0

Строка с х₃: 2 – 2 ∙ (-2) = 6;

1 – (-2) ∙ (-2) = -3;

-2 – 1 ∙ (-2) = 0;

1 – 0 ∙ (-2) = 1;

0 – 1 ∙ (-2) = 2;

0 – 0 ∙ (-2) = 0.

Строка с х₅: 3 – 2 ∙ 1 = 1;

1 – (-2) ∙ 1 = 3;

1 – 1 ∙ 1 = 0;

0 – 0 ∙ 1 = 0;

0 – 1 ∙ 1 = -1;

1 – 0 ∙ 1 = 1.

Строка с : 0 – 2 ∙ (-2) = 4;

-1 – (-2) ∙ (-2) = -5;

-2 – 1 ∙ (-2) = 0;

0 – 0 ∙ (-2) = 0;

0 – 1 ∙ (-2) = 2;

0 – 0 ∙ (-2) = 0.

Итерация №1 Таблица 2.48

базис	ЗН	х1	х2	х3	х4	х5
х3	6	-3	0	1	2	0
х2	2	-2	1	0	1	0
х5	1	3	0	0	-1	1
	4	-5	0	0	2	0

Строка с х₃: 6 – 1/3 ∙ (-3) = 7;

-3 – 1 ∙ (-3) = 0;

0 – 0 ∙ (-3) = 0;

1 – 0 ∙ (-3) = 1;

2 – (-1/3) ∙ (-3) = 1;

0 – 1/3 ∙ (-3) = 1.

Строка с х₂: 2 – 1/3 ∙ (-2) = 8/3;

-2 – 1 ∙ (-2) = 0;

1 – 0 ∙ (-2) = 1;

0 – 0 ∙ (-2) = 0;

1 – (-1/3) ∙ (-2) = 1/3;

0 – 1/3 ∙ (-2) = 2/3.

Строка с : 4 – 1/3 ∙ (-5) = 17/3;

-5 – 1 ∙ (-5) = 0;

0 – 0 ∙ (-5) = 0;

0 – 0 ∙ (-5) = 0;

2 – (-1/3) ∙ (-5) = 1/3;

0 – 1/3 ∙ (-5) = 5/3.

Итерация №2 Таблица 2.49

базис	ЗН	х1	х2	х3	х4	х5
х3	7	0	0	1	1	1
х2	8/3	0	1	0	1/3	2/3
х1	1/3	1	0	0	-1/3	1/3
	17/3	0	0	0	1/3	5/3

.

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

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

Определяем значение и :

Дополнительное ограничение имеет вид:

Приводим к канонической форме:

Вводим выражение в симплекс-таблицу Таблица 2.50

базис	ЗН	х1	х2	х3	х4	х5	х6
х3	7	0	0	1	1	1	0
х2	8/3	0	1	0	1/3	2/3	0
х1	1/3	1	0	0	-1/3	1/3	0
х6	-2/3	0	0	0	-1/3	-2/3	1
	17/3	0	0	0	1/3	5/3	0

Так как базисная переменная х₆имеет отрицательное значение, то данную задачу решаем двойственным симплекс-методом (х₆меняем или на х₄)

Строка с х₃: 7 – 2 ∙1 = 5;

0 – 0 ∙ 1 = 0;

0 – 0 ∙ 1 = 0;

1 – 0 ∙ 1 = 1;

1 – 1 ∙ 1 = 0;

1 – 2 ∙ 1 = -1;

0 – (-3) ∙ 1 = 3.

Строка с х₂: 8/3 – 2 ∙1/3 = 2;

0 – 0 ∙ 1/3 = 0;

1 – 0 ∙ 1/3 = 1;

0 – 0 ∙ 1/3 = 0;

1/3 – 1 ∙ 1/3 = 0;

2/3 – 2 ∙ 1/3 = 0;

0 – (-3) ∙ 1/3 = 1.

Строка с х₁: 1/3 – 2 ∙ (-1/3) = 1;

1 – 0 ∙ (-1/3)= 1;

0 – 0 ∙ (-1/3) = 0;

0 – 0 ∙ (-1/3) = 0;

-1/3 – 1 ∙ (-1/3) = 0;

1/3 – 2 ∙ (-1/3) = 1;

0 – (-3) ∙ (-1/3) = -1.

Строка с : 17/3 – 2 ∙ 1/3 = 5;

0 – 0 ∙ 1/3 = 0;

0 – 0 ∙ 1/3 = 0;

0 – 0 ∙ 1/3 = 0;

1/3 – 1 ∙ 1/3 = 0;

5/3 – 2 ∙ 1/3 = 1;

0 – (-3) ∙ 1/3 = 1.

Таблица 2.51

базис	ЗН	х1	х2	х3	х4	х5	х6
х3	5	0	0	1	0	-1	3
х2	2	0	1	0	0	0	1
х1	1	1	0	0	0	1	-1
х4	2	0	0	0	1	2	-3
	5	0	0	0	0	1	1

,

Пример 2.17:

Найти решение ЗЦЛП методом Гомори.

ЗЛП имеет вид:

- канонический вид.

			х2
						(1)
							(4)
				(3)
					(2)
							х1
					f (x)

Рис. 2. 13

Таблица 2.52

базис	значение	x1	x2	x3	x4	x5	x6
x3	4,2	0	0	1	-0,4	0,2	0
x6	32,6	0	0	0	1,3	-0,9	1
x2	10,6	0	1	0	0,3	0,1	0
x1	10,8	1	0	0	-0,1	0,3	0
f (x)	32,2	0	0	0	0,1	0,7	0

Решение:

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

В данном случае наибольшая дробная часть у x₁.

Определяем значение и :

10,8 – [10,8] = 0,8;

1 – [1] = 0;

0 – [0] = 0;

0 – [0] = 0;

-0,1 – [-0,1] = 0,9;

0,3 – [0,3] = 0,3;

0 – [0] = 0.

Дополнительное ограничение имеет вид:

;

Приводим к канонической форме:

Вводим выражение в симплекс – таблицу:

Итерация №0 Таблица 2.53

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	4,2	0	0	1	-0,4	0,2	0	0
x6	32,6	0	0	0	1,3	-0,9	1	0
x2	10,6	0	1	0	0,3	0,1	0	0
x1	10,8	1	0	0	-0,1	0,3	0	0
x7	-0,8	0	0	0	-0,9	-0,3	0	1
f (x)	32,2	0	0	0	0,1	0,7	0	0

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

Переменную x₄вводим в число базисных вместо переменнойx₇

Ведущий элемент равен -0,9.

Итерация №1 Таблица 2.54

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	41/9	0	0	1	0	1/3	0	-4/9
x6	283/9	0	0	0	0	-4/3	1	13/9
x2	31/3	0	1	0	0	0	0	1/3
x1	98/9	1	0	0	0	1/3	0	-1/9
x4	8/9	0	0	0	1	1/3	0	-10/9
f (x)	289/9	0	0	0	0	2/3	0	1/9

В решении задачи базисные переменные нецелые.

Наибольшая дробная часть у x₁ иx₄. Выберемx_1.

Определяем значение и :

98/9 – [98/9] = 8/9;

1 – [1] = 0;

0 – [0] = 0;

0 – [0] = 0;

0 – [0] = 0;

1/3 – [1/3] = 1/3;

0 – [0] = 0;

-1/9 – [-1/9] = 8/9.

Дополнительное ограничение имеет вид:

;

Приводим к канонической форме:

Вводим выражение в симплекс – таблицу:

Итерация №0 Таблица 2.55

базис	значение	x1	x2	x3	x4	x5	x6	x7	x8
x3	41/9	0	0	1	0	1/3	0	-4/9	0
x6	283/9	0	0	0	0	-4/3	1	13/9	0
x2	31/3	0	1	0	0	0	0	1/3	0
x1	98/9	1	0	0	0	1/3	0	-1/9	0
x4	8/9	0	0	0	1	1/3	0	-10/9	0
x8	-8/9	0	0	0	0	-1/3	0	-8/9	1
f (x)	289/9	0	0	0	0	2/3	0	1/9	0

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

Переменную x₇вводим в число базисных вместо переменнойx₈

Ведущий элемент равен -8/9.

Итерация №1 Таблица 2.56

базис	значение	x1	x2	x3	x4	x5	x6	x7	x8
x3	5	0	0	1	0	0,5	0	0	-0,5
x6	30	0	0	0	0	-1,875	1	0	1,625
x2	10	0	1	0	0	-0,125	0	0	0,375
x1	11	1	0	0	0	0,375	0	0	-0,125
x4	2	0	0	0	1	0,75	0	0	-1,25
x7	1	0	0	0	0	0,375	0	1	-1,125
f (x)	32	0	0	0	0	0,625	0	0	0,125

Ответ: