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

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) находить какой-нибудь опорный набор неизвестных,

2) заменять его на опорный с большим значением целевой функции (если таковой существует).

Или, чуть более Подробно:

1) выбираем п - т свободных неизвестных,

2) приравниваем их к нулю,

3) вычисляем соответствующие значения главных неизвестных,

4) если хотя бы одно из них отрицательно, то, воспользовавшись одним из специальных приемов, можно за сравнительно малое число шагов получить опорный набор,

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

Наиболее известный из этих специальных приемов - симплекс-метод. В книгах [4] и [5] он обоснован аккуратно и строго.

Количественные данные в линейных задачах нередко задаются посредством таблицы вида

1/1

раскрывая которую мы и приходим к выписанной выше совокупности формул

xk >0, к = 1, л, w = 2С*Х* ~* тах-

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



а.кУ1>ск, к = 1, п, у, >0, / = 1, т,

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

Попробуем, следуя Г. Стренгу [6], сформулировать их в экономических терминах на примере задачи о диете (при цитировании мы немного изменили обозначения), в которой /и различных продуктов потребляются в (неотрицательных) количествах уи ут. При этом п ограничений соответствует п требуемым витаминам. Элемент aik представляет собой количество к-то витамина в /-м продукте, и fc-e неравенство

означает, что диета должна содержать этот витамин в количестве не меньшем, чем ск. Наконец, если bt есть стоимость /-го продукта, то

Ъхух+..ЛЪтут

является стоимостью всей диеты. Минимизация этой стоимости и составляет цель исходной задачи (привлечение покупателя).

В двойственной задаче аптекарь реализует не еду, а витамины в таблетках. Цены на витамины не отрицательны, и их можно варьировать. Основное ограничение состоит здесь в том, что он не может запрашивать за витамины больше, чем стоит настоящая еда. Поскольку /-й продукт питания содержит витамины в количествах aiki цена, назначаемая аптекарем за эквивалент в витаминах (и равная апхх +...+аЛх/), не может превосходить цены bt настоящего продукта. Это и дает ограничение

апхх+...+атхл <Ьп / = 1, т.

С учетом этого ограничения аптекарь может продавать каждый витамин в количестве с получая доход в размере

который он стремится максимизировать ([6], с. 375).

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



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

апхх +...+аХлхл+хм =Ь19

ая1х1+..Латхл+хл+я=Ья,

х1>0,...,х/1>0,хя+1>0,...,хл+/я>0, Вторая задача

w = c1xI +...+спхп -> max.

>0,...,m0,+1>0,...,+;i0, Z = b{yx +...+bmym -min.

Первую и вторую задачи принято называть взаимодвойственными.

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

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

т I п

/ /=1 /-1

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

п l т \ п п

/ *-1 к-1



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