| Страница: 1 из 3 <-- предыдущая следующая --> | Перейти на страницу: |
| № рядка | Базис | Сб | Р0 | Р1 | Р2 | Р3 | Р4 | Р5 |
| 1 | Р3 | 0 | 60 | 10 | 6 | 1 | 0 | 0 |
| 2 | Р4 | 0 | 36 | -4 | 9 | 0 | 1 | 0 |
| 3 | Р5 | 0 | 8 | 4 | -2 | 0 | 0 | 1 |
| 4 | F |
| 0 | -5 | -6 | 0 | 0 | 0 |
Таблиця № 1 – Вихідна симплекс-таблиця
Знаходження оптимального розвязку ЗЛП за допмогою с-м включає слідуючі етапи:
1. За вихідною с-т знаходять опорне рішення
Кожній с-т відповідає своє опорне рішення. Воно може бути представлене у вигляди вектора Х Розмірніст вектора дорівнює кількості змінних в основній задачі.
Кожній змінній в симплекс таблиці відповідає свій вектор. Змінній x1—вектор Р1і т.д.
Вектор Р0складений із вільних членів рівнянь. Кожний рядок симплекс-таблиці – рівняння відповідно. Четвертий рядок—рядок оцінок в ньому записують коефіцієнти при змінних в цільовій ф-ції з протилежним знаком і визначається розв’язуємий стовпець, беруться модулі від’ємних чисел з цієї строки. В векторі Х кожній змінній відповідає певна компонента. Змінній х1перша компонента змінній х2—друга. Значення компонент визначають слідуючим чином, якщо вектор базисний, то компонента дорівнює значенню компоненти вектора стовпця Р0з того рідка де в базисі стоїть 1.
У вихідній таблиці вектори Р1, Р2– не базісні, тобто в Х – перша и друга компоненти = 0
Х=(0;0;60;36;8)
2. Зясовують, мається хочаб одне відємне значення врядку оцінок ( рядок 4) Якщо нема – то план оптимальний, якщо є – треба переходити до новій с-т.
Рядок оцінок має (-5) та (-6), отже данний опорний план – не оптимальний.
3. Знаходять визначальний стовпець. Стовпець називають визначальним, якщо в рядку оцінок у нього найбільше за модулем значення. Маємо стовпець Р2|-6|>|-5|
4. Знаходимо визначальний рядок. Визанчальним назівається такий рядок, який відповідає найменшому з відношень компонентів стовпця Родо додатніх компонентів визначального стовпця. (Рядок оцінок до уваги не приймається)
Min = ( 60/6; 36/9) = 4 – рядок 2.
5. Будують наступну с-т .
Для цього кожний елемент таблиці перераховуємо за формулою
aij=aij- (аіk*аnj)/ankде k-номер розв’язувального стовпця, а n- номер розв’язувального рядка
aij—елемент строки- і, стовпця- j нової сиплекс таблиці
aij—елемент строки- і, стовпця-j попередньої симплекс-таблиці
аіk-- елемент що знаходиться у визначальному стовпці попер. с-т.
аnj-- елемент що знаходиться у визначальному рядку попер с-т.
ank– элемент що стоїть на перехресті визн рядка и строки у попер сим-т.
a10= 60 – (36*6)/9 = 36
a11= 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
Х1=(0;4;36;0;16) F(X1) = 24
В рядку оцінок є одне відємне число. Тому Р1– визначальний стовпець
Min = ( 36/38*3;16/4;9) = 54/19 – визначальний рядок Р3
Таблиця № 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 |
X3= ( 54/19;100/19;0;0;136/19) F3(X3) = 4515/19
В рядку оцінок нема відємних значень, тому даний опорний план є оптимальним. Але не виконується умова цілочисельності, тому слід застосувати відсічення по методу Гоморі.
2. Застосування і побудова відсічення по методу Гоморі
х1=54/19, х2=100/19
До системи обмежень основного завдання добавляємо ще одну нерівність виду: F(a*ij)*xij>= F(b*ij), де a*ijі b*ijдробови частини чисел.
Під дробовою частиною числа а розуміють найменше невідємне число в і таке, що а – в є цілим числом.Якщо в оптимальному плані вихідного завдання дробового значення приймають декілька змінних, то додаткова нерівність будується для змінної, в якої найбільша дробова частина.
F(x1)>F(x2) (16/19 >5/19)
-3/38х3-18/19х4+ х6= -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 |
Х4= ( 54/19;100/19;0;0;135/19;-16/19) F(X4) = 45 15/19
Т.к. опорний план містить відємну змінну то треба застосувати подвійний
с. м.
3.
Відшукання розвязку ЗЛП подвійним с-м включає слідуючі етапи :
1. Знахдять опорне рішення
Х4= ( 54/19;100/19;0;0;135/19;-16/19) F(X4) = 45 15/19
2. Перевіряють знайдений опорний розвязок на оптимальність.
Розвязок не оптимальний, тому слід перейти до нового опорного рішення.
3. Вибираемо визначальний рядок. Визначальним називається той, який відповідає найбільшому за модулем відємному значенню в стовпцю Ро
Рядок № 4
4. Вибираємо визначальний стовпчик. Той, який відповідає найменшему відношенню рядка оцінок до ньгого. (по модулю)
Min = (23/38*38/3;5/19*19/18) = 5/18 стовпець Р4
Таблиця № 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 |
| Страница: 1 из 3 <-- предыдущая следующая --> | Перейти на страницу: |
| © 2007 ReferatBar.RU - Главная | Карта сайта | Справка |