Экономико-математическое моделирование /
←предыдущая следующая→
1 2
Для вирішення задачі лінейного програмування, потрібно записати вихідну задачу в формі задачі лінейного програмування, а потім застосовувати симплекс-метод . Основною задачею лінійного програмування – задача для якої:
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
Таблица №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
4. Геометирчна интерпретація процесу розвязку.
Геометирчна интерпретація процесу розвязку дозволяє наглядно проілюстровати процесс знаходження оптимального плану.
1) Будують прямі, рівняння яких отримують в результаті заміни в обмеженнях знаків нерівностей на знаки =.
10x1 + 6x2 =60 (1)
-4x1 + 9x2 = 36 (2)
4x1 - 2x2 = 8 (3)
x1=0, (4)
x2=0 (5)
Графіком рівняння x1 = 0 є вісь ординат, x2 =0 – вісь абсцисс.
Графіки решти рівнянь будують так. Оскільки графіки – це прями, то достатньо для кожного рівняння знайти дві точки, задовільнюючі йому, і через них провести пряумю.
2) Визначають область допустимих значень.
Область допустимих значень знаходиться в перший чверті координат, т.к. x1,x20 x1,x2-цілі числа
На коорд. Площині вибирають довільну точку і перевіряють виконання тотожністів рівняннях-обмеженнях. Якщо тотожність вірна, то дана нпівплощина – площина напівплощина допустимих рішень.
3) Будують радіус-вектор.
10
М
4
(2)
6
-9
(3)
(1)
-4
10
В М
4
( I )
(2)
6
-9
(3)
(1)
-4
←предыдущая следующая→
1 2
|
|