Примеры задач линейного программирования

• Задача планирования производства

Пусть некоторое предприятие производит n типов товаров (известных под номерами, обозначаемыми индексом j, ), затрачивая при этом m типов ресурсов (технологий, производственных факторов, т.е. сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т.д.).

- количество i -го ресурса, необходимое для производства единичного количества j -го товара, ;

- запас i -го ресурса на предприятии, ;

- цена единичного количества j -го товара, .

Считаем, что технология производства линейна. Т.е. затраты ресурсов растут прямо пропорционально объему производства. Пусть показывает планируемый объем производства j -го товара. Тогда допустимым является такой набор производимых товаров , при котором суммарные затраты каждого i -го ресурса не превосходят его запаса: .

Кроме этого, имеется следующее естественное ограничение: .

Стоимость товаров Х выражается величиной

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

• Задача о рационе

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

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

Пусть имеется n продуктов питания (хлеб, мясо, молоко, картофель и т.п.), в которых учитывается m полезных веществ (жиры, белки, углеводы, витамины и т.п.) и известны следующие параметры:

- содержание i -го вещества в единичном количестве j -го продукта, ;

- минимальное количество i -го вещества, которое должно потребляться в расчете на сутки (месяц или т.п.), ;

- цена единичного количества j -го продукта, .

План задачи – это количества продуктов каждого вида, обеспечивающие необходимое количество питательных веществ при минимальных затратах на исходные продукты.

Задача о рационе формулируется с.о.:

Задача о рационе ставится так: среди всех рационов питания Х, покрывающих минимальные потребности в полезных веществах, необходимо выбрать наиболее дешевый.

• Задача о раскрое материала

Суть задачи об оптимальном раскрое состоит в разработке таких технологически допустимых планов раскроя, при которых получается необходимый комплект заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму.

Пусть имеется N штук исходного материала, который можно раскроить n способами.

- количество заготовок i -го вида, получаемое при раскрое единицы исходного материала по j -му способу раскроя, ;

- минимальное количество заготовок i -го вида, ;

- величина отхода с единицы исходного материала при раскрое по j -му способу, .

План задачи , где - количество единиц исходного материала, планируемое к раскрою по j -му способу. Тогда суммарное количество отходов по всем способам раскроя (которое следует минимизировать) состоит

- функция цели,

при ограничениях: на число единиц исходного материала ,

на удовлетворение ассортиментного спроса потребителей

и условии неотрицательности .

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

• Транспортная задача

Рассмотрим простейший вариант модели транспортной задачи, когда речь идет о рациональной перевозке некоторого однородного продукта от производителей (или со склада) к потребителям; при этом имеется баланс между суммарным спросом потребителей и возможностями поставщиков по их удовлетворению. Причем потребителям безразлично, из каких пунктов производства (или склада) будет поступать продукция, лишь бы их заявки были полностью удовлетворены. Т.к. от схемы прикрепления потребителей к поставщикам существенно зависит объем транспортной работы возникает задача о наиболее рациональном прикреплении, правильном направлении перевозок грузов, при котором потребности полностью удовлетворяются, вся продукция от поставщиков вывозится, а затраты на транспортировку минимальны.

Пусть некоторый однородный продукт (уголь, кирпич, картофель и т.п.) хранится на m складах и потребляется в n пунктах.

Известны следующие параметры:

- запас однородного продукта на i -том складе, ;

- потребность в продукте в j -ом пункте, ;

- стоимость перевозки единичного количества продукта с i -го склада в j -ый пункт, .

При этом суммарные запасы равны суммарным потребностям: . (*)

- показывают количество продукта, перевозимого с i -го склада в j -ый пункт.

Матрица называется матрицей тарифов, - матрицей перевозок.

Транспортная задача ставится так:

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

на возможности поставщиков - весь продукт из складов (или пунктов производства) должен быть вывезен: ,

на спрос потребителей, который должен быть удовлетворен:

при условии неотрицательности переменных, исключающем обратные перевозки:

,

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

• Задача оптимального размещения

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

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

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

i - вид производимой продукции, ;

j - номер предприятия, производящего продукцию, ;

k - номер потребителя продукции, ;

- мощности j -го предприятия по производству продукции i -го вида;

стоимость производства единицы продукции i -го вида на j -м предприятии;

- затраты на перевозку единицы продукции i -го вида от j -го предприятия k -му потребителю;

- объем поставки продукции i -го вида k -му потребителю согласно договори: обязательствам;

- искомый объем производства продукции i -го вида на j -м предприятии;

- объем поставки j -м предприятием продукции i -го вида k -му потребителю.

С учетом обозначений суммарные производственные и транспортные затраты в математической модели определяются следующим выражением:

.

Ограничения задачи:

по мощностям каждого предприятия ;

по балансу производства и потребления продукции ;

по удовлетворению спроса потребителей ;

по неотрицательности объемов поставок и производства продукции

.

• Задача о банке

Для простоты рассмотрим числовой пример такой задачи. Пусть собственные средства банка в сумме с депозитами составляют 100 млн.долларов. Часть этих средств, но не менее 35 млн.долларов должна быть размещена в кредитах. Кредиты являются неликвидными активами банка, т.к. в случае непредвиденной потребности в наличности обратить кредиты в деньги без существенных потерь невозможно. Другое дело ценные бумаги, особенно государственные. Их можно в любой момент продать, получив некоторую прибыль или, как правило, без большого убытка. Поэтому существует правило, согласно которому коммерческие банки должны покупать в определенной пропорции ликвидные активы – ценные бумаги, чтобы компенсировать неликвидность кредитов. Считаем, что ликвидное ограничение следующее: ценные бумаги должны составлять не менее 30% средств, размещенных в кредитах и ценных бумагах.

Пусть - средства (млн.долларов), размещенные в кредитах, - средства, вложенные в ценные бумаги.

Тогда должны выполняться следующие линейные ограничения:

балансовое ограничение ,

кредитное ограничение ,

ликвидное ограничение ,

условие неотрицательности .

Если - доходность кредитов, а - доходность ценных бумаг, то цель банка состоит в том, чтобы получить максимальную прибыль от кредитов и ценных бумаг: .

Т.к. кредиты менее ликвидны, чем ценные бумаги, то обычно .