Застосування і побудова відсічення по методу Гоморі

2. Застосування і побудова відсічення по методу Гоморі

 х₁=54/19, х₂=100/19

До системи обмежень основного завдання добавляємо ще одну нерівність виду: F(a^*_ij)*x_ij>= F(b^*_ij), де a^*_ij і b^*_ij дробови частини чисел.

Під дробовою частиною числа а розуміють найменше невідємне число в і таке, що а – в є цілим числом.Якщо в оптимальному плані вихідного завдання дробового значення приймають декілька змінних, то додаткова нерівність будується для змінної, в якої найбільша дробова частина.

F(x₁)>F(x₂) (16/19 >5/19)

-3/38х₃-18/19х₄ + х₆ = -16/19

таблиця № 4

№ рядка	Базис	Сб	Р0	Р1	Р2	Р3	Р4	Р5	Р6
1	Р1	5	54/19	1	0	3/38	-1/19	0	0
2	Р2	6	100/19	0	1	2/57	5/57	0	0
3	Р5	0	136/19	0	0	-14/57	22/19	1	0
4	Р6	0	-16/19	0	0	-3/38	-18/19	0	1
5	F		870/19	0	0	23/38	5/19	0	0

Х₄ = ( 54/19;100/19;0;0;135/19;-16/19) F(X₄) = 45 15/19

Т.к. опорний план містить відємну змінну то треба застосувати подвійний

с. м.

3.

Відшукання розвязку ЗЛП подвійним с-м включає слідуючі етапи:

1.   Знахдять опорне рішення

Х₄ = ( 54/19;100/19;0;0;135/19;-16/19) F(X₄) = 45 15/19

2.   Перевіряють знайдений опорний розвязок на оптимальність.

Розвязок не оптимальний, тому слід перейти до нового опорного рішення.

3.   Вибираемо визначальний рядок. Визначальним називається той, який відповідає найбільшому за модулем відємному значенню в стовпцю Р_о

Рядок № 4

4.   Вибираємо визначальний стовпчик. Той, який відповідає найменшему відношенню рядка оцінок до ньгого. (по модулю)

Min = (23/38*38/3;5/19*19/18) = 5/18 стовпець Р₄

Таблиця № 5

№ рядка	Базис	Сб	Р0	Р1	Р2	Р3	Р4	Р5	Р6
1	Р1	5	26/9	1	0	1/12	0	0	-1/18
2	Р2	6	140/27	0	1	1/36	0	0	5/54
3	Р5	0	1048/171	0	0	-13/38	0	1	11/9
4	Р4	0	8/9	0	0	1/12	1	0	-19/18
5	F		410/9	0	0	7/12	0	0	5/18

Х₅= (26/9;140/27;0;0;8/9;1048/171) F₅ = 45 5/9

F(x₁) = f ( 2 8/9) = 8/9

F (x₂) = f ( 5 5/27) = 5/27

-1/12х₃ – 17/18х₆ + х₇ = -8/9

таблица № 6

№ рядка	Базис	Сб	Р0	Р1	Р2	Р3	Р4	Р5	Р6	Р7
1	Р1	5	26/9	1	0	1/12	0	0	-1/18	0
2	Р2	6	140/27	0	1	1/36	0	0	5/54	0
3	Р5	0	1048/171	0	0	-13/38	0	1	11/9	0
4	Р4	0	8/9	0	0	1/12	1	0	-19/18	0
5	Р7	0	-8/9	0	0	-1/12	0	0	-17/18	1
6	F		410/9	0	0	7/12	0	0	5/18	0

Таблица № 7

№ рядка	Базис	Сб	Р0	Р1	Р2	Р3	Р4	Р5	Р6	Р7
1	Р1	5	50/17	1	0	3/34	0	0	0	-1/17
2	Р2	6	260/51	0	1	1/57	0	0	0	5/57
3	Р5	0	1608/323	0	0	-436/969	0	1	0	11/17
4	Р4	0	32/17	0	0	3/17	1	0	0	-19/17
5	Р6	0	16/17	0	0	3/34	0	0	1	-18/17
6	F		770/17	0	0	19/34	0	0	0	5/17

Х₆= ( 50/17;260/51;0;32/17;1608/323;16/17) F₆ = 45 5/17

 Будуємо нове відсічення:

 F(x₁) = f(2 16/17) = f(16/17) = 16/17

F(x₂) = f (5 5/51) = f(5/51) = 5/51

F(x₁)> F(x₂)

-3/34x₃ – 16/17x₇ + x₈ = -16/17

таблица №8

№ рядка	Базис	Сб	Р0	Р1	Р2	Р3	Р4	Р5	Р6	Р7	Р8
1	Р1	5	50/17	1	0	3/34	0	0	0	-1/17	0
2	Р2	6	260/51	0	1	1/57	0	0	0	5/57	0
3	Р5	0	1608/323	0	0	-436/969	0	1	0	22/17	0
4	Р4	0	32/17	0	0	3/17	1	0	0	-19/17	0
5	Р6	6	16/17	0	0	3/34	0	0	1	-18/17	0
6	Р8	0	-16/17	0	0	-3/34	0	0	0	-16/17	1
7	F		770/17	0	0	19/34	0	0	0	5/17	0

Таблица №9

№ рядка	Базис	Сб	Р0	Р1	Р2	Р3	Р4	Р5	Р6	Р7	Р8
1	Р1	5	3	1	0	3/32	0	0	0	0	0
2	Р2	6	5	0	1	1/96	0	0	0	0	0
3	Р5	0	70/19	0	0	-521/912	0	1	0	0	0
4	Р4	0	3	0	0	9/32	1	0	0	0	0
5	Р6	0	2	0	0	3/16	0	0	1	0	0
6	Р7	0	1	0	0	3/32	0	0	0	1	1
7	F		45	0	0	17/32	0	0	0	0	0

Х^*=(3; 5) F^*=45