Методы оптимизации управления для менеджеров - Зайцев М.Г.. Методы оптимизации управления для менеджеров компьютерноориентированный подход
 Скачать 7.64 Mb.
|
|
5.1. Организация оптимального снабжения В районе имеется 2 песчаных карьера, с которых песок вывозится на 5-тонных грузовиках. Предприятия-поставщики S 1 и S 2 разрабатывающие карьеры, могут поставлять соответственно 100 и 200 грузовиков с песком в день. В этом районе имеется 3 завода железобетонных конструкций - потребители песка D 1 D 2 и D 3 , которым требуется соответственно 80, 90 и 130 грузовиков с песком в день. Стоимости перевозки песка одним грузовиком от карьера- поставщика S i к заводу-потребителю D i (в условных единицах) приведены в таблице параметров. Составить план перевозок, минимизирующий затраты. Переменные, целевая функция и ограничения модели Требуемый план перевозок должен определить, какое количество грузовиков Х ij следует направить с карьера S i на завод D j . Поскольку, очевидно, существуют 6 различных маршрутов, то в этой простой задаче имеется 6 переменных, что и отражено в таблице элементов модели. Целевая функция в данной задаче - суммарные транспортные издержки - равна сумме произведений переменных решения Х ij на стоимости перевозки единицы груза c ij приведенные в таблице параметров. В стандартной транспортной задаче считается, что необходимо, безусловно, удовлетворить все требования потребителей (привезти именно то количество грузов, которое они запрашивали) и вывезти от поставщиков все грузы, которые они имеют на складах. При этом, очевидно, предполагается, что спрос и предложение строго сбалансированы. Если обозначить запасы i-го поставщика S i , а заказы j-го потребителя D j , то для данной задачи нетрудно проверить, что S 1 +S 2 =D 1 +D 2 +D 3 В общем случае, если имеется т поставщиков и п потребителей, условие сбалансированности означает, что Если это условие не выполняется, т.е. транспортная задача не сбалансирована, упоминавшиеся выше специальные высокоэффективные алгоритмы ее решения не могут быть применены. Чтобы обеспечить их применение, в формулировку задачи вносят искусственные изменения, восстанавливающие баланс спроса и предложения. Как это делается, мы рассмотрим ниже, в разделе "Осложненные случаи транспортной задачи". Итак, выполнение требования вывезти все, что производят поставщики песка за день, означает, что сумма перевозок Х 11 +Х 12 +Х 13 из первого карьера на 1, 2 и 3-й заводы-потребители должна равняться производительности первого карьера (100 грузовиков с песком), а сумма перевозок Х 21 +Х 22 +Х 23 из второго карьера на 1, 2 и 3-й заводы-потребители - производительности второго карьера (200 грузовиков). Это первые два ограничения на перевозки, приведенные в таблице элементов модели в столбце "Поставщики". Аналогично необходимо потребовать, чтобы сумма перевозок на каждый из трех заводов - потребителей песка с двух карьеров была точно равна ежедневному заказу на песок от данного завода. Эти требования выражаются тремя равенствами в столбце "Потребители". Обратим внимание, что в отличие от рассмотренных ранее примеров ЛП-задач, где ограничения выражались нестрогими неравенствами (типа "меньше или равно" или "больше или равно"), в транспортной задаче ограничения задаются строгими равенствами. В других ЛП-моделях также вполне могут встретиться ограничения в виде равенств (особенно в тех случаях, когда переменные решения представляют собой доли какой-то заданной суммы или компоненты какой-то смеси и т.п.), однако в транспортной задаче это абсолютное правило. Заметим также, что структура ограничений транспортной задачи исключительно проста: все коэффициенты при переменных решения в ограничениях равны единице. Именно эти особенности и позволяют применять упомянутые выше специальные эффективные алгоритмы решения таких задач. Опорный план Подсчитаем количество ограничений-равенств в нашей транспортной задаче. На первый взгляд их пять. Однако если сложить первые два, то получится такое же равенство, как и при сложении последних трех ограничений: В таких случаях математики говорят, что записанные пять ограничений не являются независимыми. Поскольку первые два ограничения в сумме означают то же самое, что и последние три, фактически ограничений, влияющих на значения переменных решения, не пять, а четыре. Поскольку ограничения в этой задаче образуют систему уравнений относительно переменных решения, можно было бы попытаться решить эту систему, чтобы найти значения переменных. Но переменных решения в нашей задаче 6, а независимых уравнений для их решения только 4. Можно произвольно положить значение двух каких-нибудь переменных решения равными 0 (например, X 11 =0 и Х ]2 =0), тогда остальные переменные решения могут быть однозначно определены из системы уравнений, образованной ограничениями. Получившийся план перевозок, разумеется, необязательно будет оптимальным, но он обязательно является допустимым, поскольку удовлетворяет всем ограничениям. Такой план называется опорным. От множества других допустимых планов он отличается тем, что число ненулевых переменных решения (ненулевых перевозок) точно равно количеству независимых ограничений в транспортной задаче или, иначе, сумме числа поставщиков и потребителей минус 1. В нашей задаче число ненулевых перевозок в опорном плане равно 2 (количество поставщиков) + 3 (количество потребителей) -1=4. В общем случае если имеется т поставщиков и п потребителей, то количество ненулевых перевозок в опорном плане будет т + п - 1. Если, например, т = 10, а п = 20, то количество переменных будет 200, а количество ненулевых переменных в опорном плане - только 29. В теории линейного программирования доказывается, что оптимальный план обязательно является опорным. Иными словами, искать оптимальный план перевозок нужно только среди опорных планов. В этом и состоит основное значение опорного плана. Разумеется, опорных планов может быть много. В нашем примере нетрудно пересчитать, что существует 15 различных способов присвоить нули двум переменным из шести (т.е. имеется 15 опорных планов). В случае когда т = 10, п = 20, число различных опорных планов будет выражаться огромным числом 7,18*10 34 . Таким образом, о том, чтобы перебрать все возможные опорные планы и выбрать среди них оптимальный, в общем случае транспортной задачи, разумеется, не может быть и речи. Однако возможность осуществлять поиск только среди опорных планов все равносильно упрощает задачу по сравнению с общей задачей линейного программирования. Опорным называется такой план, в котором количество ненулевых перевозок равно сумме количеств поставщиков и потребителей минус единица. Оптимальный план перевозок следует искать только среди множества опорных планов. Метод "северо - западного угла". Циклы Хотя в настоящем учебном пособии мы не ставили целью рассмотрение технических аспектов оптимизационных алгоритмов, все же, чтобы продемонстрировать роль введенного понятия опорного плана и дать представление об упоминавшихся выше специальных эффективных алгоритмах решения транспортных задач, представляет интерес получить решение нашей "игрушечной" транспортной задачи без помощи компьютера. Для начала необходимо просто написать какой-нибудь опорный план. Это легко сделать с помощью так называемого метода "северо-западного угла". В правом верхнем углу каждой клетки таблицы перевозок укажем стоимость перевозки единицы груза и будем стремиться последовательно удовлетворять требования каждого потребителя и каждого поставщика. Начнем заполнение таблицы перевозок с левого верхнего ("северо-западного") угла. Потребителю D 1 требуется 80 единиц груза. Эти 80 единиц груза могут быть доставлены от первого поставщика S 1 . Поэтому запишем в клетку S 1 D 1 количество перевозок 80. Поставщик S 1 требует, чтобы с его предприятия было вывезено 100 единиц груза, а пока вывезено только 80. Увезем оставшийся груз к потребителю D 2 . Запишем в клетку S 1 D 2 остающиеся у поставщика S 1 20 единиц груза. Займемся теперь потребителем D 2 . Ему требуется 90 единиц груза, а пока доставлено от S 1 только 20. Недостающие 70 единиц доставим от поставщика S 2 . Продолжая заполнять таблицу, позаботимся об удовлетворении поставщика S 2 . От него вывезено 70 единиц груза, в то время как требуется вывезти 200. Увезем оставшийся груз к потребителю S 3 , и, поскольку наша транспортная задача сбалансирована, именно эти оставшиеся у поставщика S 2 130 единиц груза и нужны потребителю D 3 В результате такой методики заполнения таблицы перевозок мы удовлетворили требования всех поставщиков и потребителей (т.е. все ограничения задачи). При этом видно, что из шести клеток таблицы перевозок мы заполнили четыре. Две клетки остались пустыми. Таким образом, мы получили опорный план. Легко видеть, что полученный план можно улучшить (уменьшить суммарные транспортные издержки). Маршрут S 1 D 3 имеет цену перевозки единицы груза меньше, чем S 1 D 2 . Понятно поэтому, что было бы дешевле вывезти 20 единиц груза от поставщика .S 2 не к потребителю D 2 , а к потребителю D 3 . Но в таком случае, чтобы не нарушить выполнение требований потребителей D 2 и D 3 необходимо увеличить количество грузов, перевезенных от поставщика S 2 к потребителю D 2 , за счет уменьшения числа единиц грузов, перевезенных от S 2 к D 3 Тогда таблица перевозок приобретет следующий вид. Полученный нами план также является опорным. Легко видеть, что в результате этого преобразования 20 единиц грузов были как бы перенесены по круговому пути, или, как говорят, по "циклу", S 1 D 2 → S 1 D 3 → S 2 D 3 →S 2 D 2 . При переносе каждой единицы груза из S 1 D 2 в S 1 D 3 выигрыш в цене составляет 3 у.е.. Аналогично при переносе единицы груза из S 2 D 3 в S 2 D 2 происходит выигрыш в 1 у.е.. Итак, при переносе 20 единиц груза по этому циклу выигрыш в издержках составил 4 у.е. * 20 = 80 у.е. Говорят, что найденный нами цикл имеет "отрицательную цену" (- 4 у.е.). Процесс оптимизации плана перевозок, таким образом, состоит в отыскании циклов с отрицательной ценой и переносе наименьшего в этом цикле количества грузов вдоль этого цикла. В процессе такого преобразования план остается опорным и суммарная стоимость перевозок шаг за шагом уменьшается. Процесс следует продолжать до тех пор, пока не останется циклов с отрицательной ценой. Получившийся в результате план, очевидно, будет оптимальным. В нашей "игрушечной" задаче таких циклов, как легко убедиться, нет уже после первого циклического переноса. Таким образом, таблица перевозок (2) представляет собой оптимальный план перевозок для нашей задачи. В теории линейного программирования разработаны простые методы, позволяющие автоматически находить циклы с отрицательной ценой. Мы не будем на них останавливаться. Заметим только, что описанная методика выделения циклов с отрицательной ценой и преобразования одного опорного плана в другой посредством циклических перестановок приводит к очень эффективным алгоритмам решения транспортных задач. Заметим также, что если "Запасы" поставщиков и "Заказы" потребителей выражены целыми числами, то и все перевозки в оптимальном плане, как очевидно из самого метода решения задачи, будут целыми. Напомним, что общие алгоритмы решения ЛП-задач (например, симплекс-метод) отнюдь не гарантируют получения целочисленных решений, даже если во всех ограничениях фигурируют целые числа. Общая формулировка транспортной задачи Прежде чем перейти к решению более или менее значительных транспортных задач на компьютере с помощью MS- Excel, остановимся на описании общей формулировки транспортной задачи, тем более что она полностью соответствует организации данных на листе MS-Excel. Итак, при постановке транспортной задачи необходимо прежде всего задать таблицу транспортных издержек для перевозок единицы груза c ij от i-го поставщика к j-му потребителю. Эта таблица имеет т строк (по числу поставщиков) и п столбцов (по числу потребителей). Таблица перевозок X ij имеет те же размеры (m*n) и содержит переменные решения. Необходимо также задать запасы поставщиков, готовые к вывозу (на рисунке это столбец S i ) и величины заказов потребителей (на рисунке это строка D j ). Требования вывезти запасы каждого i-го поставщика и удовлетворить заказ каждого j-го потребителя означают соответственно, что сумма переменных решения вдоль каждой i-й строки должна быть равна запасу этого поставщика S i , а сумма переменных решения вдоль каждого j-го столбца должна быть равна заказу соответствующего потребителя D j Наконец, чтобы получить целевую функцию (суммарные издержки), необходимо рассмотреть суммы произведений каждой строки таблицы транспортных издержек на соответствующую строку таблицы перевозок и сложить их, суммируя по i от 1 до т. Это и даст двойную сумму, показанную на вкладке 2. Решение транспортной задачи с помощью MS-Excel Для практического решения транспортной задачи с помощью MS-Excel рассмотрим чуть более сложный пример. Пусть имеются 4 поставщика и 5 потребителей. Издержки перевозки единицы груза от i-го поставщика в j-й пункт назначения, запасы поставщиков и заказа потребителей даны в таблице. Оптимизировать план перевозок. D 1 D 2 D 3 D 4 D 5 Запасы S 1 13 7 14 7 5 30 S 2 11 8 12 6 8 48 S 3 6 10 10 8 11 20 S 4 14 8 10 10 15 30 Заказы 18 27 42 26 15 Организуйте данные так, как показано на рис. 22. 1. В ячейках I4-I7 - суммы произведения цены перевозки единицы груза на объем перевозки от i-го поставщика к любому потребителю. В ячейке 18 сумма этих сумм (т.е. двойная сумма) - целевая функция, которую нужно минимизировать. a) В ячейках I11:I14 — ограничения на количества груза, которые нужно увезти от каждого поставщика. b) В ячейках B16:F16 - ограничения на количества груза, которые нужно привезти к каждому потребителю. 2. Вызовите "Поиск решения": a) Целевая ячейка: I8, - Мин b) Изменяя ячейки: B11:F14 c) Ограничения: B11:F14 ≥ 0 (перевозки неотрицательны) 111:114 = 0 (ограничения на количества груза от каждого поставщика) B16:F16 = 0 (ограничения на количества груза каждому потребителю) При такой организации данных все перевозки окажутся целыми числами (если целыми являются числа в колонках "Запасы" и строке "Заказы"). Однако не следует требовать явно, чтобы переменные В11-F14 были целыми! 3. Проверьте, что в полученном решении ровно т + п - 1 ненулевых перевозок. 4. Повторите расчет, максимизируя транспортные издержки, чтобы оценить отличие наилучшего варианта от наихудшего. 5.2. Осложнения транспортной задачи Как уже отмечалось выше, эффективные методы решения транспортной задачи применимы только при условии, что она сбалансированная, т.е. если сумма запасов, которые поставщики хотят вывезти, равна сумме заказов потребителей. На практике нередко встречаются случаи, когда сумма запасов превышает сумму заказов (излишек запасов) или, наоборот, сумма запасов меньше, чем сумма заказов (дефицит запасов). В первом случае часть запасов, очевидно, должна остаться на складах поставщиков, и дополнительный вопрос при этом состоит в том, сколько грузов не вывозить (оставить на складе) у каждого поставщика, чтобы сумма транспортных издержек при выполнении заказов потребителей была бы минимальной. Во втором случае дополнительный вопрос состоит в том, как распределить дефицит между потребителями. Разумеется, в реальности этот случай сложнее для менеджера, отвечающего за доставку заказов потребителям. Решение проблемы будет, по-видимому, определяться ценностью каждого из потребителей для поставщика и исходом переговоров. Однако если предположить, что все потребители одинаково ценны (или, точнее, одинаково безразличны) для поставщика дефицитного груза и проблема состоит только в том, чтобы подешевле развезти весь имеющийся на складах поставщика товар, то этот второй случай с точки зрения оптимизации издержек мало чем отличается от первого. Несбалансированность: излишек запасов В случае излишка запасов, т.е. когда добавим в таблицу транспортных издержек и в таблицу перевозок по одному лишнему столбцу. Это можно трактовать так, как если бы появился еще один, фиктивный, потребитель. Потребуем, чтобы заказ этого "потребителя" в точности равнялся разности между суммой всех запасов и суммой всех заказов а издержки перевозок грузов к нему от любого поставщика были равны нулю. Например, допустим, что в нашей первой задаче о перевозке песка с двух карьеров на 3 завода производительность первого карьера не 100, а 150 грузовиков в день. Тогда задача становится несбалансированной: потребность заводов — 300 грузовиков с песком в день, а карьеры могут добывать 350. В этом случае нужно снизить добычу песка на каждом из карьеров. Но сколько грузовиков нужно ежедневно не загружать на первом карьере и сколько - на втором? В соответствии со сформулированным рецептом добавим 4-й столбец, представляющий фиктивного потребителя с нулевыми ценами перевозок и с заказом, равным 50 (разница между запасами (150 + 200) и заказами от реальных заводов (80 + 90 + 130)). Тогда переменные Х 14 и Х 24 покажут, сколько грузовиков песка нужно оставить (т.е. не отправлять на заводы, не добывать, хотя это и позволяют производственные мощности карьеров) соответственно на первом и на втором карьерах. |