Реферат

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

Работа добавлена на сайт bukvasha.net: 2015-10-28

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 22.11.2024





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

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

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

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

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

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

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

F = 1 +6х2        max 

      -10x1 - 6x2 ³-60       

  -4x1 + 9x2  £ 36

   4x1 -  2x2  £ 8

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

 

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

F = 1 +6х2       max
    10x1 + 6x2 + х3 =60   

  -4x1 + 9x24= 36

   4x1 -  2x2 5 = 8
x1,x2,x3,x4,x5  ³0  x1,x2-цілі числа

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

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

№ рядка

Базис

Сб

Р0

Р1

Р2

Р3

Р4

Р5

1

Р3

0

60

10

Овал: 96

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

Овал: 38/3Р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,x2³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с)” 




1. Реферат Невьянская икона Традиции Древней Руси и контекст Нового времени
2. Реферат на тему Искусство первобытной эпохи
3. Реферат на тему Frankish Gaul To 814
4. Диплом на тему Волинська земля у складі Галицько Волинського князівства
5. Реферат Риск менеджера
6. Реферат Социальная диагностика и профилактика
7. Контрольная работа Технология строительства
8. Реферат Юго-Западная Кавказская демократическая республика
9. Контрольная работа на тему Понятие и условия брака по семейному праву Недействительность брака
10. Реферат Мовлення вчителя як засіб педагогічної праці 2