Промышленный лизинг Промышленный лизинг  Методички 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 [ 29 ] 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

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

п т т п

к=\ /=1 /=1 к=\

Вследствие того что выражение в левой части этого равенства неотрицательно (напомним, что все искомые величины должны быть неотрицательными), заключаем, что

/=1 *=i

Заметим, что минимум в левой части этого неравенства ищется из условий второй задачи, а максимум в правой части - из условий первой. Из того, что выражение в правой части полученного неравенства не зависит от yh а выражение в левой его части не зависит от хк, получаем, что

тт/У/ >тахскхк.

/=1 к=1

Иными словами, искомый максимум в первой задаче не должен превосходить искомого минимума во второй.

Последнее неравенство означает, что цена у аптекаря не превосходит цены у бакалейщика.

На самом деле они равны.

Теоретически этот факт устраняет конкуренцию между аптекарем и бакалейщиком, поскольку результат всегда ничейный ([6], с. 376).

Сформулируем сказанное более аккуратно.

ТЕОРЕМА 1. Либо взаимодвойственные задачи линейного программирования одновременно разрешимы и тогда

max min >

либо ни одна из них не имеет решения.

Из этого утверждения вытекает, что если мы нашли max и>, то мы нашли и min z. Здесь, правда, есть одно но: max w в первой задаче мы находим одновременно с оптимальным набором х*, х*, х*п+т,

а про оптимальный набор у*,у*т, у*+1,у *+л во второй задаче нам почти ничего не известно. На самом деле это не так.

Вновь обратившись к равенству (о), заметим, что если выражение в его правой части обращается в нуль, то



В силу неотрицательности х*,хл\ хл+1,хп+т и у*,у*, , у *+я каждое из этих т + п попарных произведений должно быть равным нулю

*i*>C+1 = 0,хУт+п = 0, хл+1>>; = 0, ...,х1+яуя = 0.

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

Сформулируем наше наблюдение в виде утверждения.

ТЕОРЕМА 2. Положительным элементам оптимального набора одной из взаимодвойственных задач соответствуют нулевые элементы оптимального набора другой задачи.

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

Пусть х*, хл, хл+1, хл+Л - оптимальный набор переменных

первой задачи

а у *,у*т, ут+1,ут+п - оптимальный набор переменных второй задачи

bxy[+...+bmym=zm[ri-

Представим соответствие между неизвестными взаимодвойственных задач в виде следующей таблицы:

хя

У т+1

Ут

Ух

Ут

если х* >0 (к= 1, л), то ут+к = 0, если хл+/ >0 (/= 1, л), или, что то же,

апх1+...+аяхя<Ьп (0)

то >>;=о,

и наоборот,

если у] > 0 (/= 1, /я), то хл*+/ =0,



если у*т+к >0 (к = 1, л), или, что то же, аХку\+...+аткУт>ск, (®)

то х* = 0.

Применительно к рассмотренной выше задаче о диете неравенства (©) и (®) означают, что

бакалейщик не продает продукт, цена которого больше цены соответствующего витаминного эквивалента,

аптекарь не берет денег за витамины, которые оказываются в излишке в диете ([6], с. 379).

В заключение этого раздела решим конкретную задачу.

Задача 3. Имеется два вида сырья S{ и S2 в количествах 300 и 400 единиц соответственно. Из этого сырья можно изготовить три вида продукции 7ь Т2 и Ту Затраты сырья на изготовление единицы продукции и цены реализации готовых изделий даны в таблице

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

Обозначая через хь х2 и Хз искомые количества изделий, без особых затруднений приходим к следующей задаче

Зх, +4х2 + х3 < 300, 2х. +6х2 +3х3 <400,

хх >0,х2 >0,х3 >0,

w = 10xj + 20х2 + 7х3 -> max.

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

Обозначим через у{ > 0 и у2 > 0 цены на единицу сырья Si и S2 соответственно. Минимальная продажная цена определяется так: в одной единице готовой продукции Тх содержится 3 единицы сырья S\ по цене Ух и 2 единицы сырья Si по цене у2. Тем самым, общая стоимость сырья, используемого для изготовления единицы продукта Ть равна З + 2у2 и не может быть меньше ее цены - 10,



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 [ 29 ] 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92