Для неравенств типа < в левую часть неравенства вводится неотрицательная остаточная переменная. Например, в модели компании Reddy Mikks (пример 2.1.1) ограничение на количество сырья Ml задается в виде неравенства 6х, + 4х2 < 24. Вводя новую неотрицательную переменную s которая показывает остаток (неспользованное количество) сырья Ml, это ограничение преобразуется в равенство

6x,+4x2 + s1 = 24, s,>0.

Неравенства типа > в задачах ЛП обычно устанавливают нижнюю границу чего-либо. Избыточная переменная определяет превышение значения левой части неравенства над этой границей. Так, в модели диеты (пример 2.2.2) неравенство х, + х2 > 800 показывает, что суточное производство пищевой добавки не должно быть меньше 800 фунтов. Математически это неравенство эквивалентно равенству

х, + х2 - S, = 800, S, > 0.

Положительное значение избыточной переменной S, показывает превышение суточного производства добавки над минимальным значением в 800 фунтов.

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

Правую часть равенства всегда можно сделать неотрицательной, умножив все равенство на -1. Кроме того, заметим, что неравенство типа < также преобразуется в неравенство типа > посредством умножения обеих частей неравенства на -1. Например, неравенство -х, + х2 < -3 эквивалентно равенству

-х, + х2 + s, = -3, s, > 0.

Теперь, умножая обе части этого равенства на -1, получим равенство с неотрицательной правой частью: х, - х2 - s, = 3.

УПРАЖНЕНИЯ 3.1.1

1. В модели компании Reddy Mikks (пример 2.2.1) рассмотрите допустимое решение х, = 3 т и х2 = 1 т. Для этого решения найдите недоиспользование сырья Ml и М2.

2. В модели диеты (пример 2.2.2) определите превышение над минимальным допустимым объемом производства пищевой добавки, на которую расходуется 500 фунтов кукурузной муки и 600 фунтов - соевой.

3. Дано неравенство 10х,-Зх2>-5. Покажите, что в результате преобразования, когда сначала обе части неравенства умножаются на -1, а затем неравенство преобразуется в равенство, получется такое же равенство, что и в результате преобразования, когда сначала исходное неравенство преобразуется в равенство, а затем умножается на -1.

4. Два изделия, Р1 и Р2, можно произвести на двух различных станках Ml и М2. Время изготовления любого изделия на любом станке одинаково. Производительность станка Ml составляет 200 изделий за смену, а производительность станка М2 - 250 изделий. Мастер планирует сбалансировать рабочее время таким образом, чтобы общее количество изделий, произведенных на одном станке, не превышало более чем на 5 единиц общее количество изделий, изготовленных на другом станке. Доход от одного изделия Р1 составляет 10, а от второго - 15 долл. Запишите эту задачу в стандартной форме линейного программирования.

3.1. Стандартная форма задачи ЛП

5. Покажите, как следующую целевую функцию можно записать в стандартной форме задачи ЛП.

Минимизировать z = maxflx, - х2 + Зх3\, \-хх + Зх2 - х3\},

хх, х2, х3>0.

6. Покажите, что т равенств вида

Y,a x,=b,- = 1.2,...,ш,

7 = 1

эквивалентны следующим т + 1 неравенствам.

ai]Xj<b / = 1,2,...,т,

7 = 1

II f III \ III

3.1.2. Свободная переменная

Во всех примерах задач ЛП главы 2 условие неотрицательности переменных является естественным. Но, конечно, возможны ситуации, когда переменные могут принимать любые действительные значения. Такая ситуация показана в следующем примере.

Пример 3.1.1

Ресторан быстрого обслуживания McBurger торгует порционными мясными пирогами и чизбургерами. На порцию мясного пирога идет четверть фунта мяса, а на чизбургер - только 0,2 фунта. В начале рабочего дня в ресторане имеется 200 фунтов мяса, можно еще прикупить мясо в течение дня, но уже с наценкой в 25 центов. Мясо, оставшееся в конце рабочего дня, жертвуется благотворительной организации. Ресторан получает доход 20 центов от одной порции мясного пирога и 15 центов - от одного чизбургера. Как и многие другие, этот ресторан не может продать в день более 900 бутербродов. Какова должна быть доля каждого блюда (т.е. сколько порций мясного пирога и сколько чизбургеров) в ежедневном производстве ресторана, чтобы максимизировать его доход?

