Оптимизация показателей

Для вирішення задачі лінейного програмування, потрібно записати вихідну задачу в формі задачі лінейного програмування, а потім застосовувати симплекс-метод . Основною задачею лінійного програмування – задача для якої
1. потрібно визначити максимальне значення ф-ції
2. всі обмеження записані в вигляді рівностей
3. для всіх змінних виконується умова невідємності
Якщо обмеження має вид нерівності зі знаком >=, то шляхом множення його на (-1) переходять до нерівності зі знаком <=.
Від обмежень нерівностей необхідно перейти до обмежень рівностей. Такий перехід виконується шляхом введення в ліву частину кожної нерівності додаткових незалежних невідємних змінних. При цьому знак нерівності міняють на знак рівності.
Вихідне завдання
F = 5х1 +6х2 max
-10×1 — 6×2 ⊃3;-60
-4×1 + 9×2 £ 36
4×1 — 2×2 £ 8
x1,x2⊃3;0 x1,x2-цілі числа

Основна задача
F = 5х1 +6х2 max
10×1 + 6×2 + х3 =60
-4×1 + 9×2 +х4= 36
4×1 — 2×2 +х5 = 8
x1,x2,x3,x4,x5 ⊃3;0 x1,x2-цілі числа
Кожній змінній в системі відповідає свій вектор – стовпець. Вектор – стовпець Ро складається із значень правих частин рівнянь і називається вектором вільних членів.
Виходячи з основного завдання, складаєм симплекс-таблицю.

№ рядка
Базис
Сб
Р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) = 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/34×3 – 16/17×7 + 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) Будують прямі, рівняння яких отримують в результаті заміни в обмеженнях знаків нерівностей на знаки =.
10×1 + 6×2 =60 (1)
-4×1 + 9×2 = 36 (2)
4×1 — 2×2 = 8 (3)
x1=0, (4)
x2=0 (5)
Графіком рівняння x1 = 0 є вісь ординат, x2 =0 – вісь абсцисс.
Графіки решти рівнянь будують так. Оскільки графіки – це прями, то достатньо для кожного рівняння знайти дві точки, задовільнюючі йому, і через них провести пряумю.
2) Визначають область допустимих значень.
Область допустимих значень знаходиться в перший чверті координат, т.к. x1,x2⊃3;0 x1,x2-цілі числа
На коорд. Площині вибирають довільну точку і перевіряють виконання тотожністів рівняннях-обмеженнях. Якщо тотожність вірна, то дана нпівплощина – площина напівплощина допустимих рішень.
3) Будують радіус-вектор.

10

М

4

(2)
6

-9
(3)
(1)
-4

10

В М

4

( I )

-38/3

(2)
6

-9
(3)
(1)
-4

В точці В, що є оптимальною за даних умов, перетикаються (I) відсічення та (1) обмеження. Знайдемо координати т.В

-3х1 + 9х2 = 38 х1=26/9
т.В (26/9; 140/27)
10х1+ 6х2 = 60 х2=140/27 F ( B) = 45 5/9
-1/12х3 – 17/18х6 = -8/9 – второе отсечение.
-1/12х3*(60 – 10х1- 6х2) – 17/18*(38 + 3х1 – 9х2) = -8/9
-2х1 + 9х2 = 40 – уравнение 2-го отсечения.
Х7= 40 + 2х1 — 92

10

В М
С
4

-38/3

( II ) (I)

(2)
6

-9
2 16/17
-20 (II) (3)
(1)
-4

10

В М
С
D
4
(III)

( II ) (I)
(2)
6

-9
2 16/17
-20 (II) (3)
(1)
-4

Уравнение третьего отсечения
-3/34х3 – 16/17х7 = -16/17
х7 находится из 2 го ограничения
-3/34 * ( 60 – 10х1 – 6х2) – 16/17*(40 + 2х1 – 9х2) = -16/17
-х1 + 9х2 = 42 – ур. Третьего отсечения
В т. D пересекаются (1) и (III)
10х1 + 6х2 = 60
-х1 + 9х2 = 42
х1=3; х2=5. F(D)=45
т.D (3;5)
Вывод
экономико-матем. модел. испольузется в экономике для решения различного рода заданий, для оптимизации их. В данной к.р. использованы симплекс метод,….. отсечения Гомори, двойной симплекс метод. Геометрическая интерпретация показывает весь ход решения.
Список використаної літератури
1. Кузнецов Ю.Н. “Математическое програмирование (учебное пособие для экономических специальностей ”
2. Оптимізація єкономічних показників з врахуванням умови цілочисленності “Методичні вказівки до виконання курсової роботи з дисципліни “Економіко математичне моделювання для студентів економічних спеціальностей”(Викладач Іванов Л.П. –Чернігів ЧТІ,1998-20с)”