На этом шаге мы рассмотрим понятие дополнительной переменной в задачах линейного программирования.
В ранее рассмотренных примерах мы использовали неравенства типа "меньше или равно" и "больше или равно". В этих примерах также предполагалась неотрицательность всех переменных.
Введем два типа дополнительных неотрицательных переменных (назовем их остаточными и избыточными, которые связаны с неравенствами, типа "≤" и "≥" соответственно. Введем также понятие свободной переменной, которая может принимать как положительные, так и отрицательные значения (и, конечно, значение 0).
Остаточная переменная. Неравенства типа "≤" обычно можно интерпретировать как ограничения на использование некоторых ресурсов (представленных в левой части неравенств переменными модели). В такой интерпретации остаточная переменная показывает количество неиспользованных ресурсов. В примере с компанией "Русские краски" неравенство 6x1 + 4х2 ≤ 24 связано с использованием сырья M1.
Это неравенство эквивалентно равенству 6x1 + 4х2 + s1 = 24, где s1 ≥ 0. Здесь остаточная переменная s1 (= 24 - 6x1 - 4х2) равна неиспользуемому количеству сырья Ml.
Избыточная переменная. Неравенство типа "≥" показывает, что "что-то" должно быть не меньше определенной величины. Избыточная переменная определяет превышение значения левой части неравенства над этой величиной.
Например, в модели "диеты" неравенство x1 + х2 ≥ 800 показывает, что суточное производство пищевой добавки не должно быть меньше 800 кг. Математически это неравенство эквивалентно равенству x1 + х2 – S1 = 800, где S1 > 0. Положительное значение избыточной переменной S1 показывает превышение суточного производства добавки над минимальным значением в 800 кг.
Свободная переменная. В приведенных выше примерах условие неотрицательности переменных является естественным. Но, конечно, возможны ситуации, когда переменные могут принимать любые действительные значения. Такая ситуация показана в следующем примере.
Пример 1. Ресторан быстрого обслуживания торгует порционными мясными пирогами и чизбургерами. На порцию мясного пирога идет четверть кг мяса, а на чизбургер — только 0.2 кг. В начале рабочего дня в ресторане имеется 200 кг мяса, можно еще прикупить мясо в течение дня, но уже с наценкой в 25 руб. Мясо, оставшееся в конце рабочего дня, жертвуется благотворительной организации. Ресторан имеет доход 20 руб. от одной порции мясного пирога и 15 руб. — от одного чизбургера. Как и многие другие, этот ресторан не может продать в день более 900 бутербродов. Какова должна быть доля каждого из бутербродов (т.е. сколько порций мясного пирога и сколько чизбургеров) в ежедневном производстве ресторана, чтобы максимизировать его доход?
Сначала рассмотрим ограничения. Обозначим через х1 и х2 соответственно количество порций мясного пирога и чизбургеров, производимых рестораном. Для их производства ресторан может ограничиться 200 кг мяса или может прикупить еще. В первом случае получаем ограничение в виде неравенства 0.25x1 + 0.2x2 ≤ 200, а во втором — 0.25x1 + 0.2x2 ≥ 200. Естественно, выбор одного из этих неравенств будет существенно влиять на возможное оптимальное решение. Так как мы не знаем, какое из них необходимо, логично заменить их одним равенством 0.25x1 + 0.2x2 + x3 = 200, где x3 — свободная переменная. Фактически свободная переменная x3 в данной ситуации одновременно играет роль как остаточной, так и избыточной переменных.
Далее построим целевую функцию. Ресторан хочет максимизировать свой доход. Очевидно, что для максимизации дохода желательно как можно больше продавать своей продукции, но для этого необходимы дополнительные закупки мяса. В этом случае переменная x3 должна быть отрицательной, т.е. должна играть роль избыточной переменной.
Для того чтобы раскрыть "двойственную" природу переменной x3, используем стандартный математический прием, а именно представим ее в следующем виде x3 = x3+ - x3-, где x3+, x3- ≥ 0.
Если x3+ > 0 и х3- = 0, тогда переменная x3 играет роль остаточной.
Если, напротив, x3+ = 0 и х3- > 0, тогда переменная x3 выступает в роли избыточной.
Итак, теперь ограничение можно записать в виде равенства 0.25х1 + 0.2х2 + x3+ - х3- = 200. Целевая функция получает следующее выражение.
Максимизировать z = 0.20x1 + 0.15х2 - 0.25 х3-
На следующем шаге рассмотрим каноническую форму задачи линейного программирования.
