Глава 1. Линейное программирование
Математическое программирование, являющееся одним из направлений исследования операций, изучает задачи поиска экстремума функции нескольких переменных при наличии ограничений, наложенных на эти переменные. Если функция нескольких переменных и все ограничения являются линейными относительно этих переменных, то математическое программирование называется линейным (ЛП). Программированиев данном термине имеет смысл планирования.
Математическое программирование возникло в 30-е годы XX века. Линейное программирование началось с работы (1938 г.) ленинградского математика Л. В. Канторовича, в которой содержались постановка и метод решения задачи о выборе наилучшей производственной программы. В 1975 году Л. В. Канторовича стал лауреатом Нобелевской премии «за вклад в теорию оптимального распределения ресурсов». Независимо линейное программирование начало развиваться и в США. В 1947 году американский учёный Дж. Данциг описал один из основных методов решения задач ЛП, получивший название «симплексный».
Укажем несколько общих ситуаций, в которых линейное программирование применяется часто и эффективно:
· задачи о составлении смеси, цель которых заключается в выборе наиболее экономичной смеси ингредиентов при учете ограничений на физический или химический состав смеси и на наличие необходимых материалов;
· задачи производства, целью которых является подбор наиболее выгодной производственной программы выпуска одного или нескольких видов продукции при использовании некоторого числа ограниченных источников сырья;
· задачи распределения, цель которых состоит в том, чтобы организовать доставку материалов от некоторого числа источников к некоторому числу потребителей так, чтобы оказались минимальными либо расходы по этой доставке, либо время, затрачиваемое на нее, либо некоторая комбинация того и другого. В простейшем виде это задача о перевозках (транспортная задача).
1.1. Формы модели задач линейного программирования
Построение математической модели изучаемого процесса включает в себя следующие этапы:
1) выбор переменных задачи;
2) составление системы ограничений;
3) выбор целевой функции.
Переменными задачи называют величины 
, 
,…, 
, которые полностью характеризуют изучаемый процесс. Их обычно записывают в виде вектора 
.
Система ограничений включает в себя систему уравнений и неравенств, которым удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других экономических или физических условий.
Целевой функцией называют функцию переменных задачи, экстремум которой требуется найти.
В общем случае задача ЛП может быть записана в виде:
, (1.1)
(1.2)
, 
, (1.3)
т.е. требуется найти экстремум целевой функции (1.1) и соответствующие ему значения переменных 
при условии, что переменные удовлетворяют системе ограничений (1.2) и условию неотрицательности (1.3).
Приведем математическую модель задачи использования ресурсов.
Для изготовления нескольких видов продукции 
, 
,…, 
используют 
видов ресурсов 
, 
,…, 
(например, различные материалы, электроэнергию и т.д.). Объём каждого вида ресурсов ограничен и известен: 
. Известно также 
количество каждого 
-го вида ресурса, расходуемого на производство единицы 
-го вида продукции. Кроме того, известна прибыль, получаемая от реализации единицы каждого вида продукции 
. Условие задачи можно представить в виде табл. 1.1.
Таблица 1.1
| Вид ресурсов | Объём ресурсов | 
| |||
| 
| . . . | 
| ||
.
.
.
| 
.
.
.
| 
.
.
.
| 
.
.
.
| . . . . . . . . . . . . . . . . . . | 
.
.
.
|
| Прибыль | 
| 
| . . . | 
|
Пусть 
количество каждого вида продукции, которое необходимо произвести. Для первого ресурса имеет место неравенство-ограничение
.
Аналогичные неравенства будут и для остальных видов ресурсов. Следует учитывать, что все значения 
, 
.
Общая прибыль, получаемая от реализации всей продукции может быть представлена как функция 
, для которой нужно найти максимальное значение. Таким образом, математическая модель задачи использования ресурсов запишется в виде:
,
(1.4)
, 
.
Пример 1.1. Фирма производит две модели А и В сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3 
досок, а для изделия модели В – 4 . Фирма может получить от своих поставщиков до 1700 досок в неделю. Для каждого изделия модели А требуется 12 мин. машинного времени, а для изделия модели В – 30 мин. В неделю можно использовать 160 ч машинного времени. Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В – 4 дол. прибыли?
Составим математическую модель. Пусть 
количество выпущенных за неделю полок модели А, а 
количество выпущенных за неделю полок модели В. Еженедельная прибыль выражается целевой функцией 
. Ограничение, наложенное на объём используемого сырья, выражается неравенством 
, а на количество машинного времени – 
. Задача состоит в том, чтобы найти наилучшие значения 
и 
. Очевидно, наилучшими для данной задачи являются такие значения, которые максимизируют еженедельную прибыль.
Итак, нужно максимизировать функцию 
при следующей системе ограничений:
