Линейное программирование

Глава 4. Линейное программирование

4.1. Постановка задачи

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

В общем случае модель задачи лп имеет вид

(4.1)

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

(4.2)

(4.3)

где L – критерий (целевая функция), называемый также линейной формой;

n - количество переменных;

C_i – параметры (коэффициенты) критерия, не все C_i =0;

(4.2) - функциональные условия (ограничения);

–параметры условий (могут быть любыми действительными числами, но одновременно все не могут равняться нулю при i=const). Во многих случаях они имеют смысл удельных величин (расхода или затрат на единицу переменной, содержания в единице переменной и т. п.).

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

На часть или все переменные накладывается условие неотрицательности (4.3).

Задача состоит в определении таких значений переменных, удовлетворяющих условиям (4.2) и (4.3), которые доставляют в зависимости от контекста максимум или минимум линейной форме.

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

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

1. Задача составления рациона или как экономно питаться

При правильном питании человек должен потреблять в день определенное количество питательных веществ и витаминов. Содержание их в продуктах известно. Известна также цена продуктов. Задача состоит в том, чтобы составить самый дешевый набор продуктов (рацион), обеспечивающий заданное качество питания.

Обозначим:

х_i – количествоi-го продукта в рационе,

a_ij – содержание i-го питательного вещества в единице j-го продукта,

b_i – потребность в ингредиенте (норма).

Чтобы не загромождать модель большим числом данных, ограничимся тремя ингредиентами, но для общности возьмем разные варианты задания нормы. Все исходные данные удобно представить в таблице (табл. 4.1).

Таблица 4.1

Ингредиенты	Продукты				Норма
	1	2	3	4	min	max
Жиры	a11	a12	a13	a14		b1
Белки	a21	a22	a23	a24	b2
Витамины	a31	a32	a33	a34	b^`3	b^``3
Цена	C1	C2	C3	C4

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

при условиях:

Построение модели завершено.