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

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

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

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

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

от 25%

Подписываем

договор

Имя

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

Принимаю Политику конфиденциальности

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

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

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

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

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

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

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

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

F = 5х₁ +6х₂ max

      -10x₁ - 6x₂ ³-60

-4x₁ + 9x₂ £ 36

   4x₁ - 2x₂ £ 8

x₁,x₂³0   x₁,x₂-цілі числа

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

F = 5х₁ +6х₂ max

10x₁ + 6x₂ + х₃=60

-4x₁ + 9x₂ +х₄= 36

4x₁ - 2x₂ +х₅ = 8
x₁,x₂,x₃,x₄,x₅ ³0 x₁,x₂-цілі числа

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

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

№ рядка	Базис	С_б	Р₀	Р₁	Р₂	Р₃	Р₄	Р₅
1	Р₃	0	60	10	6	1	0	0
2	Р₄	0	36	-4	9	0	1	0
3	Р₅	0	8	4	-2	0	0	1
4	F		0	-5	-6	0	0	0

Таблиця № 1 – Вихідна симплекс-таблиця

Знаходження оптимального розвязку ЗЛП за допмогою с-м включає слідуючі етапи:

1.     За вихідною с-т знаходять опорне рішення

Кожній с-т відповідає своє опорне рішення. Воно може бути представлене у вигляди вектора Х Розмірніст вектора дорівнює кількості змінних в основній задачі.

Кожній змінній в симплекс таблиці відповідає свій вектор. Змінній x₁—вектор Р₁і т.д.

Вектор Р₀ складений із вільних членів рівнянь. Кожний рядок симплекс-таблиці – рівняння відповідно. Четвертий рядок—рядок оцінок в ньому записують коефіцієнти при змінних в цільовій ф-ції з протилежним знаком і визначається розв’язуємий стовпець, беруться модулі від’ємних чисел з цієї строки. В векторі Х кожній змінній відповідає певна компонента. Змінній х₁ перша компонента змінній х₂—друга. Значення компонент визначають слідуючим чином, якщо вектор базисний, то компонента дорівнює значенню компоненти вектора стовпця Р₀ з того рідка де в базисі стоїть 1.

У вихідній таблиці вектори Р₁, Р₂ – не базісні, тобто в Х – перша и друга компоненти = 0

Х=(0;0;60;36;8)

2.     Зясовують, мається хочаб одне відємне значення врядку оцінок ( рядок 4) Якщо нема – то план оптимальний, якщо є – треба переходити до новій с-т.

Рядок оцінок має (-5) та (-6), отже данний опорний план – не оптимальний.

3.     Знаходять визначальний стовпець. Стовпець називають визначальним, якщо в рядку оцінок у нього найбільше за модулем значення. Маємо стовпець Р₂ |-6|>|-5|

4.     Знаходимо визначальний рядок. Визанчальним назівається такий рядок, який відповідає найменшому з відношень компонентів стовпця Р_о до додатніх компонентів визначального стовпця. (Рядок оцінок до уваги не приймається)

Min = ( 60/6; 36/9) = 4 – рядок 2.

5.     Будують наступну с-т .

Для цього кожний елемент таблиці перераховуємо за формулою

a_ij=a_ij- (а_і_k_* а_nj)/a_nk де k-номер розв’язувального стовпця, а n- номер розв’язувального рядка

a_ij—елемент строки- і, стовпця- j нової сиплекс таблиці

a_ij—елемент строки- і, стовпця-j попередньої симплекс-таблиці

а_і_k-- елемент що знаходиться у визначальному стовпці попер. с-т.

а_nj-- елемент що знаходиться у визначальному рядку попер с-т.

a_nk – элемент що стоїть на перехресті визн рядка и строки у попер сим-т.
a₁₀= 60 – (36*6)/9 = 36

a₁₁= 10 +(6*4)/9 = 38/3

№ рядка	Базис	С_б	Р₀	Р₁	Р₂	Р₃	Р₄	Р₅
1	Р₃	0	36		0	0	-1 1/5	0
2	Р₂	6	4	-4/9	1	1	1/5	0
3	Р₅	0	16	28/9	0	0	3/5	1
4	F		24	-23/3	0	0	1 1/5	0

Таблиця № 2
Х₁=(0;4;36;0;16) F(X₁) = 24

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

Min = ( 36/38*3;16/4;9) = 54/19 – визначальний рядок Р₃

Таблиця № 3

