Курсовая: Оптимизация показателей

Для вирішення задачі лінейного програмування, потрібно записати вихідну задачу в формі задачі лінейного програмування, а потім застосовувати симплекс-метод . Основною задачею лінійного програмування – задача для якої: 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	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/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с)”