Курс лекций

АЭРОКОСМИЧЕСКИЙ КОЛЛЕДЖ

Задача о ресурсах.

В распоряжении бригады име­ются следующие ресурсы: металла, стекла, человеко-часов рабочего времени. Бригаде поручено изготовлять два наименования изделий - и . Цена одного изделия , для его изготовления необходимо металла, стекла и человеко-часов рабочего времени. Цена одного изделия , для его изготов­ления необходимо металла, стекла и человеко-часов рабочего времени. Требуется так спланировать объем вы­пуска продукции, чтобы ее стоимость была максимальной.

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

(1).

Полная стоимость запланированной к производству про­дукции выражается формулой

(2).

Таким образом, мы имеем задачу линейного програм­мирования, которая состоит в определении оптимальных значений проектных параметров , являющихся це­лыми неотрицательными числами, удовлетворяющих ли­нейным неравенствам (1) и дающих максимальное значение линейной целевой функции (2).

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

(3).

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

(4).

То получим задачу минимизации для этой целевой функции.

Примем переменные в качестве базисных и выразим их через свободные переменные из уравнений (3). Получим

(5).

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

, , , , (6).

Этому решению соответствует нулевое значение целевой функции (4):

(7).

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

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

Таким образом, полагая , , получаем но­вое опорное решение (значения переменных найдем по формулам (5)):

, , , , (8).

Значение целевой функции (4) при этом будет равно

(9).

Новое решение (8), следовательно, лучше, поскольку значение целевой функции уменьшилось по сравнению с (7).

Следующий шаг начнем с выбора нового базиса. При­мем ненулевые переменные в (8) в качестве базисных, а нулевые переменные в качестве сво­бодных. Из системы (3) найдем

(10).

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

(11).

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

Максимальное значение переменной определяется соотношениями (10). Быстрее всех нулевого значения достигнет переменная при . Дальнейшее увели­чение поэтому невозможно. Следовательно, получаем новое опорное решение, соответствующее значениям , и определяемое соотношениями (10):

, , , , (12).

При этом значение целевой функции (11) равно

(13).

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

.

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

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