Приклад розв’язання лінійної задачі цілочисельного програмування

Раніше ми отримали за допомогою ДСМ оптимальне рішення задачі ЛП:

(2.4)

(2.5)

(2.6)

,

які показані у табл.2.1.

Таблиця 2.1.

1-ша симплекс-таблиця.

Номер рівняння	Базисні змінні	Змінні				bi
		X1	X2	X3	X4
		j=1	j=2	j=3	j=4	J=0
1	X2	-1/2	1	-1/4	0	5/4
2	X4	2	0	1/2	1	15/2
0	F	7/2	0	3/4	0	-15/4

Тепер треба отримати цілочисельне рішення. З цією метою виділяємо рівняння з дробовою частиною (2.2) і з нього отримуємо рівняння Гоморі

.

Цю нерівність ми переводимо до вигляду, якого потрібно дотримуватись при використанні симплекс-методу:

.

Далі за допомогою додаткової додатньої змінної переводимо нерівність у рівність:

і створюємо нову табл. 2.2 доданням відповідної колонки та комірки для нової базисної змінної.

Таблиця 2.2.

2-га симплекс-таблиця.

Номер рівняння	Базисні змінні	Змінні					bi
		X1	X2	X3	X4	X5
		j=1	j=2	j=3	j=4	J=5	j=0
1	X2	-1/2	1	-1/4	0	0	5/4
2	X4	2	0	1/2	1	0	15/2
3	X5	-1/2	0	-3/4^х	0	1	-1/4
0	F	7/2	0	3/4	0	0	-15/4

За допомогою ДСМ заповнюємо комірки табл. 2.3 (розрахунки не показані).

Таблиця 2.3.

3-я симплекс-таблиця.

Номер рівняння	Базисні змінні	Змінні					bi
		X1	X2	X3	X4	X5
		j=1	j=2	j=3	j=4	J=5	j=0
1	X2	-1/3	1	0	0	-1/3	4/3
2	X4	5/3	0	0	1	2/3	22/3
3	X3	2/3	0	1	0	-4/3	1/3
0	F	3	0	0	0	1	-4

Ми бачимо, що цілочисельні значення отримали лише комірки рядка і = 0 для функції мети. Тому з табл. 2.3. виділяємо рівняння і = 1, отримуємо для нього рівняння Гоморі і заповнюємо табл. 2.4.

Таблиця 2.4.

4-та симплекс-таблиця.

Номер рівняння	Базисні змінні	Змінні						bi
		X1	X2	X3	X4	X5	X6
		j=1	j=2	j=3	j=4	j=5	j=6	J=0
1	X2	-1/3	1	0	0	-1/3	0	4/3
2	X4	5/3	0	0	1	2/3	0	22/3
3	X3	2/3	0	1	0	-4/3	0	1/3
4	X6	-2/3	0	0	0	-2/3^х	1	-1/3
0	F	3	0	0	0	1	0	-4

В табл.2.4 виділяємо вирішальний елемент (показаний зірочкою) і за допомогою ДСМ заповнюємо табл. 2.5.

Таблиця 2.5.

5-та симплекс-таблиця.

Номер рівняння	Базисні змінні	Змінні						bi
		X1	X2	X3	X4	X5	X6
		j=1	j=2	j=3	j=4	j=5	j=6	J=0
1	X2	0	1	0	0	0	-1/2	3/2
2	X4	1	0	0	1	0	1	7
3	X3	2	0	1	0	0	-2	1
4	X5	1	0	0	0	1	-3/2	½
0	F	2	0	0	0	0	3/2	-9/2

В табл.2.5 для рядка і = 4 отримуємо рівняння Гоморі, вводимо нову колонку та рядок для нової базисної змінної і заповнюємо комірки табл.2.6.

Таблиця 2.6.

6-та симплекс-таблиця.

Номер рівняння	Базисні змінні	Змінні							bi
		X1	X2	X3	X4	X5	X6	X7
		j=1	j=2	j=3	j=4	j=5	j=6	j=7	j=0
1	X2	0	1	0	0	0	-1/2	0	3/2
2	X4	1	0	0	1	0	1	0	7
3	X3	2	0	1	0	0	-2	0	1
4	X5	1	0	0	0	1	-3/2	0	1/2
5	X7	0	0	0	0	0	-1/2^х	1	-1/2
0	F	2	0	0	0	0	3/2	0	-9/2

В табл.2.6 виділяємо вирішальний елемент (показаний зірочкою) і за допомогою ДСМ заповнюємо табл.2.7.

Таблиця 2.7.

7-ма симплекс-таблиця.

Номер рівняння	Базисні змінні	Змінні							bi
		X1	X2	X3	X4	X5	X6	X7
		j=1	j=2	j=3	j=4	j=5	j=6	j=7	j=0
1	X2	0	1	0	0	0	0	-1	2
2	X4	1	0	0	1	0	0	2	6
3	X3	2	0	1	0	0	0	-4	3
4	X5	1	0	0	0	1	0	-3	2
5	X6	0	0	0	0	0	1	-2	1
0	F	2	0	0	0	0	0	4	-6

Таким чином отримали цілочисельне рішення за методом Гоморі: