2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

1. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Во многих областях практики возникают своеобразные задачи оптимизации решений, для которых характерны следующие черты:

— показатель эффективности W представляет собой линейную функцию от элементов решения ;

— ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.

Такие задачи принято называть задачами линейного программирования.

Приведем несколько примеров задач линейного программирования из разных областей практики.

1. Задача о пищевом рационе.

Имеется четыре вида продуктов питания:

Известна стоимость единицы каждого продукта:

Из этих продуктов необходимо составить пищевой рацион, который должен содержать:

Единица продукта содержит единиц белков, единиц углеводов, единиц жиров и т. д. Содержание элементов в единице каждого продукта задано таблицей (табл. 1.1).

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

Запишем сформулированные словесно условия задачи в виде математических формул. Обозначим

количества продуктов входящих в рацион.

Таблица 1.1

Очевидно, общая стоимость рациона будет

или короче

(1.2)

Запишем математически условия (1.1). В одной единице продукта содержится единиц белка, значит, в единицах — единицах продукта содержится единиц белка и т. д. Общее количество белков, содержащееся в рационе, не должно быть меньше отсюда получаем первое условие-неравенство:

Записывая аналогичные условия для углеводов и жиров, получим, включая (1.3), три условия-неравенства:

Эти условия представляют собой ограничения, накладываемые на решение.

Возникает следующая задача:

Выбрать такие неотрицательные значения переменных удовлетворяющие линейным неравенствам (1.4), при которых линейная функция этих переменных

обращалась бы в минимум.

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