Книги по разным темам
Pages: | 1 | ... | 15 | 16 | 17 | 18 | 19 | ... | 20 | z1p2a - количество продукта, поставляемое заводом пользователю 2 в августе;
z2p1a - количество продукта, поставляемое заводом пользователю 1 в августе;
z2p2a - количество продукта, поставляемое заводом пользователю 2 в августе;
z1p1s - количество продукта, поставляемое заводом пользователю 1 в сентябре;
z1p2s - количество продукта, поставляемое заводом пользователю 2 в сентябре;
z2p1s - количество продукта, поставляемое заводом пользователю 1 в сентябре;
z2p2s - количество продукта, поставляемое заводом пользователю 2 в сентябре;
c1a - количество продукта, поступившего на склад завода 1 в августе;
c2a - количество продукта, поступившего на склад завода 2 в августе;
z1a - количество продукта, произведенного заводом 1 в августе;
z1s - количество продукта, произведенного заводом 1 в сентябре;
z2a - количество продукта, произведенного заводом 2 в августе;
z2s - количество продукта, произведенного заводом 2 в сентябре.
Целевая функция будет иметь вид:
С = z1p1a 10 + z2p1a 12 + z1p1s 10 + z2p1s 12 + + z1p2a 13 + z2p2a 6 + z1p2s 13 + z2p2s 5 + z1a 3 + + z2a 3.2 + z1s 3.6 + z2s 2.9 + c1a 0.5 + c2a 0.6.
Ее значение необходимо минимизировать.
Введем следующие ограничения.
z1p1a + z2p1a = z1p1s + z2p1s = z1p2a + z2p2a = z1p2s + z2p2s = z1a < z1s < z2a < z2s < c1a = z1a - z1p1a - z1p2a c2a = z2a - z2p1a - z2p2a z1s = z1p1s - z1p2s - c1a z2s = z2p1s + z2p2s - c2a С помощью прикладной программы для ЭВМ получаем следующее решение:
Отчет о решении задачи линейной оптимизации Переменная Замечание Значение z1p1a 420.z1p2a 50.z2p1a 0.z2p2a 300.z1p1s 550.z1p2s 0.z2p1s 0.z2p2s 480.c1a 30.c2a 0.z1a 500.z1s 520.z2a 300.z2s 480.Значение целевой функции (оптимальное) 20289.Анализ ограничений и теневые цены:
Огр: z1p1a + z2p1a = 420.0000 = 420.0000 ==> Ц13.Огр: z1p1s + z2p1s = 550.0000 = 550.0000 ==> Ц13.Огр: z1p2a + z2p2a = 350.0000 = 350.0000 ==> Ц16.Огр: z1p2s + z2p2s = 480.0000 = 480.0000 ==> Ц7.Огр: z1a < 500.0000 <= 500.0000 ==> 0.Огр: z1s < 520.0000 <= 600.0000 ==> 0.Огр: z2a < 300.0000 <= 300.0000 ==> 6.Огр: z2s < 480.0000 <= 500.0000 ==> 0.Огр: c1a = z1a - z1p1a - z1p2a 30.000000 = 30.000000 ==> 3.Огр: c2a = z2a - z2p1a - z2p2a 0.00000 = 0.00000 ==> 10.Огр: z1s = z1p1s + z1p2s - c1a 520.0000 = 520.0000 ==> Ц3.Огр: z2s = z2p1s + z2p2s - c2a 480.0000 = 480.0000 ==> Ц2.Итоговая таблица оптимального плана производства и транспортировки выглядит следующим образом.
2.6П Оптимальный плана производства и транспортировки Август Сентябрь Пользователь Пользователь Пользователь Склад 1 2 1 1 420 50 30 30 + 520 2 0 300 0 0 420 350 - 550 Итого 2.2П АЛГОРИТМЫ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ Выше приведено решения задач с помощью методов линейного программирования. Возможно также использовать алгоритм решения транспортной задачи. Применение этого алгоритма требует, чтобы задача удовлетворяла определенным требованиям:
1) должна быть известна стоимость перевозки единицы продукта из каждого пункта производства в пункт назначения;
2) запас продуктов в каждом пункте производства должен быть известен;
3) потребности в продуктах в каждом пункте производства должны быть известны;
4) общее предложение должно быть равно общему спросу, то есть задача должна быть транспортной.
Задача 1 не являлась транспортной как раз по тому, что не удовлетворяла предпосылке 4). Тем не менее, можно ввести фиктивный завод, потребность которого определяется разностью между общим предложением и общим спросом. Потребность фиктивного завода по данным задачи 2.1 составила бы (11 500 - - 8500) = бутылок. Любые продукты, которые подлежат распределению в фиктивный пункт назначения, на деле не вывозятся из пункта производства. В случае, если общее предложение меньше общего спроса, поступают аналогичным образом, то есть в модель вводится фиктивный поставщик, максимальный объем поставок которого равен величине неудовлетворенного спроса. Количество товаров, вывозимых из фиктивного пункта производства, характеризует величину недостающих поставок.
Алгоритм решения транспортной задачи состоит из четырех этапов:
Этап 1. Представление данных в форме стандартной таблицы и поиск любого допустимого распределения перевозок. Допустимым называется такое распределение перевозок, которое позволяет удовлетворить весь спрос в пунктах назначения и вывезти весь запас продуктов из пунктов производства.
Этап 2. Проверка полученного распределения перевозок на оптимальность.
Этап 3. Если полученное распределение перевозок не является оптимальным, то ресурсы перераспределяются, снижая стоимость транспортировки.
Этап 4. Повторная проверка оптимальности полученного распределения перевозок.
Данный итеративный процесс повторяется до тех пор, пока не будет получено оптимальное решение.
2.2.1П ПОИСК НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ ПЕРЕВОЗОК Начальное распределение перевозок может быть получено с помощью любого метода, позволяющего найти допустимое решение задачи. Однако при систематическом решении таких задач можно разработать методы, позволяющие получать более выгодные начальные решения. Остановимся на двух методах нахождения начального распределения перевозок - методе минимальной стоимости и методе Вогеля.
З а д а ч а 2.3. Три торговых склада - P, Q и R - могут поставлять некоторое изделие в количестве 9, 4 и единиц соответственно. Величины спроса трех магазинов розничной торговли, находящихся в пунктах А, В и С, на это изделие равны 3, 5 и 6 единицам соответственно. Какова минимальная стоимость транспортировки изделий от поставщиков к потребителям Единичные издержки транспортировки приведены в таблице.
2.7П Издержки транспортировки, объемы потребностей и предложения Транспортные издержки Общий объем для магазинов, у.е.
Поставщик предложения А В С 10 20 5 Р 2 10 8 Q R 1 20 7 Общий объем спроса 3 5 Решение.
В нашем распоряжении имеется информация об издержках, предложении изделий и потребностей в них, но общее предложение превышает общий спрос. Общее количество изделий, которое могут поставить все склады, равно 21, однако розничным магазинам необходимо только 14 изделий. Следовательно, необходимо ввести фиктивный розничный магазин, потребность которого будет равна 7 изделиям, определяющим избыток предложения. Фактически эти 7 изделий не будут вывезены с торговых складов, поэтому предполагается, что издержки транспортировки для них будут равны нулю.
2.8П Сбалансированная транспортная таблица Транспортные издержки Общий объем для магазинов, у.е.
Поставщик предложения А В С Ф 10 20 5 0 Р 2 10 8 0 Q R 1 20 7 0 Общий объем 3 5 6 спроса Для нахождения начального допустимого распределения перевозок будем использовать метод минимальной стоимости, а затем метод Вогеля. Тем не менее следует иметь ввиду, что на практике требуется применение только одного из методов.
М е т о д 1. Метод минимальной стоимости 1. В клетку с минимальной единичной стоимостью записывают наибольшее возможное количество продукта.
2. Производится корректировка оставшихся объемов предложения и потребностей.
3. Выбирается следующая клетка с наименьшей стоимостью, в которую помещается наибольшее возможное количество продукта, и так далее до тех пор, пока спрос и предложение не станут равными нулю.
4. Если наименьшее значение стоимости соответствует более чем одной клетке таблицы, выбор осуществляется случайным образом.
2.9П НАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ПЕРЕВОЗОК, ПОЛУЧЕННОЕ МЕТОДОМ МИНИМАЛЬНОЙ СТОИМОСТИ Транспортные издержки для магазинов, у.е. Общий объем Поставщик предложения Ф А В С 1 20 5 Р - - 23 71 2 10 8 Q - 45 - - 1 20 7 R 32 16 44 - Общий 3 5 6 объем 0 40 40 спроса Ключ:
Единичная стоимость транспортировки Количество перевозимого продукта В таблице стоимость транспортировки находится в верхнем правом углу каждой клетки внутри прямоугольника. Индексы, соответствующие количеству продукта, характеризуют последовательность распределения перевозок и облегчают понимание процедуры распределения. Прочерки в клетках - отсутствие предложения или спроса, соответствующим этим клеткам.
1 Наименьшая стоимость транспортировки равна нулю. Следовательно, можно выбрать любую из клеток, относящихся к фиктивному заводу. Пусть выбрана клетка (Р, Ф), в соответствии с алгоритмом в ней помещается максимальное количество продукта, равное 7 единицам. Предложение в Р и спрос фиктивного магазина уменьшаются на 7. Затем в клетках, которые уже нельзя использовать в дальнейшем распределении перевозок, ставится прочерк.
2 Клеток с нулевой стоимостью больше нет, поэтому выбирается клетка (R, A), которая соответствует наименьшая стоимость, равная единице. В данной клетке размещается наибольшее количество продукта, равное 3. Затем производится корректировка итоговых значений спроса и предложения, соответствующих данным строке и столбцу, а в остальных клетках этого столбца ставится прочерк.
3 Наименьшая стоимость перевозки равна 5 и соответствует клетке (Р, С). В данной клетке размещается две единицы изделия, оставшиеся на складе Р. Производится корректировка итоговых значений соответствующих строки и столбца, а в остальных клетках строки Р ставится прочерк.
4 Наконец, оставшееся количество продукта распределяется последовательно в клетки (R, С), (Q, В) и (R, В).
Если распределение является допустимым, то объемы предложения на складах и объемы потребностей во всех магазинах должны быть равны нулю. Полученное выше распределение перевозок является допустимым.
Стоимость = (3 1) + (4 10) + (1 20) + (2 5) + (4 7) + (7 0) = 101.
Мы еще не можем сказать, является ли данное распределение перевозок наиболее дешевым, однако получена некоторая реальная стоимость.
М е т о д 2. Метод Вогеля В данном методе используется штрафная стоимость. Штрафная стоимость для каждой строки и столбца - разность между наиболее дешевым маршрутом и следующим за ним с точки зрения критерия минимизации стоимости перевозок.
Суть метода состоит минимизации этих штрафов.
1 Чтобы вычислить значения штрафной стоимости для каждой строки и столбца, необходимо найти клетки с наименьшей стоимостью и ближайшим к ним значением стоимости. Для каждой клетки и столбца наименьшее значение стоимости вычитается из ближайшего к нему значения, найденного по критерию минимизации стоимости. Такая процедура позволяет получить значения штрафов за отсутствие перевозок в клетках с наименьшей стоимостью.
2 Выбирается строка или столбец с наименьшим значением штрафной стоимости, и в клетку с наименьшим значением стоимости перевозки для данной строки и столбца помещается наибольшее возможное количество продукта. Такая процедура позволяет избежать назначения высоких штрафов.
3 Как и в предыдущем методе, производится корректировка итоговых значений по строкам и столбцам таблицы.
4 В строках или столбцах, в которых предложение или спрос приняли нулевые значения, ставится прочерк во всех клетках, в которых отсутствуют перевозки, так как эти клетки нельзя использовать в процессе дальнейшего распределения перевозок.
2.10П Начальное распределение перевозок, полученое методом Вогеля Транспортные издержки для Штрафная Общий магазинов, у.е. стоимость объем Поставщик предлож А В Ф 1 2 ения С 10 20 5 5 5 Р - 1 6 2 2 10 2 - - Q - - - - 20 32 - 53 - R 1 1 ОБЩИЙ 3 5 6 ОБЪЕМ 0 40 0 СПРОСА 1-Й 1 101 2 ШТРАФ 2-Й 92 0 2 ШТРАФ 3-Й - 0 2 ШТРАФ Ключ:
Единичная стоимость транспортировки Количество перевозимого продукта 5 Производится возврат к шагу 1 и перерасчет штрафных стоимостей без учета клеток, в которых указаны перевозки, или клеток, в которых стоит прочерк.
Указанные шаги повторяются до тех пор, пока весь спрос не будет удовлетворен.
Индексы, соответствующие количествам перевозок, отражают порядок выбора штрафных стоимостей и распределения перевозок.
После третьего распределения продукта оставшееся его количество распределяется по клеткам транспортной таблицы однозначно.
Стоимость = 1 20 + 6 5 + 2 0 + 4 10 + 3 1 + 5 0 = 93.
КАК И В ПРЕДЫДУЩЕМ СЛУЧАЕ, ЕЩЕ НЕИЗВЕСТНО, ЯВЛЯЕТСЯ ЛИ ДАННОЕ РЕШЕНИЕ ОПТИМАЛЬНЫМ, ОДНАКО МОЖНО С УВЕРЕННОСТЬЮ УТВЕРЖДАТЬ, ЧТО ПЛАН ПЕРЕВОЗОК, ПОЛУЧЕННЫЙ МЕТОДОМ ВОГЕЛЯ, БОЛЕЕ ДЕШЕВЫЙ ПО СРАВНЕНИЮ С ПЛАНОМ, ПОЛУЧЕННЫМ МЕТОДОМ МИНИМАЛЬНОЙ СТОИМОСТИ, СТОИМОСТЬ КОТОРОГО СОСТАВИЛА 101.
2.2.2П ПРОВЕРКА НА ОПТИМАЛЬНОСТЬ Чтобы осуществить проверку оптимальности, необходимо определить, является ли начальное распределение перевозок базисным, то есть находится ли полученное решение в крайней точке допустимого множества.
Представленное в таблице распределение перевозок является допустимым решением, то есть лежит внутри или на границе допустимого множества. Если распределение перевозок является базисным, каждому ограничению должна соответствовать одна базисная переменная. Задача для m торговых складов и n розничных магазинов (включая фиктивный) содержит (m + n - 1) независимых ограничений. Следовательно, базисное решение должно размещаться в (m + n - 1) клетках транспортной таблицы. Все (m + n - 1) переменные должны занимать независимые позиции. Однако на данной стадии нет необходимости проявлять беспокойство по поводу независимости переменных, поскольку в процессе проверки решения на оптимальность любые нарушения будут выявлены.
Если распределение перевозок включает (m + n - 1) независимых переменных, то к нему непосредственно можно применить методы проверки оптимальности. Если же число переменных меньше указанного количества, то критерий проверки оптимальности необходимо модифицировать так, как это будет показано ниже. Однако если число переменных превышает (m + n - 1), процедура распределения перевозок проведена некорректно. В этом случае должны существовать варианты такого распределения перевозок, которые при меньшей стоимости содержат требуемое число переменных.
Проверим каждое из полученных разными методами распределений перевозок на базисность. В таблице 3 строки и столбца, следовательно, базисное решение должно содержать (3 + 4 - 1) = 6 заполненных клеток. Это верно для обоих методов распределения перевозок. Кроме того, переменные решения, полученные с помощью обоих методов, находятся в различных точках допустимого множества. Следовательно, процедуру проверки можно применять, не прибегая ни к каким модификациям.
Pages: | 1 | ... | 15 | 16 | 17 | 18 | 19 | ... | 20 | Книги по разным темам