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

В распоряжении бригады имеются следующие ресурсы: 300 кг металла, 100 м² стекла, 160 чел.-ч. (человеко-часов) рабо­чего времени. Бригаде поручено изготовлять два наименования изделий: А и Б. Цена одного изделия А 1 тыс. р., для его изготовления необходимо 4 кг металла, 2 м² стекла и 2 чел.-ч. рабочего времени. Цена одного изделия Б 1.2 тыс. р., для его изготовления необходимо 5 кг металла, 1 м² стекла и 3 чел.-ч. рабочего времени. Требуется так спланировать объем выпуска продукции, чтобы ее стоимость была максимальной.

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

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

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

Введём дополнительные переменные , такие, чтобы при их прибавлении к левым частям соотношений неравенства превращались в равенства. Тогда ограничения примут вид

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

Выразим через свободные переменные . Получим

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

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

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

Таким образом, полагая = 50, х₂ = 0, получаем новое решение

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

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

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

Получим

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

Отсюда следует, что значение целевой функции по сравнению с предыдущей можно уменьшить за счет увеличения х₂ поскольку коэффициент при этой переменной в отрицательный. При этом увеличение недопусти­мо, поскольку это привело бы к возрастанию целевой функции; поэтому пусть =0.

Быстрее всех нулевого значения достигнет переменная при х₂ = 30. Дальнейшее увеличение х₂ поэтому невозможно. Следо­вательно, получаем новое опорное решение, соответствующее значени­ям х₂ = 30, = 0 и тогда

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

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

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

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