Формализация задач ЛП

Ниже рассмотрены примеры построения формальных моделей типовых задач ЛП.

Пример 2.1. Задача оптимального использования ресурсов.

Предприятие имеет в своем распоряжении определенное количество ресурсов: рабочая сила, финансы, сырьё, оборудование, производственные площади и т.п.

Рассмотрим пример, когда предприятие ограничено ресурсами трех видов: рабочая сила, сырье и оборудование. Предприятие может выпускать гобелены четырех видов: «Пейзаж», «Закат», «Меланхолия», «Орнамент». Количество трех видов ресурсов ограничено суточными объемами: труд – 700 (чел./часов), оборудование – 280 (станко/часов), сырье – 300 (кг). Информация о нормах расхода каждого ресурса на один гобелен каждого вида, и доходах, получаемых от продажи единицы товара, приведена в таблице:

Ресурсы	Нормы расхода ресурсов на единицу изделия	Лимит ресурсов
«Пейзаж»	«Закат»	«Меланхолия»	«Орнамент»
Труд
Оборудование
Сырьё
Цена (тыс.руб.)

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

Обозначим через х₁, х₂, х₃, х₄ количество гобеленов каждого вида произведенных в течении рабочего дня. Тогда экономико – математическую можно представить в виде:

найти

при ограничениях на ресурсы

Пример 2.2. Задача о размещении средств.

Предприятие на планируемый год имеет собственных средств 80 млн. руб. Часть этих средств, но не менее 30 млн. руб. размешается в инвестиционных проектах. Эти активы являются неликвидными, так как не могут быть быстро конвертируемы в наличные средства в случае необходимости.

Часть средств инвестируется в ценные бумаги, которые можно легко реализовать без большого убытка. Финансовый менеджмент предприятия накладывает ограничение по ликвидности на уровне 25%, то есть ценные бумаги должны составлять не менее 25% от общей суммы размещенных средств.

Обозначим через х₁ – средства, размещенные в проектах, а через х₂ – средства, размещенные в ценных бумагах. Целью предприятия является получение максимальной прибыли от вложенных средств. Пусть средняя доходность по проектам составляет 10% годовых, а по ценным бумагам 18% годовых.

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

найти

при условиях

Пример 2.3. Задача составления рациона (задача о диете, задача о смесях).

Имеется два вида корма А и Б, содержащего питательные вещества (витамины, микроэлементы и т.п.) D₁, D₂ и D₃. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум и их необходимый минимум в суточном рационе, а также стоимость 1 кг корма приведены в таблице:

Питательное вещество	Число ед. питательного вещества в 1 кг. корма	Необходимый минимум
А	Б
D1
D2
D3
Цена 1 кг, руб.

Обозначим через х₁ и х₂, количество кг кормов А и Б в суточный рацион. Тогда задача ЛП на минимизацию стоимости суточного рациона с удовлетворением требований по содержанию в рационе необходимого количества питательных веществ будет иметь вид:

найти

При ограничениях на ресурсы

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

Пример 2.4. Задача о раскрое материала.

Из поступающих на распил 195 бревен длиной 6 метров необходимо изготовить максимальное количество комплектов брусьев. Комплект должен состоять из 2-х брусьев длиной 1,2 м, одного бруса длиной 3 м и 3 бруса длиной 5 м (вариант комплектации условный).

В соответствии с условиями задачи можно сформировать четыре способа распила бревен:

1) 5 бревен длиной по 1.2 метра;

2) 2 бревна длиной по 1.2 метра и одно бревно длиной 3 метра;

3) 2 бревна длиной 3 метра;

4) 1 бревно длиной 5 метров.

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

Способ распила	Число получаемых брусьев длиной в метрах
1,2 метра	3 метра	5 метров
1 - способ	5 шт.	-	-
2 - способ	2 шт.	1 шт.	-
3 - способ	-	2 шт.	-
4 - способ	-	-	1 шт.
Условие комплектности

Теперь можно записать формальную модель рассмотренной задачи:

найти

при ограничениях