Рефераты - Афоризмы - Словари
Русские, белорусские и английские сочинения
Русские и белорусские изложения
 

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

Работа из раздела: «Экономико-математическое моделирование»

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



                (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


( 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с)”

-----------------------
9

38/3

-38/3

-38/3




ref.by 2006—2022
contextus@mail.ru