Задача по линейному программированию

  Программированные задания

Вариант № 7 

Задание 1 

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

 

   x₁, x₂, x₃, x₄, x₅ ≥ 0 

Решение:

 
I этап. Избавимся от отрицательных свободных членов, умножив на -1 ограничения 2.

  x₁, x₂, x₃, x₄, x₅ ≥ 0 

          В исходной задаче базисные переменные отсутствуют, это значит, что исходная задача не содержит в себе допустимого базисного решения. Для его нахождения составим расширенную задачу и будем рассматривать ее в симметричной форме (F=- f, тогда поиск min f эквивалентен поиску max F, причем min f = max F).

        Для этого в левые части уравнений системы ограничений введем дополнительные неотрицательные неизвестные x₆ и х₇ . Получим следующую систему ограничений:

 

  x₁, x₂, x₃, x₄, x₅, x₆, x₇ ≥ 0 
 
с базисными переменными x₆, x₇. 

I I этап. Целью решения данной системы является получение допустимого базисного решения, не содержащего искусственных переменных (x₆, x₇).

 Приравняем свободные переменные системы уравнений (ограничений) к  нулю: х₁= х₂= х₃= х₄= х₅=0, получаем начальное опорное решение расширенной задачи х₁ = (0,0,0,0,0,1,1). Вычисляем оценки разложений векторов условий по базису опорного решения и записываем в симплексную таблицу (табл. 1). При этом оценки ∆_ј и F(x₁) для удобства  вычислений записываем в две строки: в первую - слагаемые ∆^'_ј, независящие от коэффициентов x₆ и x₇, во вторую - слагаемые ∆"_ј, зависящие от коэффициентов x₆ и x₇.

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

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

                                                                                                                    Табл.1 
Симплекс-таблица № 1

 

Индексная строка находится по формулам:

 
 

 
 
 
 

      Проверяем критерий оптимальности: начальное  опорное решение не является оптимальным, так как в индексной строке ∆"_ј имеются отрицательные оценки. 

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

IV этап. Построение нового базиса.

      Выбираем  номер вектора х_j вводимого в базис опорного решения, и вектора х_і , выводимого из базиса. Для этого вычисляем приращения целевой функции ∆F_ј при введении в базис каждого из векторов с положительной оценкой и находим минимум этого приращения. При этом слагаемые оценок ∆^'_ј пренебрегаем до тех пор, пока хотя бы одно слагаемое ∆"_ј отлично от нуля. 

min     b_i      = min  (1/5; 1/6) = 1/6.

         a_i2>0

V этап. Определение нового опорного плана.

 Ключевое число 6. Вектор х₇ , выводимый из базиса, исключаем из рассмотрения. Получаем опорное решение х₂ = (0, 1/6, 0, 0, 0, 1/6, 0) с базисом х₂ , х₆ . Составим вторую симплексную таблицу (табл.2) 

                                                                                                                    Табл.2 
Симплекс-таблица № 2

 

      Данное  решение не является оптимальным, так  как векторы х₃, х₄ и х₅ имеют отрицательные оценки. Проделываем со второй симплексной таблицей то же, что и с первой. Получаем новую третью симплекс-таблицу (табл.3). 

                                                                                                                    Табл.3 
Симплекс-таблица № 3

 

      Получено  оптимальное решение расширенной задачи. Все искусственные переменные вышли из базиса и поэтому можно приступить к решению исходной задачи, приняв полученное базисное решение в качестве опорного. Строка ∆"_ј больше не нужна, принятие решения о ключевом столбце, во всех последующих симплекс-таблицах, будем принимать по строке ∆^'_ј . Составим четвертую симплексную таблицу (табл.4).