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

     Получаем: 

      Находим начальное опорное решение.  Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.

     Получаем  опорное решение Х1 = (0,0,0,24,30,6) с  единичным базисом Б1 = (А4, А5, А6).

     Вычисляем оценки разложений векторов условий  по базису опорного решения по формуле: 

     Δk = CбXk — ck 

     Где Cб = (с1, с2, ... , сm ) — вектор коэффициентов целевой функции при базисных переменных;

     Xk = (x1k, x2k, ... , xmk ) — вектор разложения  соответствующего вектора Ак  по базису опорного решения;

     Ск  — коэффициент целевой функции  при переменной хк. 

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

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

     В последней строке таблицы с оценками Δk в столбце "А0" записываются значения целевой функции на опорном решении Z(X1).

     Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ1 = -2, Δ3= -9 для векторов А1 и А3 отрицательные.

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

     Определим, введение какого из двух векторов приведет к большему приращению целевой функции.

     Приращение целевой функции находится по формуле: . 

     Вычисляем значения параметра θ01 для первого  и третьего столбцов по формуле:

     Получаем  θ01 = 6 при l = 1, θ03 = 3 при l = 1 (табл.1).

     Находим приращение целевой функции при  введении в базис первого вектора  ΔZ1 = — 6*(- 2) = 12, и третьего вектора ΔZ3 = — 3*(- 9) = 27.

     Следовательно, для более быстрого приближения  к оптимальному решению необходимо ввести в базис опорного решения  вектор А3 вместо первого вектора  базиса А6, так как минимум параметра  θ03 достигается в первой строке (l = 1).

     Производим  преобразование Жордана с элементом  Х13 = 2, получаем второе опорное решение  Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (табл.2) 

     Это решение не является оптимальным, так  как вектор А2 имеет отрицательную  оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

     Определяем  номер вектора, выводимого из базиса. Для этого вычисляем параметр θ02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим  второй вектор базиса А4. Производим преобразование Жордана с элементом х22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (табл.3). 

     Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

     Δ1 = 7/2, Δ4 = 2, Δ6 = 7/2.

     Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

5.Заключение 

     Решение задач линейного программирования – это достаточно трудоемкий процесс, особенно при большом числе переменных и ограничений. Поэтому решать такие задачи целесообразно с применением ЭВМ. Табличный симплекс-метод хорошо приспособлен для программирования и машинного счета.

     Существуют  программные реализации симплекс-метода. В настоящее время появились  интегрированные математические  программные системы для научно-технических расчетов: Eureka, PCMatLAB, MathCAD, Derive Maple V, Mathematica 2, Mathematica 3 , и др.

     Широкую  известность и заслуженную популярность  приобрели математические системы  класса MathCAD, разработанные фирмой MathSoft (США). Это единственные математические системы, в которых описание математических задач дается с помощью привычных математических формул и знаков 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

1. Ашманов, С.А. Линейное программирование / С.А.Ашманов. – М.: Наука, 1981. – 304 с.
2. Вентцель, Е.С. Исследование операций: Задачи, принципы, методология / Е.С.Вентцель. – М.: Высшая школа, 2001. – 208 с.
3. Гольдштейн, Е.Г. Линейное программирование: Теория, методы и приложения / Е.Г.Гольдштейн, Д.Б.Юдин. – М.: Наука, 1969. – 736 с.
4. Кофман, А. Методы и модели исследования операций / А.Кофман. – М.: Мир, 1966. – 523 с.
5. Силич, В.А. Системный анализ и исследование операций: учебное пособие / В.А. Силич, М.П. Силич. – Томск: Изд-во ТПУ, 2000. – 96 с.
6. Силич, В.А. Системный анализ экономической деятельности: учебное пособие / В.А.Силич. – Томск: Изд. ТПУ, 2001. – 97 с.
7. Хэмди, А. Таха. Введение в исследование операций. пер. с англ. / А. Таха Хэмди. – М.: Издательский дом «Вильямс», 2007. – 912 с.