Оптимізація показників

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

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

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

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

4x1 — 2×2 = 8 (3) x1=0, (4) x2=0 (5).

Графіком рівняння x1 = 0 є вісь ординат, x2 =0 — вісь абсцисс.

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

2) Визначають область допустимих значень. Область допустимих значень знаходиться в перший чверті координат, т.к. x1, x2(0×1,x2-цілі числа На коорд. Площині вибирають довільну точку й перевіряють виконання тотожністів рівняннях-обмеженнях. Якщо тотожність вірна, то дана нпівплощина — площина напівплощина допустимих рішень.

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

М.

(2).

— 9.

(3).

(1).

— 4.

У М.

(I).

(2).

— 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.

У М.

С.

(II) (I).

(2).

— 9.

2 16/17.

— 20 (II) (3).

(1).

— 4.

У М.

С.

D.

4 (III).

(II) (I).

(2).

— 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с)".

———————————- 9.

38/3.

— 38/3.

— 38/3.