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

ВВЕДЕНИЕ

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

Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит:

1) умение находить начальный опорный план;

2) наличие признака оптимальности опорного плана;

3) умение переходить к нехудшему опорному плану.

2.1 Цель

Усвоить алгоритм решения задач линейного программирования симплексным методом, М-метод.

2.2 Задачи

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

2.3 Алгоритм решения

Предварительный шаг: приведение задачи к каноническому виду.

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

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

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

3. Найдем предельное значение переменной, за счет которой можно улучшить значение целевой функции. Увеличение значения этой переменной допустимо до тех пор, пока одна из m переменных, вошедших в пробное решение не обратится в нуль.

. Разрешим систему из n уравнений относительно переменной, вошедшей в новое пробное решение. Вернемся ко второму этапу.

Пример решения задачи

Найти оптимальное сочетание посевов пшеницы и сахарной свеклы, обеспечивающий максимум прибыли. Под эти культуры хозяйство выделило ресурсы 1000 га пашни, 18000 чел.- дней труда, 3000 ц минеральных удобрений. В таблице 2.1 представлены исходные показатели.

Таблица 2.1 Исходные показатели

Решение.

Переменные:

Х1 - площадь под пшеницу, га;

Х2 - площадь под сахарную свеклу, га.

Ограничения:

. По площади пашни, га

X1 +Х2 ≤ 1000,

. По затратам труда, чел.-дней

Х1 +40Х2 ≤ 18000;

. По использованию минеральных удобрений, ц

Х1 +9Х2 ≤ 3000;

Z (мах прибыли, руб.) =150Х1 +300Х2 → max.

Решение задачи

Предварительный шаг. Приведем к каноническому виду:

х1 +40х2 +х3 =18000,

х1 +9х2 +х4 =3000,

х1 +х2+х5 =1000.

Х1 , Х2 ³ 0,

Z =150х1 +300х2+ 0х3 +0х4 +0х5 → max.

Интерация 1.