- 1
- 2
- 3
- . . .
- последняя »
Для вирішення задачі лінейного програмування, потрібно записати вихідну задачу в формі задачі лінейного програмування, а потім застосовувати симплекс-метод . Основною задачею лінійного програмування – задача для якої:
потрібно визначити максимальне значення ф-ції всі обмеження записані в вигляді рівностей для всіх змінних виконується умова невідємності
Якщо обмеження має вид нерівності зі знаком >=, то шляхом множення його на (-1) переходять до нерівності зі знаком |-5| Знаходимо визначальний рядок. Визанчальним назівається такий рядок, який відповідає найменшому з відношень компонентів стовпця Ро до додатніх компонентів визначального стовпця. (Рядок оцінок до уваги не приймається)
Min = ( 60/6; 36/9) = 4 – рядок 2.
Будують наступну с-т .
Для цього кожний елемент таблиці перераховуємо за формулою
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 |
Х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 |
В рядку оцінок нема відємних значень, тому даний опорний план є оптимальним. Але не виконується умова цілочисельності, тому слід застосувати відсічення по методу Гоморі.
2. Застосування і побудова відсічення по методу Гоморі
х1=54/19, х2=100/19
До системи обмежень основного завдання добавляємо ще одну нерівність виду: F(a*ij)*xij>= F(b*ij), де a*ij і b*ij дробови частини чисел.
Під дробовою частиною числа а розуміють найменше невідємне число в і таке, що а – в є цілим числом.Якщо в оптимальному плані вихідного завдання дробового значення приймають декілька змінних, то додаткова
- 1
- 2
- 3
- . . .
- последняя »
Похожие работы
Интересная статья: Основы написания курсовой работы