Примеры постановки задач ЛП

Задача ЛП

Если целевая функция и все функции линейны, – это случай задачи линейного программирования. Если хотя бы одна из этих функций нелинейна, – это случай задачи нелинейного программирования. Стандартный метод решения задач оптимизации при большом числе переменных и ограничений неэффективен. Для конкретного вида задач, например задач ЛП, созданы эффективные специальные методы.

Задачу ЛП можно записать в следующем виде:

,

где .

Введем матрицу коэффициентов ограничений A и векторы переменных и правых частей :

, , .

За счет изменения знака в обеих частях приведем все неравенства к неравенствам одного вида и запишем систему ограничений в матричном виде: .

Так как

, (1)

вместо задачи минимизации функции (рис.5) можно рассматривать максимизацию функции . Поэтому задачу ЛП всегда можно привести к стандартной форме: .

  Рис.5. Максимизация и минимизация функций    

Экономические задачи оптимизации, связанные с планированием производства или распределением продуктов (изделий), являются задачами ЛП. Если рассматривать доходы, то это будут задачи максимизации, а если расходы – задачи минимизации. При этом значения переменных имеют смысл планируемого количества разных продуктов и являются неотрицательными: . В дальнейшем эти ограничения (смысловые ) считаются выполненными. Если задача ЛП приведена к стандартной форме, то является вектором цен на соответствующие продукты, – постоянная составляющая дохода (или расхода), а целевая функция выражает величину дохода (расхода). Матрица ограничений является коэффициентом использования набора ресурсов, запасы которых заданы вектором ресурсов .

В силу такой экономической интерпретации вектор называется планом. При этот план допустимый. Если – допустимый план и , то этот план – оптимальный.

При непрерывности целевой функции и нестрогости всех ограничений (область ограничений замкнута) такая задача оптимизации может не иметь решения только в двух случаях:

1) область ограничений пуста: Ǿ (ограничения несовместны);

2) целевая функция неограниченна на неограниченной области ( или ).

Задача о производстве. Мастерская изготавливает столы и шкафы. В запасе имеется 15 и 10 м³ древесины 1-го и 2-го сорта соответственно, а также ресурсы труда – 200 человеко-ч. Расходы ресурсов на производство одного изделия следующие:

Изделия	1 сорт	2 сорт	Ресурсы труда
Стол	0,5	0,2
Шкаф	1,2

Доход от продажи одного стола равен 100 условных единиц, а от продажи одного шкафа – 150 условных единиц.

Найти план производства, максимизирующий доход.

Поставим задачу математически. Пусть запланированное количество столов равно , а шкафов – , т.е. план производства . Тогда ограничения по ресурсам, соответственно по использованным для производства древесины 1-го, 2-го сорта и труду, примут вид следующих неравенств:

Ясно, что выполняются и смысловые ограничения .

Доход, т.е. целевая функция этой задачи, при выполнении плана равен . Таким образом, математически задача оптимизации плана производства сводится к задаче ЛП:

Задача о диете. Из двух продуктов и надо составить диету, которая удовлетворяет ежесуточной потребности организма в белках, жирах, углеводах и требует наименьших затрат. Распределение белков, жиров и углеводов по продуктам, потребности организма и стоимости продуктов следующие:

Продукты	Белки	Жиры	Углеводы	Стоимость 1 кг
A	а 1	а 2	а 3	S 1
B	b 1	b 2	b 3	S 2
Потребность	a	b	c

Если – количество продукта A и – количество продукта B, т.е. рацион , то затраты , а ограничения состоят в покрытии потребностей соответственно по белкам, жирам и углеводам:

где .

Дата добавления: 2017-02-01