Пример 1.5

Вспомним пример 1.1.

Фирма производит две модели А и В сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3 м2 досок, а для изделия модели В - 4 м². Фирма может получить от своих поставщиков до 1700 м2 досок в неделю. Для каждого изделия модели А требуется 12 мин машинного времени, а для изделия модели В - 30 мин. В неделю можно использовать 160 ч машинного времени. Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие

модели А приносит 2 дол. прибыли, а каждое изделие модели В - 4 дол. прибыли? Чтобы сформулировать эту задачу математически, обозначим через x ₁количество выпущенных за неделю полок модели А, а через x ₂- количество выпущенных полок модели В. Задача состоит в том, чтобы найти наилучшие значения x ₁и x ₂. Очевидно, наилучшими для данной задачи являются такие значения, которые максимизируют еженедельную прибыль.

Предположим, что недельная продажа ограничена 450 полками. Тогда должно быть включено дополнительное ограничение x1+x2≤450.

В виде уравнения оно записывается как x1+x2+x5=450, где – дополнительная переменная.

Это ограничение нарушается оптимальным решением исходной задачи. Необходимо ли решать эту задачу с самого начала с новым включением? Если так поступить и повторить проведенные вычисления, то дополнительное ограничение выразится через небазисные переменные, которые можно получить из текущей канонической формы

Поэтому уравнение x1+x2+x5=450 после исключения и принимает вид

Последняя таблица будет иметь следующий вид (изменения - только вид дополнительного

ограничения):

Здесь возникают определенные трудности. В этой канонической форме для базиса , , целевая функция имеет такой же вид, как оптимальная, однако базис не допустим, т. к. переменная отрицательна. Существует ли, несмотря на это, способ coxpaнить результаты проделанной к этому моменту полезной работы? Да, и соответствующая процедура носит название двойственного симплекс-метода.

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

В нашей задаче базисная переменная отрицательна и является кандидатом на удаление из базиса. Какая переменная должна ее заменить? В строке X₅ таблицы ищется отрицательный ведущий элемент, такой, что при последующих преобразованиях коэффициенты целевой функции будут оставаться положительными. Перед формализацией этих правил посмотрим, как они выполняются в нашей задаче. В строке имеется только один отрицательный коэффициент – коэффициент при x₃, равный -3/7. Если мы разделим уравнение на -3/7, чтобы включить в базисные переменные переменную x₃ (с коэффициентом 1), то получим уравнение

т. е. значение станет положительным. Следующим шагом мы должны исключить переменную из остальных ограничений и из целевой функции. Это достигается простыми симплексными вычислениями результаты, как показано ниже, могут быть сведены в таблицу. Ведущий элемент (отрицательное значение -3/7) отмечен звездочкой.

В конечной таблице приведено оптимальное решение новой задачи:

причем

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

Литература.

1) Банди Б Основы линейного программирования, 1989г.

2) Грызина Н.Ю., Мастяева И.Н., Семенихина О.Н. Математические методы исследования операций в экономике: Учебно-методический комплекс. – М.: Изд. центр ЕАОИ, 2008. – 204 c.

Поиск по сайту: