Экономико-математические методы (Абчук)

Проверим теперь, соблюдается ли условие потенциальности

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

Суммы потенциалов для свободных клеток называются псев­ достоимостями и обозначаются С. Их записывают в левых верх­ них углах клеток.

Из выражений (3.34) и (3.35) следует, что для оптимального варианта плана: С. - С < 0. Как видно из табл. 3.3, условие (3.34) выполняется для всех свободных клеток. Следовательно, этот план оптимальный.

В случае, если условие оптимальности не соблюдено, план подлежит улучшению.

П р и м е р 3.3

Допустим, что производственное предприятие располагает четырьмя бригадами рабочих-специалистов определенного профи­ ля: условно Ар А2, А3, А4. Специалисты из этих бригад распределя­ ются по пяти различным видам работ: условно Бр Б2, Б3, Б4, Б5. От того, как будут распределены по этим видам рабочие, зависит в первую очередь качество продукции.

При составлении конкретного плана распределения рабочихспециалистов целесообразно применять математическое програм­ мирование.

Прежде всего составляется таблица исходного плана (табл. 3.4), подобная рассмотренной выше. В качестве стоимостей и псевдо­ стоимостей в данном случае выступают стоимости бракованной продукции, получаемой при данном распределении рабочих по видам работ.

Здесь в трех клетках - А,Б5, A2Bj и А4Б5 - псевдостоимости оказываются большими, чем соответствующие стоимости (эти не­ равенства подчеркнуты). Таким образом, условие оптимальности не соблюдается и, следовательно, план требует улучшения. Для это­ го необходимо ввести распределение рабочих в ту из клеток, где имеются наибольшие нарушения условий оптимальности, т.е. где разность между псевдостоимостью и стоимостью наибольшая (она подчеркнута двойной чертой в клетке А2Б,).

Таблица 3.4

Первый план (исходный)

Чтобы при заполнении А2Б, не был нарушен общий баланс распределения, необходимо перераспределение специалистов вы­ полнить так, чтобы сумма ресурсов рабочих по всем горизонталям и вертикалям сохранялась. Достигается это тем, что рабочие пере­ распределяются лишь в пределах определенного контура, начало и конец которого находятся в полученной свободной клетке А2Б, (от­ мечен штриховой линией). Изменение направления контура следу­ ет производить в тех клетках, где есть распределение. Причем не­ обходимо стремиться к тому, чтобы поворотные клетки, лежащие на одной горизонтали и вертикали со свободной клеткой, содержа­ ли работы наибольшей стоимости (с наибольшим браком). Это выгодно, так как количество рабочих в указанных клетках будет уменьшаться на h человек для компенсации нового распределения в клетке А Б . Тем самым брак будет уменьшаться.

Для соблюдения общего баланса добавляют h рабочих в клетку А4Б2. В контуре происходит чередование знаков дополнительного рас­ пределения h в поворотных клетках: в клетке A2Bj - плюс, в клетке А2БА - минус и т.д. Величина дополнительного количества рабочих h должна избираться таким образом, чтобы ни одно из распределений не становилось отрицательным. В данном случае h = 9.

Таблица 3.5

Второй план (улучшенный)

После распределения рабочих в контуре получим второй план, который вследствие более рационального распределения спе­ циалистов будет лучше исходного (табл. 3.4).

Общая стоимость брака по первому плану (у) составляла:

^ 1 = J ] 2 ] C i x i = 8 - 2 + 4.20 + 3-9 + 2-10 + 3-12 +

+ 2-7 + 812 + 5-4 = 309.

После улучшения плана стоимость брака Ау уменьшилась на следующую величину:

Ау = G21h1 - C22h, + C42h, - C4lh, = \ • (C21 - C22 + C42 - C41) = = (3 - 3 + 5 - 8) • 9 = 27.

Общая стоимость брака по второму плану (у2) будет:

у2 = у 1 - А у = 3 0 9 - 2 7 = 282.

При проверке второго плана на оптимальность уста­ навливаем, что условие оптимальности не соблюдено в клетках AjB5 и А4Б3, причем последняя из них имеет наибольшую разность между

псевдостоимостью и стоимостью. Строим контур относительно указанной клетки (см. табл. 3.5). Величина дополнительного коли­ чества рабочих h2 = 3.

После перераспределения рабочих получим третий план (табл. 3.5), который экономичнее второго на величину Ау:

Ay = (C4 3 -C4 1 +C2 | -C2 ,)h2 = (4 - 8 + 3 - 2) - 3= - 9 .

Таблица 3.6

Третий план (оптимальный)

Стоимость брака по третьему плану, таким образом, равна:

у3= у2-Ау = 282-9 = 273.

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

Заметим, что оптимизация плана распределения рабочихспециалистов по видам работ привела к сокращению брака (по его

( 309 -273 ^

стоимости) на 12% | — ^ ^ 100 L И это улучшение качества 309

достигнуто без ввода каких-либо дополнительных ресурсов, исклю­ чительно за счет составления обоснованного плана.

П р и м е р 3.4

Имеется m (i = 1,2,..., m) инвестиционных возможностей (ва­ риантов проектов), которые можно реализовать на n (j =1, 2, ..., п) объектах.

j=i

и означающие, что на каждом объекте может быть реализован лишь один проект.

Кроме того, очевидно, что

xi}>0. (3.39) Необходимо распределить проекты по объектам таким об­ разом, чтобы суммарная эффективность от реализации всех проек­

тов была максимальной. Решение

Оптимизируемая функция, а также ограничивающие ее усло­ вия соответствуют данным, приведенным выше, при постановке

транспортной задачи. Это дает возможность применить метод по­ тенциалов (несколько его видоизменив).

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

Исходя из сказанного, представим условие примера 3.4 в виде табл. 3.8.

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

у, = 0,50 + 0,71 + 0,76 + 0,81 + 0,27 = 3,05.

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

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

Для того чтобы такие действия не вызвали искажения пла­ на, величина s считается сколько угодно малой, и поэтому для пла­ на добавление или исключение ее оказывается несущественным.

Объекты

Проекты

Рис. 3.2

Перепишем исходный план с учетом вышеизложенных изменений (табл. 3.9).

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

Здесь условие оптимальности не соблюдается в тех клетках, где псевдостоимости меньше, чем стоимости (в клетках 1-Й, 1—IV, 1-V, 2-IV, 2-V, 3-V).

Наибольшая разность в клетке 1—IV, в которую нужно вне­ сти дополнительную "перевозку" hr Относительно указанной клет­ ки строим контур. Величина h, = е.

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

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

При этом h2 = е.

Перейдем к третьему плану (табл. 3.11).

Дальнейшее улучшение плана выполняется аналогичным путем. Улучшенные планы сведены в таблицы. Четвертый - в табл. 3.12; пятый-в табл. 3.13; шестой - в табл. 3.14.

Таблица 3.9

Первый план (исходный)

Таблица ЗЛО

Второй план (улучшенный)

Таблица 3.11

Третий план (улучшенный)

Таблица 3.12

Четвертый план (улучшенный)

Таблица 3.13

Пятый план (улучшенный)

Таблица 3.14

Шестой план (оптимальный)