Модифицированный симплекс метод

Таблица 2.

 

Находим вектор  Ω⁽¹⁾:

λ₁⁽¹⁾ =М*1+М*0+М*0=М

λ₂⁽¹⁾ =М*0+М*1+М*0=М

λ₃⁽¹⁾ =М*0+М*0+М*1=М

F₀= - М*12 - М*18 - М*32= - 62М

Находим числа  ∆_j⁽¹⁾:

∆₁=

∆₂=

∆₃= -М*4-М*2-М*0+4=-6М+4

∆₄=

∆₅=

∆₆= - М * 1-М * 3-М * 0+2= -12М+2

∆₇= - М * (-1) - М * 0 - М * 0-0=М

∆₈= -М * 0 - М * (-1) - М * 0 - 0=М

∆₉=-М * 0 - М * 0 - М *(-1) - 0=М

     Так как среди чисел имеются отрицательные, то исходный опорный план не является оптимальным. Перейдем к новому опорному плану. Введем в базис вектор Р₆ и выведем Р₁₂. Строим новую таблицу (3).

Таблица 3.

 

Находим вектор  Ω⁽²⁾:

λ₁=

λ₂ =

λ₃=М*

F₀= 

Находим числа  ∆_j⁽²⁾:

∆₁ = -3М+2

∆₂ = 5М+ 3/4

∆₃ =  -6М+4

∆₄ =

∆₅ = - 4М+11/2

∆₆ = -12М+2

∆₇ = М

∆₈ = М

∆₉ = М

     Так как среди чисел имеются отрицательные, то исходный опорный план не является оптимальным. Перейдем к новому опорному плану. Введем в базис вектор Р₃ и выведем Р₁₀. Строим новую таблицу (4).

     Таблица 4.

 

Находим вектор  Ω⁽³⁾:

λ₁ = - 4* ¼ +М* ½ +2*0 = - ½ М+1

λ₂ = -4*0 + М*1 -2 * 0 = М

λ₃ = - 4 * ( - 1/32 ) + М * ( - 5/16) – 2* 1/8 = -

F₀= - 2М - 16

Находим числа  ∆_j⁽³⁾:

∆₁= 0

∆₂= ½ М + 15/4

∆₃= 0

∆₄= 2М+3

∆₅= - 5/2 М +5/2

∆₆= 0

∆₇= - ½ М +1

∆₈= М

∆₉= - 5/16 М + 1/8

     План  не оптимален. Выводим из базиса Р₁₁ и вводим Р₅. Составляем новую таблицу (5).

       Таблица 5.

 

Находим вектор  Ω⁽⁴⁾:

λ₁ = - 4* 3/10 + 3* 1/5 +2 * 1/20 = ½

λ₂ = 4*1/10 – 3* 2/5 – 2*1/10 = 1

λ₃ = -4*0 + 3* 1/8 – 2 * 3/32 = 3/16

F₀= - 4* ½ -3*1 -2* (-3/16) = -18

Находим числа  ∆_j⁽⁴⁾:

∆₁= 0

∆₂=  17/4

∆₃= 0

∆₄= 5

∆₅= 0

∆₆= 0

∆₇= ½

∆₈= 1

∆₉=  - 3/16

     Полученный  план не оптимален. Выводим из базиса Р₅ и вводим Р₉. Строим новую таблицу (6).

     Таблица 6.

 
 

Находим вектор  Ω⁽⁵⁾:

λ₁ = - 4*3/10 + 0* (- 8/5) + 2* 1/5 = 4/5

λ₂ = -4* (-1/10) +0* 16/5 -2* 2/5 = 2/5

λ₃ = -4*0+0*(-1)-2*0=0

F₀= -4* 9/5 + 32/5*0 – 2* 24/5 = -84/5

Находим числа  ∆_j⁽⁵⁾:

∆₁= 0

∆₂= 79/20

∆₃= 0

∆₄= 19/5

∆₅= 3/2

∆₆= 0

∆₇= 4/5

∆₈= 2/5

∆₉= 0

     Так как все ∆_j⁽⁵⁾ то задача имеет множество оптимальных планов –

     х = (0, 0, 9/5, 0, 0, 24/5, 0, 0, 32/5)

     F_min= - 84/5

     Ответ:  Данная задача линейного программирования имеет оптимальный план х = (0, 0, 9/5, 0, 0, 24/5, 0, 0, 32/5). При этом плане целевая  функция задачи принимает свое минимальное  значение F_min= - 84/5. 
 

     Заключение.

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

      В настоящее время новейшие достижения математики и современной вычислительной техники находят все более  широкое применение как в экономических  исследованиях и планировании, так  и в других задачах. Этому способствует развитие таких разделов математики как математическое программирование, теория игр, теория массового обслуживания, а также бурное развитие быстродействующей  электронно-вычислительной техники. Уже  накоплен большой опыт постановки и  решения экономических и тактических  задач с помощью математических методов. Особенно успешно развиваются  методы оптимального управления. Экономика  и производство развивается быстро там, где широко используются математические методы. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Список  используемой литературы 

1. С. А. Ашманов  «Линейное программирование» ,1981г.
2. И.Л. Акулич  « Математическое программирование в примерах и задача», 1986г.
3. А. В. Кузнецов « Высшая математика. Математическое программирование»,1994г.
4. В. Г. Карманов «Математическое программирование», 2001г.