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

ОБЩАЯ ПОСТАВНОКА ЗАДАЧ

Под программированием здесь подразумеваем планирование.

Определение

Задачей линейного программирования будем называть задачу отыскания наибольшего или наименьшего значения линейной функции на некотором множестве.

Задача имеет следующий внешний вид:

Это система линейного ограничения.

где:

– целевая функция или критерий оптимальности

– любой знак

Целевая функция чаще всего имеет вид:

Определение:

Задача линейного программирования называется стандартной, если:

1. на

2. для любых

3. Ограничения имеют вид неравенств (СЭЛП)

Определение:

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

Определение:

Множество называется множеством планов или допустимых решений. Иными словами, если ’ы удовлетворяют решениям задачи, то множество будет планом допустимых решений задачи.

Определение:

План называется оптимальным в задаче на , если для любых .

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

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

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

белков не менее ед.

углеводов – не менее ед.

жиров – не менее ед.

Содержание белков, углеводов и жиров в одной единице продукции каждого вида указано в таблице:

Вид продукции	белки	жиры	углеводы	Стоимость единицы продукции

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

Cоставим задачу.

– это количество единиц той или иной продукции.

Составим ограничения.

Белков в продукции будет , т. к. – это количество продукции , а – это количество белков в одной единице продукции. Тогда:

Определим целевую функцию. По условию задачи она стремится к минимуму:

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

Таким образом, задача имеет следующий вид: