Реферат: Оптимизация показателей

3. Знаходять визначальний стовпець. Стовпець називають визначальним, якщо в рядку оцінок у нього найбільше за модулем значення. Маємо стовпець Р₂ |-6|>|-5|

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

Min = ( 60/6; 36/9) = 4 – рядок 2.

5. Будують наступну с-т .

Для цього кожний елемент таблиці перераховуємо за формулою

a_ij =a_ij - (а_{і k *} а_nj )/a_nk де k-номер розв’язувального стовпця, а n- номер розв’язувального рядка

a_ij —елемент строки- і, стовпця- j нової сиплекс таблиці

a_ij —елемент строки- і, стовпця-j попередньої симплекс-таблиці

а_{і k} -- елемент що знаходиться у визначальному стовпці попер. с-т.

а_nj -- елемент що знаходиться у визначальному рядку попер с-т.

a_nk – элемент що стоїть на перехресті визн рядка и строки у попер сим-т.

a₁₀ = 60 – (36*6)/9 = 36

a₁₁ = 10 +(6*4)/9 = 38/3

№ рядка	Базис	Сб	Р0	Р1	Р2	Р3	Р4	Р5
1	Р3	0	36	0	0	-1 1/5	0
2	Р2	6	4	-4/9	1	1	1/5	0
3	Р5	0	16	28/9	0	0	3/5	1
4	F	24	-23/3	0	0	1 1/5	0

Таблиця № 2

Х₁ =(0;4;36;0;16) F(X₁ ) = 24

В рядку оцінок є одне відємне число. Тому Р₁ – визначальний стовпець

Min = ( 36/38*3;16/4;9) = 54/19 – визначальний рядок Р₃

Таблиця № 3

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

X₃ = ( 54/19;100/19;0;0;136/19) F₃ (X₃ ) = 45 15/19

В рядку оцінок нема відємних значень, тому даний опорний план є оптимальним. Але не виконується умова цілочисельності, тому слід застосувати відсічення по методу Гоморі.

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