№ рядка	Базис	С_б	Р₀	Р₁	Р₂	Р₃	Р₄	Р₅
1	Р₁	5	54/19	1	0	3/38	-1/19	0
2	Р₂	6	100/19	0	1	2/57	5/57	0
3	Р₅	0	136/19	0	0	-14/57	22/57	1
4	F		870/19	0	0	21/38	5/19	0

X₃= ( 54/19;100/19;0;0;136/19) F₃(X₃) = 45 15/19

В рядку оцінок нема відємних значень, тому даний опорний план є оптимальним. Але не виконується умова цілочисельності, тому слід застосувати відсічення по методу Гоморі.

2. Застосування і побудова відсічення по методу Гоморі

х₁=54/19, х₂=100/19

До системи обмежень основного завдання добавляємо ще одну нерівність виду: F(a^*_ij)*x_ij>= F(b^*_ij), де a^*_ij і b^*_ij дробови частини чисел.

Під дробовою частиною числа а розуміють найменше невідємне число в і таке, що а – в є цілим числом.Якщо в оптимальному плані вихідного завдання дробового значення приймають декілька змінних, то додаткова нерівність будується для змінної, в якої найбільша дробова частина.

F(x₁)>F(x₂) (16/19 >5/19)

-3/38х₃-18/19х₄ + х₆ = -16/19

таблиця № 4

№ рядка	Базис	С_б	Р₀	Р₁	Р₂	Р₃	Р₄	Р₅	Р₆
1	Р₁	5	54/19	1	0	3/38	-1/19	0	0
2	Р₂	6	100/19	0	1	2/57	5/57	0	0
3	Р₅	0	136/19	0	0	-14/57	22/19	1	0
4	Р₆	0	-16/19	0	0	-3/38	-18/19	0	1
5	F		870/19	0	0	23/38	5/19	0	0

Х₄ = ( 54/19;100/19;0;0;135/19;-16/19) F(X₄) = 45 15/19

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

с. м.

3.

Відшукання розвязку ЗЛП

подвійним с-м включає слідуючі етапи:

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

Х₄ = ( 54/19;100/19;0;0;135/19;-16/19) F(X₄) = 45 15/19

2.     Перевіряють знайдений опорний розвязок на оптимальність.

Розвязок не оптимальний, тому слід перейти до нового опорного рішення.

3.     Вибираемо визначальний рядок. Визначальним називається той, який відповідає найбільшому за модулем відємному значенню в стовпцю Р_о

Рядок № 4

4.     Вибираємо визначальний стовпчик. Той, який відповідає найменшему відношенню рядка оцінок до ньгого. (по модулю)

Min = (23/38*38/3;5/19*19/18) = 5/18 стовпець Р₄
Таблиця № 5

№ рядка	Базис	С_б	Р₀	Р₁	Р₂	Р₃	Р₄	Р₅	Р₆
1	Р₁	5	26/9	1	0	1/12	0	0	-1/18
2	Р₂	6	140/27	0	1	1/36	0	0	5/54
3	Р₅	0	1048/171	0	0	-13/38	0	1	11/9
4	Р₄	0	8/9	0	0	1/12	1	0	-19/18
5	F		410/9	0	0	7/12	0	0	5/18

Х₅= (26/9;140/27;0;0;8/9;1048/171) F₅ = 45 5/9

F(x₁) = f ( 2 8/9) = 8/9

F (x₂) = f ( 5 5/27) = 5/27
-1/12х₃ – 17/18х₆ + х₇ = -8/9
таблица № 6

№ рядка	Базис	С_б	Р₀	Р₁	Р₂	Р₃	Р₄	Р₅	Р₆	Р₇
1	Р₁	5	26/9	1	0	1/12	0	0	-1/18	0
2	Р₂	6	140/27	0	1	1/36	0	0	5/54	0
3	Р₅	0	1048/171	0	0	-13/38	0	1	11/9	0
4	Р₄	0	8/9	0	0	1/12	1	0	-19/18	0
5	Р₇	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

№ рядка	Базис	С_б	Р₀	Р₁	Р₂	Р₃	Р₄	Р₅	Р₆	Р₇
1	Р₁	5	50/17	1	0	3/34	0	0	0	-1/17
2	Р₂	6	260/51	0	1	1/57	0	0	0	5/57
3	Р₅	0	1608/323	0	0	-436/969	0	1	0	11/17
4	Р₄	0	32/17	0	0	3/17	1	0	0	-19/17
5	Р₆	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

