Методом северо-западного угла
Определяем элементы матрицы Затем вычисляем x12 = min {ax – x11 b2} при a1>b1, x21 = min { a2, b1–х11 }при а1<b1. Этот процесс продолжается до тех пор, пока на каком-то этапе не исчерпаются ресурсы ат и не удовлетворятся потребности bп. Пример 1. Даны: матрица транспортных издержек
Проверяем условие баланса x11 = min{60, 70} = 60; x21 = min{55, 70-60}= 10; x22 = min {5, 55- 10}= 5; x23 = min {45, 55- 10-5} = 40; x33 = min{40, 45-40} = 5; x34 = min{70, 40-5}= 35; x44=35;
Полученный план невырожден, так как 1.5.3. Построение начального опорного плана Методом минимального элемента
Данный метод позволяет получить опорный план с учетом матрицы стоимости перевозок C=|cij|. План строим таким образом, чтобы перевозки xij выполнялись, по возможности, по маршрутам с минимальной стоимостью. Для этого элементы матрицы С (см. исходные данные предыдущего примера) нумеруем, начиная от минимального в порядке возрастания (показано верхним индексом), а затем в этом же порядке определяем элементы матрицы X:
(1) x11 = min{60, 70} = 60; (2) x23=min{55, 45} = 45; (3) x44=min{35, 70} = 35; (4) х12= 0; (5) х41=0; (6) x21=min{55, 70-60} = 10; (7) х42= 0; (8) х43=0; (9) x34=min{40, 70-35} = 35; (10) х22=0; (11) x32=min {40-35, 5} = 5.
Элементы матрицы Х, соответствующие Строим опорный план
Построенный план – невырожденный, поскольку количество ненулевых элементов
Метод потенциалов
Рассмотрим работу алгоритма на данных, приведенный в примере 1. Допустим, был получен следующий начальный опорный план:
Для удобства вычисления потенциалов
Рис. 1.5.1 По соответствующим маршрутам указываем стоимость перевозки cij единицы груза из i -го пункта в j -й. Принимаем u1 = 0 (можно взять любое число) и, пользуясь соотношением (1.5.8), определяем потенциалы: Рассчитываем элементы оценочной матрицы по соотношению (1.5.7): и т.д. Получаем следующую матрицу: Так как в С1 имеются отрицательные элементы, план Х0 не является оптимальным. Первая итерация. В матрице Хо, начиная с элемента х32, соответствующего в оценочной матрице наибольшему по модулю отрицательному элементу (-7), строим цепочку, в которую входят элементы
Полученный план является вырожденным. Поскольку в дальнейших расчетах оперируем невырожденным планом, один из нулей цепочки заменяем величиной В матрице
Затем ко всем элементам зачеркнутых строк прибавляем
В оценочной матрице С2 нет отрицательных элементов, следовательно, план X1, является оптимальным. Стоимость перевозок будет равна:
Перечислим наиболее часто встречающиеся экономические задачи, которые относятся к транспортным задачам [4, 16, 18]. 1. Отдельные поставки от определенных поставщиков некоторым потребителям должны быть исключены (из-за отсутствия необходимых условий хранения, чрезмерной перегрузки коммуникаций и т.д.). Это ограничение требует, чтобы в матрице перевозок, содержащей оптимальный план, определенные клетки оставались свободными, что достигается искусственным завышением затрат cij на перевозки. При этом производят завышение величины сij, до таких значений, которые будут заведомо больше всех и с которыми их придется сравнивать в процессе решения задачи. 2. На предприятии необходимо определить минимальные суммарные затраты на производство и транспортировку продукции. С подобной задачей сталкиваются при решении вопросов, Связанных с оптимальным размещением производственных проектов. Здесь может оказаться экономически более выгодным доставлять сырье из более отдаленных пунктов, но зато при меньшей его себестоимости. В таких задачах за критерий оптимальности принимают сумму затрат на производство и транспортировку продукции. 3. Ряд транспортных маршрутов, по которым необходимо доставить грузы, имеет ограничения по пропускной способности. если, например, по маршруту AiBi можно провести не более p единиц груза, то В -йстолбец матрицы разбивается на два столбца – 4. Поставки по определенным маршрутам обязательны и должны войти в оптимальный план независимо от того, выгодно это или нет. В этом случае уменьшают запас груза у поставщиков и спрос потребителей и решают задачу относительно тех поставок, которые необязательны. Полученное решение корректируют с учетом обязательных поставок.
5. Экономическая задача не является транспортной, но в математическом отношении подобна транспортной, так как описывается аналогичной моделью, например моделью распределения производства изделий между предприятиями, оптимального закрепления механизмов по определенным видам работы. 6. Необходимо максимизировать целевую функцию задачи транспортного типа. В этой ситуации при составлении опорного плана в первую очередь стараются заполнить клетки с наиболее высокими значениями показателей cij. Выбор клетки, подлежащей заполнению при переходе от одного допустимого плана к другому, должен производиться не по минимальной отрицательной разнице 7. Необходимо в одно время распределить груз различного рода по потребителям. Задачи данного типа называются многопродуктовыми транспортными задачами. В этих задачах поставщики т родов грузов разбиваются на т условных поставщиков, а потребители п родов грузов разбиваются на п условных потребителей. С учетом этой разбивки составляют полную транспортную таблицу. При этом заметим, что некоторые маршруты
Пример 2. Первый сыроваренный завод (A1) производит сыр двух сортов в следующих количествах: 3 т – I сорта и 4 т – II сорта. Второй сыроваренный завод (А2) также производит сыр двух сортов в следующих количествах: 5 т – I сорта и 2 т – II сорта. Сыр с заводов должен быть поставлен в два супермаркета: "РАМСТОР" и "ПЯТЕРОЧКА". В первый (B1) – 2т сыров I сорта и 3 т – II сорта и остальные 2 т сыра любого сорта. Во второй (В2) – 8т сыров, в том числе обязательно 1 т – I сорта и 2 т – II сорта. Стоимость перевозки в дсн. сд. 1 т сыра составляет: из пункта A1 в пункты B1 и В2 – 10 и 15 ден. ед. соответственно; из пункта А2 в пункты В1и В2 – 20 и 10 ден. ед. соответственно. Составить оптимальный план перевозок. Решение. Каждого поставщика (сыроваренные заводы) разбиваем на две составляющие согласно двум видам сыра ( Тем самым исходная таблица транспортной задачи будет следующей.
Пример 3. Имеются три сорта ткани (
Определить оптимальное распределение ткани. Решение. Данную задачу, которая по своему экономическому смыслу не является транспортной, можно привести к таковой. Зная количество и расход ткани на одну куртку, можно определить потребности в ткани каждого сорта: 80∙0,4 = 32 м2, 60∙1,0 = 60 м2, 120∙0,6 = 72 м2, 110∙0,2 = 22 м2. Общие запасы тканей составляют 200 м2, а общие потребности – 186 м2, поэтому необходимо в таблицу ввести фиктивного потребителя В5 с нулевыми затратами. А так как модель составляется относительно ткани, то исходную матрицу себестоимостей С следует преобразовать относительно единицы ткани (каждый столбец матрицы С разделим на количество ткани, приходящейся на одну куртку).
Исходная таблица будет следующей.
Пример 4. Завод "Калибр" переводит свое производство на выпуск определенного вида изделий, которые будут выпускаться в течение года. Величины спроса в течение года распределяются поквартально и составляют 100, 180, 150 и 200 изделий соответственно. В каждом квартале спрос можно удовлетворить за счет: • запасов изделий, произведенных в прошлом квартале и сохраняющихся для реализации в будущем; • производства изделий в течение текущего квартала; • избытка производства изделий в более поздние кварталы в счет невыполненных заказов. Затраты на одно изделие в каждом квартале составляют 30 усл. ед. Изделие, произведенное для более поздней реализации, влечет за собой дополнительные издержки на хранение 10 усл. ед. в квартал. С другой стороны, каждое изделие, выпускаемое в счет невыполненных заказов, облагается штрафом в размере 20 усл. ед. в квартал. Объем производства изделий меняется от квартала к кварталу в зависимости от выпуска других изделий. В рассматриваемые четыре квартала предполагается выпуск 80, 120, 250 и 200 изделий соответственно. Требуется составить план, имеющий минимальную стоимость производства и хранения изделий. Решение. Данную задачу можно сформулировать как транспортную, записав следующую эквивалентность между элементами производственной и транспортной задач.
Для рассматриваемой задачи стоимость "перевозки" изделия из периода i в период j выражается как стоимость производства в i -й период, i=j; стоимость производства в i -й период плюс стоимость задержки от i до j, i <j; стоимость производства в i -й период плюс штраф за нарушение срока, i>j. Таким образом, затраты в период i при реализации продукции в тот же период j (i=j) оцениваются только стоимостью производства. Если производимая в i -й период продукция будет потребляться позже (i < j), то возникают издержки, связанные с хранением. Аналогично, если производство в i -й период не будет выполнено (i>j), то возникают дополнительные расходы в виде штрафа. Например, Исходная транспортная таблица выглядит следующим образом.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|