Глава 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 дол. прибыли?

Составим математическую модель. Пусть количество выпущенных за неделю полок модели А, а количество выпущенных за неделю полок модели В. Еженедельная прибыль выражается целевой функцией . Ограничение, наложенное на объём используемого сырья, выражается неравенством , а на количество машинного времени – . Задача состоит в том, чтобы найти наилучшие значения и . Очевидно, наилучшими для данной задачи являются такие значения, которые максимизируют еженедельную прибыль.

Итак, нужно максимизировать функцию при следующей системе ограничений: