Симплекс-метод, его сущность

      С практической точки зрения отсутствие допустимых решений свидетельствует  о том, что задача плохо сформулирована. 

      Пример 3.4-1. (Отсутствие допустимых решений) 

      Рассмотрим  следующую задачу. 

      Максимизировать z = 3x1 + 2x2 

      при выполнении условий 

         2x1 + x2 <= 2,

             3x1 + 4x3 >= 12,

      x1, x2 >= 0. 

      Результат применения симплекс-метода представлен  в следующей таблице.

 

      Данные  из этой таблицы показывают, что  в точке оптимума искусственная  переменная R имеет положительное значение (= 4), что свидетельствует об отсутствии допустимого решения. На рис. 3.4 графически представлена ситуация данной задачи. Алгоритмы симплекс-метода, допуская положительные значения искусственной переменной, по существу, превращает неравенство 3x1 + 4x3 >= 12 в 3x1 + 4x3 <= 12. (Объясните, почему так происходит.) В результате получаем то, что можно назвать псевдооптимальным решением. 

      

      Рис. 3.4 
 
 
 
 
 
 
 
 
 
 
 

2. Практическая часть. 

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

      Решить  задачи: 

1. F = 14x1 + 10x2 + 14x3 + 14x4 → max

 

      при ограничениях: 

       4x1 + 2x2 + 2x3 + x4 <= 35;

      x1 + x2 + 2x3 + 3x4 <= 30;

      3x1 + x2 + 2x3 + x4 <= 40;

      xj >= 0, j = 1, 2, 3, 4. 

2. F = x1 + x2 → max

 

      при ограничениях: 

       x1 – 4x2 – 4 <= 0;

      3x1 – x2 >= 0;

      x1 + x2 – 4 >= 0;

      x1 >= 0, x2 >= 0. 
 
 
 
 
 
 
 
 
 
 
 

      Решение. 

1.  F = 14x1 + 10x2 + 14x3 + 14x4 → max

      при ограничениях:

      

      4x1 + 2x2 + 2x3 + x4 <= 35;

      x1 + x2 + 2x3 + 3x4 <= 30;

      3x1 + x2 + 2x3 + x4 <= 40;

      xj >= 0, j = 1, 2, 3, 4. 

      Переведём систему в канонический вид для  решения симплексным методом.

       4x1 + 2x2 + 2x3 + x4 + x5 = 35;

      x1 + x2 + 2x3 + 3x4 + x6 = 30;

      3x1 + x2 + 2x3 + x4 + x7 = 40;

      xj >= 0, j = 1, 2, 3, 4, 5, 6, 7. 

      14x1 + 10x2 + 14x3 + 14x4 + 0x5 + 0x6 + 0x7 → max

      Ответ: max z = 225 при x2 = 5, x3 = 12,5, x7 = 10, x1 = x4 = x5 = x6 = 0. 

      Двухэтапный метод. 

2.   F = x1 + x2 → max 

       при ограничениях:

      x1 – 4x2 – 4 <= 0;

      3x1 – x2 >= 0;

      x1 + x2 – 4 >= 0;

      x1, x2 >= 0. 

      Переведём в канонический вид и добавим  искусственные переменные.

      f = x1 + x2 + 0x3 + 0x4 + 0x5 – Mx0 – Mx7 → max.

      

      x1 – 4x2 – 4 + x3 = 0;

      3x1 – x2 – x4 + x6 = 0;

      x1 + x2 – 4 – x5 + x7 = 0;

      x1, x2, x3, x4, x5, x6, x7 >= 0; 

      Этап 1.

      Z = x6 + x7 → min