Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Задача о ресурсах.
В распоряжении бригады имеются следующие ресурсы: 300 кг металла, 100 м2 стекла, 160 чел.-ч. (человеко-часов) рабочего времени. Бригаде поручено изготовлять два наименования изделий: А и Б. Цена одного изделия А 1 тыс. р., для его изготовления необходимо 4 кг металла, 2 м2 стекла и 2 чел.-ч. рабочего времени. Цена одного изделия Б 1.2 тыс. р., для его изготовления необходимо 5 кг металла, 1 м2 стекла и 3 чел.-ч. рабочего времени. Требуется так спланировать объем выпуска продукции, чтобы ее стоимость была максимальной. Сначала сформулируем задачу математически. Обозначим через количество изделий А и Б, которое необходимо запланировать (т. е. это искомые величины). Имеющиеся ресурсы сырья и рабочего времени зададим в виде ограничений-неравенств: Полная стоимость запланированной к производству продукции выражается формулой Таким образом, мы имеем задачу линейного программирования, которая состоит в определении оптимальных значений проектных параметров являющихся целыми неотрицательными числами, удовлетворяющих линейным неравенствам и дающих максимальное значение линейной целевой функции. Введём дополнительные переменные , такие, чтобы при их прибавлении к левым частям соотношений неравенства превращались в равенства. Тогда ограничения примут вид При этом очевидно, что , , . Заметим, что введение дополнительных неизвестных не повлияло на вид целевой функции, которая зависит только от параметров .Фактически будут указывать остатки ресурсов, не использованные в производстве. Выразим через свободные переменные . Получим В качестве опорного решения возьмем такое, которое соответствует нулевым значениям свободных параметров: Этому решению соответствует нулевое значение целевой функции Положим , и будем увеличивать переменную до тех пор, пока переменные остаются положительными. Отсюда следует, что можно увеличить до значения = 50, поскольку при большем его значении переменная х4 станет отрицательной. Таким образом, полагая = 50, х2 = 0, получаем новое решение Значение целевой функции при этом будет равно Новое решение лучше, поскольку значение целевой функции уменьшилось по сравнению с предыдущим. Следующий шаг начнем с выбора нового базиса. Примем ненулевые переменные в качестве базисных, а нулевые переменные в качестве свободных. Получим
Выражение для целевой функций запишем через свободные параметры. Получим Отсюда следует, что значение целевой функции по сравнению с предыдущей можно уменьшить за счет увеличения х2 поскольку коэффициент при этой переменной в отрицательный. При этом увеличение недопустимо, поскольку это привело бы к возрастанию целевой функции; поэтому пусть =0. Быстрее всех нулевого значения достигнет переменная при х2 = 30. Дальнейшее увеличение х2 поэтому невозможно. Следовательно, получаем новое опорное решение, соответствующее значениям х2 = 30, = 0 и тогда При этом значение целевой функции равно Покажем, что полученное решение является оптимальным. Для проведения следующего шага ненулевые переменные , , , нужно принять в качестве базисных, а нулевые переменные х4, х5 — в качестве свободных переменных. В этом случае целевую функцию можно записать в виде
Поскольку коэффициенты при , положительные, то при увеличении этих параметров целевая функция возрастает. Следовательно, =71 является оптимальным. Таким образом, ответ на поставленную задачу об использовании ресурсов следующий: для получения максимальной суммарной стоимости продукции при заданных ресурсах необходимо запланировать изготовление изделий А в количестве 35 штук и изделий Б в количестве 30 штук. Суммарная стоимость продукции равна 71 тыс. р. При этом все ресурсы стекла и рабочего времени будут использованы, а металла останется 10 кг.
|