Решение задач линейного программирования симплекс методом

Министерство  образования Российской Федерации

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ  
«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» 
 
 
 
 

Отчет по лабораторной работе №3

по дисциплине

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

на  тему:

«Решение  задач линейного  программирования симплекс методом»

Вариант 14

                                   Руководитель работы

                                                           _______________ Шаяхметова Р.М.

                                            «____»____________2011г.

                  Исполнитель

                                       Студентка группы 09ФК-1

                                                             ________________ Кофейникова О.Ю.

                                             «____»_____________2011г. 
 
 
 

Оренбург 2011

Постановка  задачи

Задача  №1. Найти решение задачи линейного  программирования:

2) Симплекс методом для b) на max(min) и для с) на max

b)F = 5x₁ - x₂ →max (min)

-x₁ + 7x₂ ≤ 14

 x₁ +5x₂ ≥ 20

x₁ ≥ 0 ,  x₂ ≥ 0

c)F = 3x₁ + x₂ →max

x₁ - 2x₂ ≥ 6

 -x₁ + x₂ ≥ 8

x₁ ≥ 0 ,  x₂ ≥ 0 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

b)F = 5x₁ - x₂ →max

-x₁ + 7x₂ ≤ 14

 x₁ +5x₂ ≥ 20

x₁ ≥ 0 ,  x₂ ≥ 0

1. Приведем задачу к каноническому виду:

F(x₁ + x₂ + x₃ + x₄ ) = 5 * x₁ - x₂ + 0 * x₃ + 0 * x₄ → max

-x₁ + 7x₂ +x₃= 14

 x₁ +5x₂ – x₄= 20

x_j ≥ 0, j = 1,4

А₁ =   1 ; А₂ =  7 ;      А₃ =   1 ;        А₄ =   0 .    

          -1  5                         0  -1                             

     Так как базис не полный следовательно необходимо перейти к решению вспомогательной задачи.

G(x,y₁) = -y₁ → max  

-x₁ + 7x₂ +x₃ = 14

 x₁ +5x₂ – x₄ + y₁ = 20 

x_j ≥ 0, j = 1,4; y₁ ≥ 0

А₁ =   1 ; А₂ =  7 ;      А₃ =   1 ;        А₄ =   0 .  А₃ =   0   

          -1  5                         0  -1                   1

B = 14

       20

Решаем  вспомогательную задачу симплекс методом

                                 

Строим  симплекс таблицу.

 

Строим 2-ую симплекс таблицу, так как строка оценок имеет отрицательные значения.

Строим  3-тью симплекс таблицу, так как строка оценок имеет отрицательные значения.

 

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

Так как оценки отрицательные и значения отрицательные, следовательно, задача на max не разрешима. 

Решаем задачу на min.

F = -5x₁ + x₂ → min

-x₁ + 7x₂ ≤ 14

 x₁ +5x₂ ≥ 20

x₁ ≥ 0 ,  x₂ ≥ 0

1. Приведем задачу к каноническому виду:

F(x₁ + x₂ + x₃ + x₄ ) = -5 * x₁ + x₂ + 0 * x₃ + 0 * x₄ → min

-x₁ + 7x₂ +x₃= 14

 x₁ +5x₂ – x₄= 20

x_j ≥ 0, j = 1,4

А₁ =   1 ; А₂ =  7 ;      А₃ =   1 ;        А₄ =   0 .     

          -1  5                         0  -1                             

     Так как базис не полный  следовательно необходимо перейти  к решению вспомогательной задачи. 

G(x,y₁) = -y₁  →min  

-x₁ + 7x₂ +x₃ = 14

 x₁ +5x₂ – x₄ + y₁ = 20 

 x_j ≥ 0, j = 1,4; y₁ ≥ 0 

А₁ =   1 ; А₂ =  7 ;      А₃ =   1 ;        А₄ =   0 .  А₅ =   0   

          -1  5                         0  -1                   1

B = 14

       20

Решаем  вспомогательную задачу симплекс методом

Строим  симплекс таблицу.

 

Строим 2-ую симплекс таблицу, так как строка оценок имеет отрицательные значения.