Общие положения. Симплексный метод - это универсальный метод линейного программирования

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

Когда рассматриваемая модель содержит т уравнений ограничений, вычислительная процедура симплексного метода за­ключается в следующем:

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

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

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

Шаг 4. Разрешим систему т. уравнений относительно переменных, вошедших в новое пробное решение. Исключим эти переменные из вы­ражения для целевой функции. Вернемся к шагу 2.

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

Задача 8.9. Корма трех видов В₁, В₂, В₃ содержат определенное количество питательных веществ А₁, А₂, A₃. Цены, по которым поку­паются эти корма, различны. Требуется составить кормовой рацион, со­стоящий из указанных кормов, так, чтобы в нем было не менее заданных ко­личеств питательных веществ и чтобы он был самым дешевым.

Задача 8.10. Есть три вида станков: А₁, А₂, А₃. На этих станках по­следовательно обрабатываются детали четырех видов: В₁, В₂, В₃, б₄. Известно сколько часов каждая деталь изготавливается на каждом стан­ке, сколько времени может проработать каждый станок и какая при­быль может быть получена от продажи детали каждого типа. Требуется найти оптимальный план работы станков, чтобы получить максималь­ную прибыль.

Задача 8.11. Имеются автомобили трех типов А_1; A₂, A₃, рабо­тающие на перевозке однородного груза у трех потребителей В₁, В₂, В₃. Известна производительность каждого автомобиля у каждого по­требителя и себестоимость использования автомобиля. Требуется так закрепить автомобили за потребителями, чтобы была наименьшая се­бестоимость (максимальная производительность) и др.

Дата добавления: 2015-08-09