Варіант №10. Роз’вязок

Варіант №10

Знайти цілочисельний розв’язок наступної задачі.

z= + 2 max

2 + k 7

(2+ k) - k 9

x1. 2 0, цілі числа, k=10

a) Знайти рішення методом Гоморі.

Роз’вязок

1. Знайти цілочисельний розв’язок наступної задачі.

Рішення:

y1= -2 - 10 + 7 0

y2= -12 + 10 + 9 0

1. y1= -2 - 10 + 7 0

y1 = 0

-2 - 10 + 7 = 0

x1 = 0, x2 = 7/10

x2 = 0, x1 = 7/2

y1(0) = 7 0

2. y2= -12 + 10 + 9 0

y2 = 0

-12 + 10 + 9 0

x1= 0, x2= -9/10

x2 =0, x1= 9/12

y2(0)= 9 0

z= + 2 = 0

x1= 0, x2= 0

x1 =-2, x2= 1

a) Знайти рішення методом Гоморі.

т. М (12/2; 0) maxZ = z(M)= 12/2

Точка М нецілочисельна. Ми знайшли нецілочисельний оптимальний розвязок. Переходимо до другого етапу і знаходимо цілочисельний оптимальний розв’язок.

x1 = 12/2, складаємо додаткове обмеження.

S1 = β 11x2 + β 12y1 – β 1

S1= 1/2 x2 – 1/2 y1 – 1/2

т. М (6; 0) maxZ= Z(M)=6

Точка М цілочисельна.

Висновок: На лабораторній роботі засвоєно метод відсікаючих площин (Гоморі) знаходження цілочисельного розв’язку.