Сначала рассмотрим ограничения. Обозначим через х, и х2 соответственно количество порций мясного пирога и чизбургеров, производимых рестораном. Для их производства ресторан может либо ограничиться 200 фунтами мяса, либо прикупить еще. В первом случае получаем ограничение в виде неравенства 0,25х, + 0,2х, < 200, а во втором- 0,25д, + 0,2д:2 > 200. Естественно, выбор одного из этих неравенств будет существенно влиять на возможное оптимальное решение. Так как мы не знаем, какое из них необходимо, логично заменить их одним равенством 0,25 + 0,2х2 + х3 = 200, гдех3 - свободная переменная. Фактически свободная переменная х3 в данной ситуации одновременно играет роли как остаточной, так и избыточной переменной.

Далее построим целевую функцию. Ресторан хочет максимизировать свой доход. Очевидно, что для максимизации дохода желательно как можно больше продавать своей продукции, но для этого необходимы дополнительные закупки мяса. В этом случае переменная х3 должна быть отрицательной, т.е. должна играть роль избыточной переменной.

Для того чтобы раскрыть двойственную природу переменной х3, используем стандартный математический прием, т.е. представим ее в следующем виде.

х3 = х*3 - х3 , где .г, , л-, > 0.

Если л* > 0 и л3 = 0, то переменная .v3 играет роль остаточной. Если, напротив, х} > О и xl = 0, то переменная х3 выступает в роли избыточной. (Теория задач ЛП гласит, что переменные х*3 и .v3~ не могут одновременно принимать положительные значения.) Итак, теперь ограничение можно записать в виде равенства

0,25л-, +0,2х2 + х; - х~ = 200. Целевая функция получает следующее выражение.

Максимизировать z = 0,20 + 0, [5х2 - 0,25 х}

УПРАЖНЕНИЯ 3.1.2

1. В некотором машинном центре производятся два изделия, причем на производство одной единицы первого изделия затрачивается 10 минут рабочего времени, а на единицу второго изделия - 12 минут. Рабочее время машинного центра ограничено 2500 минут в день (некоторые операции центр может выполнять параллельно); возможно превышение этой величины, но каждая дополнительная минута работы машинного центра стоит 50 центов. В рабочий день допустимо производить от 150 до 200 единиц первого изделия, но не более 45 единиц второго.

a) Предполагая, что доход от единицы первого изделия составляет 6,00 долл., а второго - 7,50 долл., постройте модель и найдите оптимальное соотношение между объемами производства изделий, максимизирующее общий доход, а также дополнительное время работы машинного центра.

b) Если стоимость дополнительного времени работы машинного центра увеличится до 1,50 долл., будет ли компания использовать это время?

2. Фирма производит три вида изделий, прибыль от которых составляет соответственно 2, 5 и 3 долл. на единицу изделия. Для производства этих изделий фирма располагает 80 рабочими часами ручного труда и 65 часами машинного времени. Для производства одной единицы изделия каждого из трех видов требуется 2, 1 и 2 часа ручного труда и 1, 1 и 2 часов машинного времени соответственно. При необходимости фирма может увеличить количество рабочих часов ручного труда и количество часов машинного времени, но каждый дополнительный час ручного труда будет стоить 15, а машинного - 10 долл.

Сформулируйте задачу линейного программирования и найдите ее оптимальное решение с помощью программы TORA.

3. В задачах ЛП, где есть несколько свободных переменных, преобразование типа *;=.v*-.v~, х*, Xj>0, удваивает соответствующее число неотрицательных переменных. Но при использовании подстановок х =xj-w, xj,w>0

можно к свободных переменных заменить на ft + 1 неотрицательных. Используя программу TORA, покажите, что эти два метода приводят к одному и тому же решению следующей задачи ЛП.

Максимизировать z = -2х, + Зх2 - 2х3