Х₆= ( 50/17;260/51;0;32/17;1608/323;16/17) F₆ = 45 5/17

Будуємо нове відсічення:

F(x₁) = f(2 16/17) = f(16/17) = 16/17

F(x₂) = f (5 5/51) = f(5/51) = 5/51

F(x₁)> F(x₂)
-3/34x₃ – 16/17x₇ + x₈ = -16/17
таблица №8

№ рядка	Базис	С_б	Р₀	Р₁	Р₂	Р₃	Р₄	Р₅	Р₆	Р₇	Р₈
1	Р₁	5	50/17	1	0	3/34	0	0	0	-1/17	0
2	Р₂	6	260/51	0	1	1/57	0	0	0	5/57	0
3	Р₅	0	1608/323	0	0	-436/969	0	1	0	22/17	0
4	Р₄	0	32/17	0	0	3/17	1	0	0	-19/17	0
5	Р₆	6	16/17	0	0	3/34	0	0	1	-18/17	0
6	Р₈	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

№ рядка	Базис	С_б	Р₀	Р₁	Р₂	Р₃	Р₄	Р₅	Р₆	Р₇	Р₈
1	Р₁	5	3	1	0	3/32	0	0	0	0	0
2	Р₂	6	5	0	1	1/96	0	0	0	0	0
3	Р₅	0	70/19	0	0	-521/912	0	1	0	0	0
4	Р₄	0	3	0	0	9/32	1	0	0	0	0
5	Р₆	0	2	0	0	3/16	0	0	1	0	0
6	Р₇	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) Будують прямі, рівняння яких отримують в результаті заміни в обмеженнях знаків нерівностей на знаки =.

   10x₁ + 6x₂ =60   (1)

-4x₁ + 9x₂ = 36       (2)

   4x₁ - 2x₂ = 8      (3)

x₁=0, (4)

x₂=0 (5)

Графіком рівняння x₁= 0 є вісь ординат, x₂=0 – вісь абсцисс.

Графіки решти рівнянь будують так. Оскільки графіки – це прями, то достатньо для кожного рівняння знайти дві точки, задовільнюючі йому, і через них провести пряумю.

2)     Визначають область допустимих значень.

Область допустимих значень знаходиться в перший чверті координат, т.к. x₁,x₂³0   x₁,x₂-цілі числа

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

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

                (2)

                                                                                                                                                                   6



-9
                                                                                                         (3)
(1)
-4

В М

( I )

-38/3

(2)

6

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

-3х₁ + 9х₂ = 38           х₁=26/9

                                                                         т.В (26/9; 140/27)

10х₁+ 6х₂ = 60            х₂=140/27                       F ( B) = 45 5/9
-1/12х₃ – 17/18х₆ = -8/9 – второе отсечение.

-1/12х₃*(60 – 10х₁- 6х₂) – 17/18*(38 + 3х₁ – 9х₂) = -8/9

-2х₁ + 9х₂ = 40 – уравнение 2-го отсечения.

Х₇= 40 + 2х₁ - 9₂

В М

-38/3

( II )                             (I)
                (2)

                                                                                                                                                                   6

-9

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

В М

С

D

(III)

-9

                                                                                                                           2 16/17
-20 (II)                                                                                              (3)
(1)
-4
Уравнение третьего отсечения:

-3/34х₃ – 16/17х₇ = -16/17

х₇ находится из 2 го ограничения

-3/34 * ( 60 – 10х₁ – 6х₂) – 16/17*(40 + 2х₁ – 9х₂) = -16/17

-х₁ + 9х₂ = 42 – ур. Третьего отсечения

В т. D пересекаются (1) и (III)

10х₁ + 6х₂ = 60

-х₁ + 9х₂ = 42
х₁=3; х₂=5. F(D)=45

т.D (3;5)
Вывод:

экономико-матем. модел. испольузется в экономике для решения различного рода заданий, для оптимизации их. В данной к.р. использованы симплекс метод,….. отсечения Гомори, двойной симплекс метод. Геометрическая интерпретация показывает весь ход решения.
Список використаної літератури:

1.
Кузнецов Ю.Н. “Математическое програмирование:(учебное пособие для экономических специальностей ”

2.
Оптимізація єкономічних показників з врахуванням умови цілочисленності: “Методичні вказівки до виконання курсової роботи з дисципліни “Економіко математичне моделювання для студентів економічних спеціальностей”(Викладач Іванов Л.П. –Чернігів: ЧТІ,1998-20с)”

Bukvasha