Постановка задачи. Рассмотрим несколько примеров задач линейного программирования (ЗЛП)

 

Рассмотрим несколько примеров задач линейного программирования (ЗЛП).

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

Ферма производит откорм скота с коммерческой целью. Пусть имеются четыре вида продуктов: Р ₁, Р ₂, Р ₃, Р ₄ со стоимостью с ₁, с ₂, с ₃, с ₄ соответственно. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков – не менее b ₁ единиц, углеводов – не менее b ₂ единиц, жиров – не менее b ₃ единиц. Для продуктов Р ₁, Р ₂, Р ₃, Р ₄ содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано таблицей.

Продукт	Элементы
Белки	Углеводы	Жиры
Р 1 Р 2 Р 3 Р 4	a 11 a 21 a 31 a 41	a 12 a 22 a 32 a 42	a 13 a 23 a 33 a 43

 

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

Составим математическую модель этой задачи. Пусть x ₁, x ₂, x ₃, x ₄ – количества продуктов Р ₁, Р ₂, Р ₃, Р ₄ соответственно, входящих в рацион. Целевая функция (стоимость рациона) будет иметь вид:

.

Ограничительные условия по белкам, углеводам и жирам приводят к следующим неравенствам:

(2.1)

Таким образом, задача сводится к следующей: найти такие неотрицательные значения переменных x ₁, x ₂, x ₃, x ₄, чтобы они удовлетворяли неравенствам (2.1) и обращали в минимум целевую функцию:

.

Задача об использовании сырья (задача планирования производства).

Из сырья двух видов 1 и 2, запасы которого ограничены и составляют b ₁ и b ₂ единиц соответственно, изготавливается продукция трех видов. Затраты сырья на производство продукции задаются следующей таблицей.

 

Вид сырья	Затраты сырья на 1 ед. продукции вида
	a 11 a2 1	a 12 a 22	a 13 a 23

 

Прибыль от производства единицы продукции j -го вида составляет c_j рублей
(j = 1, 2, 3). Требуется найти такой план выпуска продукции, при котором сырье не будет перерасходовано, а суммарная прибыль окажется максимальной.

Обозначим x ₁, x ₂, x ₃ соответственно количество производимой продукции 1-го, 2-го и
3-го видов. Тогда математическая модель задачи имеет вид:

 

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

Ткацкая фабрика располагает двумя видами станков: N ₁ станков типа 1 и N ₂ станков типа 2. Станки могут производить три вида тканей: Т ₁, Т ₂, Т ₃, но с разной производительностью. Станок типа i производит в месяц a_ij метров ткани вида T_j. Каждый метр ткани вида T_j приносит прибыль с _j (j = 1, 2, 3). Согласно плану, фабрика должна производить в месяц не менее b_j метров ткани T_{j .} Кроме того, все станки должны быть загружены. Требуется так распределить загрузку станков, чтобы суммарная месячная прибыль была максимальной.

Пусть x_ij – количество станков типа i (i = 1, 2), занятых производством ткани
T_j (j = 1, 2, 3). Тогда должны выполняться следующие ограничения:

Целевой функцией, очевидно, является получаемая прибыль, т. е.

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

Общая задача линейного программирования состоит в нахождении экстремума (максимума или минимума) линейной целевой функции

 

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

(2.2)

 

где a_ij, b_i, c_j (, ) – заданные постоянные величины. Среди ограничений могут одновременно встречаться знаки ≤, =, ≥.

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

Общая ЗЛП может быть приведена к единому стандартному виду, в котором целевая функция должна быть максимизирована, а все ограничения должны быть записаны в виде равенств с неотрицательными переменными:

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

,

, ,

где , .

Эта стандартная форма называется основной задачей линейного программирования (ОЗЛП). Запишем ее в матричном виде

 

 

при ограничениях Ax = b, x ≥ 0.

Здесь

, , , ,

 

^T означает транспонирование, т. е. с^T – вектор-строка, . A, b, c предполагаются известными, причем b ≥ 0.

Привести общую ЗЛП к основной очень просто, используя следующие очевидные правила.

1. Минимизация целевой функции f равносильна максимизации функции g = –f.

2. Ограничение в виде неравенства равносильно уравнению при условии, что дополнительная переменная . Аналогично,

3. Если на некоторую переменную x_j не накладывается условие неотрицательности, то делают замену переменной , , .