3. Задача линейного программирования

Задача 3. Для изготовления двух видов продукции и используют четыре вида ресурсов , , , . Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, а также прибыль, получаемая от реализации единицы продукции, приведены в таблице (цифры условные)

Найти такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

Требуется:

1) Составить математическую модель данной задачи.

2) Решить полученную задачу линейного программирования графическим методом.

3) Решить задачу симплекс-методом.

Решение:

1) Для составления математической модели поставленной задачи сначала введем переменные:

- количество единиц продукции , планируемое к выпуску;

- количество единиц продукции , планируемое к выпуску.

Затем запишем выражение целевой функции, имеющей смысл суммарной прибыли от реализации выпущенной продукции: .

Далее составим систему ресурсных ограничений (затраты соответствующего ресурса не должны превышать его запаса):

По смыслу задачи переменные должны быть неотрицательными:

, .

В результате получаем математическую модель стандартной задачи линейного программирования в нормальной форме ([3]):

Найти такие значения переменных и , которые удовлетворяют системе линейных неравенств

и доставляют наибольшее значение целевой функции

.

2) при решении поставленной выше задачи линейного программирования графическим методом будем следовать приведенному в работе [4] алгоритму графического метода.

В системе координат на плоскости переменных построим выпуклый многоугольник допустимых значений переменных. Для этого сначала построим ограничивающие этот многоугольник прямые, уравнения которых получаются заменой в ограничениях на переменные знаков неравенств на соответствующие равенства:

, опорные точки (0; 6) и (18, 0);

, опорные точки (0; 16) и (8, 0);

(горизонтальная прямая);

(вертикальная прямая);

(ось );

(ось ).

Затем определим полуплоскости, задаваемые каждым из неравенств системы ограничений, и находим пересечение выделенных полуплоскостей. В результате получаем многоугольник .

Далее находим вектор-градиент целевой функции и строим его, прикладывая в начале координат. Заметим, что целевая функция возрастает в направлении вектора-градиента. После этого строим нулевую линию уровня целевой функции , которая проходит через начало координат и перпендикулярна вектору-градиенту .

Затем передвигаем нулевую линию уровня параллельно самой себе в направлении вектора-градиента до тех пор, пока она не займет предельное крайнее положение по отношению к выпуклому многоугольнику . Этим положением является точка (см. рис.).

Наконец, определяем на пересечении каких ограничивающих прямых лежит угловая точка : ; находим координаты этой точки, решая соответствующую систему уравнений

имеем (6; 4), т.е. , ; и вычисляем значение целевой функции в этой точке:

.

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

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

;

где .

Краткое описание алгоритма симплекс-метода содержится в работе [5], схему и терминологию которого мы будем использовать ниже.

Включим выражение целевой функции в систему уравнений канонической формы задачи и представим ее в специальном виде:

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

СТ-0

Все переменные специальной системы оказались разбитыми на две группы:

- базисные переменные , , , (в СТ-0 им соответствуют "единичные" столбцы) и

- свободные переменные , (им соответствуют не "единичные" столбцы в СТ-0).

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

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

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

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

Далее находим отношения свободных членов СТ-0 к соответствующим положительным коэффициентам выделенного разрешающего столбца:

; ;

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

Далее вычисления организуются в следующем порядке:

- разрешающая строка делится на разрешающий элемент и переписывается в новую симплекс-таблицу СТ-1;

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

Этим заканчивается процедура однократного замещения, и в результате получаем новую симплекс-таблицу

СТ-1

Новое опорное решение: , , , , , , а соответствующее ему базисное значение целевой функции .

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

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

СТ-2

СТ-3

Таким образом, оптимальное решение рассматриваемой задачи линейного программирования выражается равенствами

, , , , , , а соответствующее ему оптимальное значение целевой функции .

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

,

то для приведения задачи к канонической форме следует заменить каждое такое неравенств равносильной ему системой соотношений:

где - дополнительная неотрицательная балансовая переменная.

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