Общая постановка задачи линейного программирования

Однородные дифференциальные уравнения первого порядка

Общей задачей линейного программирования (ОЗЛП) называют задачу

где , , − заданные действительные числа; (1) – целевая функция, (2)-(6) – ограничения; – план задачи.

Оптимальным планом называется такой план , при котором линейная функция (1) принимает оптимальное (максимальное или минимальное) значение.

Если система ограничений содержит линейные неравенства и уравнения, то задача называется общей, если только уравнения − основной. Частным случаем основной задачи является задача каноническая, определение которой будет дано ниже. Любая задача линейного программирования может быть записана в одной из трех форм: общей, основной или канонической.

Симметричной формой записи ЗЛП называют задачу

Канонической формой записи ЗЛП называют задачу

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

Задача планирования производства продукции.

Для производства продукции n типов требуются ресурсы m видов. Нормы расхода ресурсов на производство единицы продукции каждого типа заданы матрицей , где – количество ресурса i –го вида, необходимое для производства единицы продукции j -го типа. Известно количество ресурсов каждого вида, которое имеется в наличии у предприятия. Известны также величины прибыли , которую получит предприятие при реализации единицы продукции j -го типа. Требуется найти оптимальный план производства продукции, т.е. количество продукции каждого типа, которое нужно произвести, чтобы получить наибольшую прибыль. Условие задачи можно представить в виде таблицы 1.

Таблица1 Исходные данные к задаче планирования производства продукции

Ресурсы	Продукция	Наличие ресурсов
Тип 1	Тип 2	…	Тип
Ресурс 1			…
…	…	…	…	…	…
Ресурс			…
Прибыль			…

Обозначим через – количество продукции j -го типа, которое планируется выпустить . Тогда математическая модель задачи будет выглядеть следующим образом:

(2.1)

(2.2)

(2.3)

Целевая функция (2.1) этой задачи представляет собой общую прибыль от производства всей продукции. Ограничения (2.2) выражают условие того, что потребление ресурса i -го вида не должно превышать запаса этого ресурса. Условия неотрицательности переменных (2.3) вытекают из смысла переменной : количество продукции не может быть отрицательным.

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

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

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

Модель задачи о наилучшем составе смеси рассмотрим на примере задачи о диете. Имеются пищевые продукты, известные под номерами 1, 2, …, n. Они содержат различные питательные вещества, обозначаемые номерами 1, 2, …, m (углеводы, белки, жиры, витамины, микроэлементы и др.). Единица -того продукта содержит единиц -го питательного вещества. Для нормальной жизнедеятельности в заданный промежуток времени нужно потреблять не менее единиц -го питательного вещества. Обозначим через стоимость единицы продукта -того вида. Требуется выбрать рацион минимальной стоимости, содержащий необходимые количества питательных веществ. План задачи – это количества продуктов каждого вида, обеспечивающие необходимое количество питательных веществ при минимальных затратах на исходные продукты.

Математическая модель задачи имеет вид:

(),

().

Дата добавления: 2015-04-24