Необходимо разработать такой…
Это будет так называемая транспортная задача математического программирования. Одним из наиболее рас-пространенных методов решения подобных задач является метод потенциалов. Прежде всего составляем исходный план распределения машин по объектам. В правые верхние углы кле ток таблицы поместим цифры простоя машин, освободив тем самым нижнюю половину кле ток для цифр, характеризующих количество распределяемых единиц техники. Первоначально заполняется первая строка плана. Очевидно, что распределение целесообразно выполнить по тому направлению, где время простоя минимально, т. е. А, Б4. Здесь время простоя (обозначим его С14) равно 3 ч. Количество машин на этом направлении устанавливается как минимальное из их общего количества, имеющегося на А1 и потребного для Б4, и равняется 7. Таким образом, достигается либо полный расход техники данной базы, либо полное насыщение данного объекта. В рассматриваемом случае полностью насыщается объект Б4 (для памяти подчеркнем). После указанной операции на базе А1 остаются 4 единицы, которые записываем в скобках рядом с цифрой 11. Этот остаток целесообразно направить на объект Б3, поскольку простои по направлению А, будут минимальными из оставшихся. Теперь все ресурсы базы Ах оказываются исчерпанными (А, можно подчеркнуть), а на объекте Б3 остается потребность в 5 единицах (эта цифра записывается рядом с 9 в скобках). Поскольку все ресурсы базы А| израсходованы, переходим ко второй строке плана, где описание операций повторяется и т. д. Таблица 6.3 Первый план (исходный) Базы Объекты Бі 5 Б2 9(3) Бз 9(5) Б4 7 «А; Ai 11 (4) 5 < 7 7 < 8 5 4 3 7 0 А2 11 (6) 2 5 4 6 2 < 5 0 < 9 -3 А3 8(3) 1<6 3 3 1 5 -1 < 2 -4 "Б/ 5 7 5 3 В результате получаем первый, или исходный, план распределения машин по объектам (табл. 6.3). Чтобы определить оптимальность полученного плана, время простоя, характеризующее эффективность решаемой задачи, будем рассматривать в качестве некоторой стоимости: чем время простоя меньше, тем меньше и стоимость работы. Вводим понятие потенциала. Потенциалами являются некоторые числа ид,- и иприписываемые соответственно базам и объектам, сумма которых для кле ток плана, содержащих цифры распределенных машин, равна стоимости результата времени простоя, то есть «А/ + «Б/ = Су (Ху > 0), (6.34) а для тех клеток, где распределения нет, эта сумма будет не более стоимости результата, то есть «А/ + «Б/ - (CijXy < 0). (6.35) План, все клетки которого отвечают условиям (6.34), (6.35), является оптимальным. Чтобы определить оптимальность указанного исходного плана, вначале рассчитаем и внесем в табл. 6.3 значения потенциалов баз и объектов. Примем, что иА/ = 0, тогда МБЗ = С13 — «А; = 5 — 0 = 5; — С\4 — U\J — 3 — 0 — 3; "A3 = С33 — «БЗ = 1 — 5 = —4; «БЗ = С23 — "A3 = —3 (—4) = 7; «А2 = С22 — «Б2 = 4 — 7 = —3; «Б1 = С21 — «А2 = 2 — (—3) =5. Проверим теперь, соблюдается ли условие потенциальности для свободных клеток. Просуммируем для каждой из них соответствующие потенциалы баз и объектов и сравним полученные значения с временем простоя, проставленным в правых верхних углах клеток. Суммы потенциалов для свободных кле ток называются псев-достоимостями и обозначаются Су. Их записывают в левых верхних углах клеток. Из выражений (6.34) и (6.35) следует, что для оптимального варианта плана: Су — Су < 0. Как видно из табл. 6.3, условие (6.34) выполняется для всех свободных клеток. Следовательно, этот план оптимальный. В случае, если условие оптимальности не соблюдено, план подлежит улучшению. Пример 6.3 Допустим, что производственное предприятие располагает четырьмя бригадами рабочих-специалистов определенного профиля: условно Ai, А2, A3, А4. Специалисты из этих бригад распределяются по пяти различным видам работ: условно Бі, Б2, Б3, Б4, Б5. От того, как будут распределены по этим видам рабочие, зависит в первую очередь качество продукции. При составлении конкретного плана распределения рабочих - специалистов целесообразно применять математическое програм-мирование. Прежде всего составляется таблица исходного плана (табл. 6.4), подобная рассмотренной выше. В качестве стоимостей и псевдо-стоимостей в данном случае выступают стоимости бракованной продукции, получаемой при данном распределении рабочих по видам работ. Здесь в трех кле тках — А1Б5, А2Б1 и А4Б5 — псевдостоимости оказываются большими, чем соответствующие стоимости (эти не-равенства подчеркнуты). Таким образом, условие оптимальности не соблюдается и, следовательно, план требует улучшения. Для этого необходимо ввести распределение рабочих в ту из клеток, где имеются наибольшие нарушения условий оптимальности, то есть где разность между псевдостоимостью и сто имостью наибольшая (она подчеркнута двойной чертой в клетке А2Б|). Таблица 6.4 Первый план (исходный) Бригады Виды работ Бі 24 (12) Б2 15 (13,4) Бз 10 Б4 20 Б5 7 «А; Ai 22 (2) 11 < 12 8 2 7 < 10 4 20 10 > 9 0 А2 19 (9) 6 < 3 hi 3 9 - hi 2 10 -1 < 6 5 < 10 -5 А3 29 (12) 3 12 0 < 7 - 1 < 10 -4 < 3 2 7 -8 А4 16 (12) 8 12 - hi 5 4 + hi 4 = 4 1 3 7 > 5 - 3 11 8 7 4 10 Чтобы при заполнении А2Б1 не был нарушен общий баланс распределения, необходимо перераспределение специалистов выполнить так, чтобы сумма ресурсов рабочих по всем горизонталям и вертикалям сохранялась. Достигается это тем, что рабочие перераспределяются лишь в пределах определенного контура, начало и конец которого находится в полученной свободной клетке А2Б (отмечен штриховой линией). Изменение направления контура следует производить в тех клетках, где есть распределение. Причем необходимо стремиться к тому, чтобы поворотные кле тки, лежащие на одной горизонтали и вертикали со свободной клеткой, содержали работы наибольшей стоимости (с наибольшим браком). Это выгодно, так как количество рабочих в указанных кле тках будет уменьшаться на И человек для компенсации нового распределения в клетке А2Б|. Тем самым брак будет уменьшаться. Для соблюдения общего баланса добавляют h рабочих в кле тку А4Б2. В контуре происходит чередование знаков дополнительного распределения И в поворотных клетках: в клетке А2Б| — плюс, в кле тке А2Ба — минус и т. д. Величина дополнительного количества рабочих И должна избираться таким образом, чтобы ни одно из распределений не становилось отрицательным. В данном случае Ai = 9. Таблица 6.5 Второй план (улучшенный) Виды работ Бригады Бі 24 Б2 15 Бз 10 Б4 20 Б5 7 «Аі Ai 22 11 < 12 8 2 10 = 10 4 20 10 > 9 0 А2 19 3 9 + h2 0 < 3 2
