Для вирішення задачі лінейного програмування, потрібно записати вихідну задачу в формі задачі лінейного програмування, а потім застосовувати симплекс-метод . Основною задачею лінійного програмування – задача для якої:

1. потрібно визначити максимальне значення ф-ції

2. всі обмеження записані в вигляді рівностей

3. для всіх змінних виконується умова невідємності
Якщо обмеження має вид нерівності зі знаком >=, то шляхом множення його на
(-1) переходять до нерівності зі знаком |-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) = 45 15/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 | |5 |F | |410/9 |0 |0 |7/12 |0 |0 |5/18 | |
Х5= (26/9;140/27;0;0;8/9;1048/171) F5 = 45 5/9
F(x1) = f ( 2 8/9) = 8/9
F (x2) = f ( 5 5/27) = 5/27

-1/12х3 – 17/18х6 + х7 = -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 | |
Х6= ( 50/17;260/51;0;32/17;1608/323;16/17) F6 = 45 5/17
Будуємо нове відсічення:
F(x1) = f(2 16/17) = f(16/17) = 16/17
F(x2) = f (5 5/51) = f(5/51) = 5/51
F(x1)> F(x2)

-3/34x3 – 16/17x7 + x8 = -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 | |

Поделитесь этой записью или добавьте в закладки