Реферат: Оптимизация показателей

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

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

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

3.   для всіх змінних виконуєтьсяумова невідємності

Якщо обмеження має вид нерівності зізнаком >=, то шляхоммноження його на (-1) переходять до нерівності зі знаком <=.

Від обмежень нерівностей необхідно перейтидо обмежень рівностей. Такий перехід виконується шляхом введення в ліву частинукожної нерівності додаткових незалежних невідємних змінних. При цьому знакнерівності міняють на знак рівності.

Вихідне завдання:                                         

/>F = 5х1 +6х2        max

/>      -10x1 — 6x2 ³-60      

  -4x1 + 9x2  £ 36

   4x1 -  2x2  £ 8

x1,x2³0   x1,x2-цілі числа

 

Основна задача:

/>F = 5х1 +6х2       max

/>    10x1 + 6x2 + х3 =60  

  -4x1 + 9x2 +х4= 36

   4x1 -  2x2 +х5 = 8

x1,x2,x3,x4,x5 ³0  x1,x2-цілі числа

Кожній змінній в системі відповідає свій вектор –стовпець. Вектор – стовпець Ро складається із значень правих частинрівнянь і називається вектором вільних членів.

Виходячи з основного завдання, складаєм симплекс-таблицю. 

№ рядка Базис

Сб

Р0

Р1

Р2

Р3

Р4

Р5

1

Р3

60 10

/>6

1 2

Р4

36 -4 9 1 3

Р5

8 4 -2 1 4 F -5 -6

Таблиця№ 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

36 -1 1/5

/>0

2

Р2

6 4 -4/9 1 1 1/5 3

Р5

16 28/9 3/5 1 4 F 24

/>-23/3

1 1/5

Таблиця № 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 3/38 -1/19 2

Р2

6 100/19 1 2/57 5/57 3

Р5

136/19 -14/57 22/57 1 4 F 870/19 21/38 5/19

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<sub/> і  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 3/38 -1/19 2

Р2

6 100/19 1 2/57 5/57 3

Р5

136/19 -14/57 22/19 1 4

Р6

-16/19 -3/38

/>-18/19

/>1

5 F 870/19 23/38 5/19

/>

Х4 = (54/19;100/19;0;0;135/19;-16/19)  F(X4) = 4515/19

Т.к. опорний план містить відємну змінну то требазастосувати подвійний

с. м.

3.

Відшукання розвязкуЗЛП подвійним с-м включає слідуючі етапи:

1.  Знахдять опорне рішення

Х4 = (54/19;100/19;0;0;135/19;-16/19)  F(X4) = 4515/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 1/12 -1/18 2

Р2

6 140/27 1 1/36 5/54 3

Р5

1048/171 -13/38 1 11/9 4

Р4

8/9 1/12 1 -19/18 5 F 410/9 7/12 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 1/12 -1/18 2

Р2

6 140/27 1 1/36 5/54 3

Р5

1048/171 -13/38 1 11/9 4

Р4

8/9 1/12 1 -19/18 5

Р7

-8/9 -1/12

/>-17/18

/>1

6 F 410/9 7/12

/>5/18

Таблица № 7

№ рядка Базис

Сб

Р0

Р1

Р2

Р3

Р4

Р5

Р6

Р7

1

Р1

5 50/17 1 3/34 -1/17 2

Р2

6 260/51 1 1/57 5/57 3

Р5

1608/323 -436/969 1 11/17 4

Р4

32/17 3/17 1 -19/17 5

Р6

16/17 3/34 1 -18/17 6 F 770/17 19/34 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 3/34 -1/17 2

Р2

6 260/51 1 1/57 5/57 3

Р5

1608/323 -436/969 1 22/17 4

Р4

32/17 3/17 1 -19/17 5

Р6

6 16/17 3/34 1 -18/17 6

Р8

-16/17 -3/34

/>-16/17

1 7 F 770/17 19/34 5/17

Таблица №9

№ рядка Базис

Сб

Р0

Р1

Р2

Р3

Р4

Р5

Р6

Р7

Р8

1

Р1

5 3 1 3/32 2

Р2

6 5 1 1/96 3

Р5

70/19 -521/912 1 4

Р4

3 9/32 1 5

Р6

2 3/16 1 6

Р7

1 3/32 1 1 7 F 45 17/32

Х*=(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,x2³0   x1,x2-цілічисла

На коорд. Площинівибирають довільну точку і перевіряють виконання тотожністіврівняннях-обмеженнях. Якщо тотожність вірна, то дана нпівплощина – площинанапівплощина допустимих рішень.

3)  Будують радіус-вектор.

/>

/>                                                                                           10

/> /> /> /> /> <td/> /> /> /> />

/>/>                   

/>/>                                                                                                                                                      М

/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> <td/> /> <td/> /> <td/> /> <td/> /> /> /> <td/> /> <td/> /> <td/> /> <td/> /> <td/> /> <td/> /> <td/> /> <td/> />

/>/>                                                                                     4

/> /> /> /> /> /> /> /> <td/> /> /> /> <td/> /> /> /> <td/> /> /> /> <td/> /> /> /> <td/> /> /> /> <td/> />

               (2)                                                                                                    

                                                                                                                                                                   6

                                                                                                                                                                

-9

/>                                                                                                        (3)

(1)

-4

 

/>

/>                                                                                           10

/> /> /> /> /> <td/> /> /> /> />

/>/>/>                   

/>/>                                                                                                                         В                          М

/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> <td/> /> <td/> /> <td/> /> <td/> /> /> /> <td/> /> <td/> /> <td/> /> <td/> /> <td/> /> <td/> /> <td/> /> <td/> />

/>/>                                                                                     4

/>/>/>/>/>/>/>/>                                             

                                    ( I )

-38/3

 

                (2)                                                                                                    

                                                                                                                                                                   6

/>                                                                                                                                                               

-9

/>                                                                                                        (3)

(1)

-4

 

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

/> /> /> /> /> /> <td/> />

-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

/> /> /> /> /> <td/> /> /> /> />

/>/>/>                   

/>/>/>                                                                                                                         В                          М

/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>                                                                                                                             С

/>/>                                                                                     4

/>/>/>/>/>/>/>/>                                             

/>                                   

-38/3

  ( II )                            (I)

               (2)                                                                                                     

                                                                                                                                                                   6

/>                                                                                                                                                               

-9

                                                                                                                           216/17

/>-20 (II)                                                                                           (3)

(1)

-4

 

/>

/>                                                                                           10

/> /> /> /> /> <td/> /> /> /> />

/>/>/>                   

/>/>/>/>                                                                                                                         В                          М

/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>                                                                                                                             С

                                                                                                                         D

/>/>                                                                                     4

/>/>/>/>/>/>/>/>(III)                                     

/>                                   

( II )                            (I)

               (2)                                                                                                    

                                                                                                                                                                   6

/>                                                                                                                                                                

-9

                                                                                                                           216/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с)”