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

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. Ашманов, С.А. Линейное программирование / С.А.Ашманов.
2. Вентцель, Е.С. Исследование операций: Задачи, принципы, методология / Е.С.Вентцель
3. Гольдштейн, Е.Г. Линейное программирование: Теория, методы и приложения / Е.Г.Гольдштейн, Д.Б.Юдин
4. Кофман, А. Методы и модели исследования операций / А.Кофман. – М.: Мир, Силич, В.А. Системный анализ и исследование операций: учебное пособие
5. Силич, В.А. Системный анализ экономической деятельности: учебное пособие.
6. Хэмди, А. Таха. Введение в исследование операций. пер. с англ. / А. Таха