Задачи, сводящиеся к задаче линейного программирования

Задача о наилучшем использовании ресурсов

Пусть предприятие может выпускать n видов продукции. Выпуск ограничен m видами ресурсов. Пусть b _i, i = – имеющееся количество единиц i -го ресурса. Известна экономическая выгода, получаемая от единицы продукции каждого вида. Пусть, для определенности, это будет c _j – цена единицы продукции j –го вида j = . Технологические коэффициенты a _ij – показывают, сколько единиц i -го ресурса требуется для производства единицы j –го вида продукции i = , j = .

Пусть x _j – количество производимой продукции j –го вида. Вектор называется планом производства. Суммарная стоимость всей продукции при таком плане составит

.

Требуется выбрать такой план выпуска продукции x, удовлетворяющий всем ограничениям по ресурсам (x X), чтобы суммарная стоимость всей продукции была максимальной.

Запишем ограничения по ресурсам. Для этого нужно ответить на вопрос, сколько i -го ресурса будет истрачено на выпуск первого вида продукции. При выпуске единицы продукции первого вида его будет истрачено a _i1, а для выпуска x ₁ – a _i1 x ₁ единиц. В сумме по всем видам продукции будет израсходовано i -го ресурса. Нельзя израсходовать этого ресурса больше, чем имеется, т.е. больше, чем b _i. Следовательно, получаем неравенство

.

Это неравенство будет выполняться для всех i = . Величины выпускаемой продукции x _j j = не могут быть отрицательными, т.е. . В результате получаем следующую задачу линейного программирования

(1.5)

Задача о смесях

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

Рассмотрим такую задачу на примере составления пищевого рациона. Пусть имеются продукты, которым присвоены номера 1, 2,…, n. Они содержат различные питательные вещества, обозначаемые номерами 1, 2,…, m, например белки, углеводы и т.д. Для нормальной жизнедеятельности в заданный промежуток времени требуется не менее b _i единиц i -го питательного вещества. Пусть c _j – стоимость j –го продукта. Требуется выбрать на рассматриваемый период рацион (определить количество потребления каждого продукта) минимальной стоимости так, чтобы в потребляемых продуктах количество всех питательных веществ было не ниже нормы. Обозначим x _j j = , количество j –го продукта в рационе. Тогда стоимость всех продуктов, входящих в рацион, будет равна

.

Теперь задачу о смесях можем записать в виде

Дата добавления: 2014-12-27