Количество единиц жира, содержащееся в х кг продукта Р и в у кг продукта Q, равно 15х + 4у и по условию диеты не должно превышать 14,

Количество калорий, содержащееся в х кг продукта Р и в у кг продукта Q, равно 150х + 200>> и по условию диеты должно быть не меньше 300,

150х + 200>>> 300.

Стоимость w продуктов, которая равна

w = 150* + 250>>,

в соответствии с высказанными в условии задачи пожеланиями должна быть минимальной. Это записывается так

w = 150x + 250>>-*min.

Тем самым мы получаем систему формул

Обозначив в задаче 2 через х количество обычных, а через у - количество улучшенных наборов, посредством схожих рассуждений приходим к следующей совокупности формул:

А вот как записывается задача линейного программирования в общем

15х + 4>>< 14.

15х + 4>><14,

150х + 200>>>300,

х>0, >>>0,

w = 150x + 250;ymin.

Зх + 2>>>10, 4х + 6>>>20, х + 3>>>7, х > 0, у > 0,

w = 300x + 400;y- min.

случае:

хк>0, & = !,...,л,

скхк * max.

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

Например, неравенство

150х+ 200>>> 300 из первой задачи легко заменяется на равносильное

-150х-200>>< -300,

а требование

w = 150x+ 250>>- min заменой w на w* = -w сводится к требованию

w*-> max.

Стоит, кстати, пояснить термин линейное программирование: линейное означает, что ищется экстремальное значение линейной целевой функции при линейных ограничениях (линейных уравнениях и линейных неравенствах);

вторая составляющая, программирование, в данном словосочетании имеет смысл планирования.

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

2я<Л=*/> / = 1,...,/и,

х,>0, £ = 1,...,л, (*)

w = 2СЛ ~* тах-

Поясним на первом из приведенных выше примеров, как заменить условия-неравенства на условия-равенства. Перепишем неравенства задачи о диете

15х + 4>>< 14, 150х + 200д>> 300

в равносильной форме

-15х-4>> + 14 £ О,

150х + 200>>- 300 >0

и обозначим выражения в левых частях этих неравенств через и и v соответственно,

и = 15х + 4>> + 14, v= 150х+200>>- 300. Это позволяет записать исходные неравенства в требуемом виде

15х + Ау + и = 14, 150x+ 200>>-v= 300, х £ О, у > О, и > О, v > 0.

Таким образом, путем введения двух новых неотрицательных неизвестных величин мы преобразовали оба условия-неравенства в условия-равенства, сохраняя неотрицательность всех величин, подлежащих определению, и целевую функцию.

Подведем итог постановкой основной задачи линейного программирования: найти неотрицательные значения неизвестных хь хъ хп, для которых линейная функция

достигает наибольшего значения

w -> шах

при т условиях-равенствах

аЛхк-Ьп / = 1,...,/п. (тМг)

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

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