Постановка задачи, основные определения.Закрытая и открытая транспортная задача.Метод северо-западного угла .Метод минимального тарифа .Метод потенциалов

1 Тема 3: ТРАНСПОРТНАЯ ЗАДАЧА 2 План темы 3 «Транспортная задача»: 3.1. Постановка задачи, основные определения 3.2. Закрытая и открытая транспортная задача 3.3. Метод северо-западного угла 3.4. Метод минимального тарифа 3.5. Метод потенциалов 3.1. Постановка задачи, основные определения 3 Цель транспортной задачи - разработка наиболее рациональных путей и способов транспортировки товаров, устранение чрезмерно дальних, встречных и повторных перевозок. 3.1. Постановка задачи, основные определения 4 Исторические этапы исследований транспортной задачи I этап. Задача национального плана перевозок, позволяющего минимизировать суммарный километраж в железнодорожных перевозках при наличии не более двух поставщиков Толстой А. Н. Методы устранения нерациональных перевозок при планировании. Социалистический транспорт, 1939, № 9. II этап. Одну из разновидностей транспортной задачи в 1941 г. Поставил американец Хичкок. Детально разобрал Тьяллинг Чарльз Купманс, который работал членом Объединенного комитета перевозок во время Второй мировой войны. III этап. Первый общий, законченный метод решения транспортной задачи («метод потенциалов») разработан Леонидом Канторовичем. Канторович Л. В., Гавурин М. К., Применение математических методов в вопросах анализа грузопотоков, Сб. ст. Проблемы повышения эффективности работы транспорта, АН СССР, 1949 3.1. Постановка задачи, основные определения 5 На практике существуют 3 основные постановки транспортной задачи: 1. Необходимо найти оптимальную структуру транспортных средств, обеспечивающую минимизацию издержек на транспортировку. эксплуатационные и экономические показатели зависят от состава транспорта 3.1. Постановка задачи, основные определения 6 На практике существуют 3 основные постановки транспортной задачи: 2. Необходимо установить такое распределение грузов между имеющимися в хозяйстве видами транспорта, при котором затраты на перевозки всего объёма грузов были бы минимальными эффективность использования различного транспорта на одной и той же работе не всегда одинакова 3.1. Постановка задачи, основные определения 7 На практике существуют 3 основные постановки транспортной задачи: 3. Задача прикрепления потребителей к поставщикам экономичный план перевозок однородного груза из пункта производства в пункты потребления 3.1. Постановка задачи, основные определения 8 минимум денежноматериальных затрат на перевозки 1. минимум приведенн ых затрат 4. Критерии оптимизации транспортной задачи 2. 3. минимум объёма транспортных работ минимум затрат времени на перевозки 3.1. Постановка задачи, основные определения Однородный продукт, сосредоточенный в m пунктах отправления в количествах а1, a2, … am единиц соответственно, необходимо доставить в каждый из n пунктов назначения в количествах b1 , b2 , … bn единиц соответственно. Стоимость (расстояние) перевозки единицы продукта из i-го пункта отправления в j-й пункт назначения равна cij (стоимость доставки) и известна для каждого маршрута. 9 Содержательная постановка задачи Пусть хij – количество продукта, перевозимого из i-го пункта отправления в j-й пункт назначения. Задача заключается в определении таких величин хij для всех маршрутов, при которых суммарная стоимость или расстояние перевозок были бы минимальными. 3.1. Постановка задачи, основные определения 10 Обозначения: m – количество пунктов отправления (поставщиков); i – номер поставщика; n – количество пунктов назначения (потребителей); j – номер потребителя; ai – объем однородного груза i-го поставщика (запасы); bi – объем однородного груза, требуемого j-ому потребителю (спрос); cij – стоимость доставки единицы груза i-го поставщика jому потребителю; xij – количество груза, доставляемое от i-го поставщика к jму потребителю; С – общие затраты на перевозки. 3.1. Постановка задачи, основные определения 11 потребители поставщики Потреб. Поставщ. 1 1 c11 x11 … i … xi1 … … … … c1j x1j … … n xij … … … cmj xmj … Запас c1n a1 x1n … cij … cm1 xm1 … j … ci1 … m … … … cin ai xin … … cmn am xmn m Спрос b1 … bj … bn a i 1 стоимость доставки единицы груза от i-го поставщика к j-ому потребителю n b j 1 3.1. Постановка задачи, основные определения 12 Стоимость перевозок можно выразить так C = c11x11 + … + cijxij + … + cmnxmn → min или более компактно m n C c ij x ij min i 1 j 1 это целевая функция, которая позволяет определить численное значение критерия оптимальности на всех этапах расчетов и в оптимальном плане 3.1. Постановка задачи, основные определения 13 Необходимо найти минимальное значение целевой функции при следующих возможных условиях: 1 условие. Вывоз всего груза от каждого поставщика: x 11 ... x ij ... x 1n ... ... ... ... ... x ij ... x in ... ... ... ... ... ... x m1 ... x mj ... x mn am ... x i1 a1 ... ai или n x ij j 1 a i где i = 1 … m 3.1. Постановка задачи, основные определения 14 Необходимо найти минимальное значение целевой функции при следующих возможных условиях: 2 условие. Удовлетворение спроса каждого потребителя: x 11 ... x 1j ... x 1n ... x i1 ... x m1 ... ... ... ... ... x ij ... x mj ... ... ... ... ... x 1n ... x mn b1 ... bj ... bn или m x ij i 1 b j где j = 1 … m 3.1. Постановка задачи, основные определения 15 Необходимо найти минимальное значение целевой функции при следующих возможных условиях: 3 условие. Равенство запаса и спроса: a1 ... ai ... am b1 ... bj ... bn или m n ai i 1 b j j 1 Равенство запаса и спроса есть необходимое и достаточное условие совместимости и, следовательно, разрешимости транспортной задачи. 16 3.2. Закрытая и открытая транспортная задача Закрытая модель транспортной задачи Открытая модель транспортной задачи Спрос равен запасу m n m ai i 1 b j Спрос не равен запасу 1 n ai j i 1 b j 1 j 17 3.2. Закрытая и открытая транспортная задача Модель закрытой транспортной задачи m n C При ограничениях: c ij x ij min i 1 j 1 n i x ij ai , i x ij bj, j 1, m 1 m i 1 x ij 1, n 18 3.2. Закрытая и открытая транспортная задача Открытая модель транспортной задачи 1. Запас превышает спрос 2. Спрос превышает запас m n ai i bj 1 j m 1 n ai i 1 bj j 1 19 3.2. Закрытая и открытая транспортная задача 1. Запас превышает спрос m n C При ограничениях: если n i x ij ai x ij b 1 1 x ij min i 1 j 1 m n ai i 1 bj j 1 Не требуется весь имеющийся груз вывозить от поставщика, после удовлетворения спроса часть его может остаться не вывезенной m i c ij x ij j Потребности (спрос) каждого потребителя необходимо удовлетворить полностью 20 3.2. Закрытая и открытая транспортная задача 1. Запас превышает спрос Решение m n ai i 1 bj bn 1 j 1 cn 1 Фиктивный потребитель При введении фиктивного потребителя открытая модель преобразуется в закрытую 21 3.2. Закрытая и открытая транспортная задача 2. Спрос превышает запас m n C При ограничениях: если c ij x ij min i 1 j 1 m n ai i bj 1 j n i x ij ai , i x ij bj, j 1, m 1 m i 1 x ij 1, n 1 22 3.2. Закрытая и открытая транспортная задача 2. Спрос превышает запас Решение n m bj j 1 ai am 1 i 1 Фиктивный поставщик 23 3.3. Метод северо-западного угла «Метод северо-западного угла» на примере: Пример: С 3-х баз требуется доставить в магазины однородный товар. Пусть на базе А1 имеется 50 единиц груза, на базе А2 – 40 единиц, на базе А3 – 20 единиц. Указанный товар нужно отгрузить 4-м потребителям: В1, В2, В3, В4, потребности которых составляют соответственно 35, 25, 30, 25 единиц товара. Стоимость перевозки от базы до потребителей представлена в таблице: В1 В2 В3 В4 А1 3 2 4 6 А2 2 3 1 2 А3 3 2 7 4 Требуется составить такой план перевозок, который обеспечит минимальные транспортные расходы. 24 3.3. Метод северо-западного угла Решение: 1 этап. Составление распределительной таблицы В1 В2 В3 В4 Наличие товара А1 3 2 4 6 50 А2 2 3 1 2 40 А3 3 2 7 4 20 Потребность в товаре 30 25 30 25 110 25 3.3. Метод северо-западного угла Решение: 2 этап. Составление модели Целевая функция (стоимость всей перевозки): C 3 x11 2 x12 4 x13 6 x14 2 x 21 3 x 22 x 23 2 x 24 Проверяем задачу на разрешимость: 3 7 x 33 4 x 34 min ai bj j 1 4 ai 50 40 i 1 20 110 , bj 30 25 30 25 110 j 1 Ограничения по поставкам x11 + x12 + x13 + x14 = 50 x21 + x22 + x23 + x 24 = 40 x31 + x32 + x33 + x34 = 20 x ij 2 x 32 4 i 1 3 3 x 31 0, i 1,3, j 1, 4 Ограничения по потребителям x11 + x21 + x31 = 30 x12 + x22 + x32 = 25 x13 + x23 + x33 = 30 x14+ x24 + x34 = 25 3.3. Метод северо-западного угла 26 Условимся: 1. Построение опорных решений системы, а также преобразования этих решений будут производиться в таблицах. 2. Если базисное неизвестное xij = a, то это число записывается в соответствующей клетке (i, j), и эта клетка называется загруженной, если же переменная не базисная, то xij = 0 и соответствующая клетка остается свободной 27 3.3. Метод северо-западного угла 3 этап. Составление плана Метод северо-западного угла заключается в том, что заполнение таблицы начинают с левого верхнего угла, двигаясь далее по строке вправо или по столбцу вниз. В1 min (50, 30) = 30 А1 30 А2 А3 Потреб ность в товаре В2 3 В3 min (25, 20) = 20 Наличие товара В4 2 4 6 2 3 1 2 3 2 7 4 30 30-30 = 0 20 25 25 - 20 = 5 30 25 50-30 = 20 50 40 20 110 28 3.3. Метод северо-западного угла Метод северо-западного угла заключается в том, что заполнение таблицы начинают с левого верхнего угла, двигаясь далее по строке вправо или по столбцу вниз. В1 А1 А2 В4 4 6 min2 (5, 40) = 5 3 1 2 7 4 30 3 В3 2 20 5 3 А3 Потреб ность в товаре В2 Наличие товара 30 30-30 = 0 2 25 25 - 20 = 5 30 25 50 40 20 110 29 3.3. Метод северо-западного угла Метод северо-западного угла заключается в том, что заполнение таблицы начинают с левого верхнего угла, двигаясь далее по строке вправо или по столбцу вниз. В1 А1 А2 30 3 В3 2 20 min2 (5, 40) = 5 3 30-30 = 0 6 min (30, 35) = 30 1 2 7 4 30 3 30 В4 4 5 А3 Потреб ность в товаре В2 Наличие товара 2 25 5-5=0 30 25 50 40-5 = 35 40 20 110 30 3.3. Метод северо-западного угла Метод северо-западного угла заключается в том, что заполнение таблицы начинают с левого верхнего угла, двигаясь далее по строке вправо или по столбцу вниз. В1 А1 30 3 В3 2 20 2 А2 3 5 30 30-30 = 0 В4 4 1 2 25 5-5=0 6 min (25, 5) = 5 30 3 А3 Потреб ность в товаре В2 Наличие товара 2 5 7 30 30 - 30 = 0 4 25 50 40-35 = 5 40 20 110 31 3.3. Метод северо-западного угла Метод северо-западного угла заключается в том, что заполнение таблицы начинают с левого верхнего угла, двигаясь далее по строке вправо или по столбцу вниз. В1 А1 30 В2 3 20 2 А2 В3 А3 Потреб ность в товаре 30 30-30 = 0 В4 2 4 6 3 1 2 5 30 3 2 25 5-5=0 Наличие товара 5 min (25, 7 20) = 20 20 30 35 - 35 = 0 4 25 25 - 25 = 0 50 40 20 110 32 3.3. Метод северо-западного угла Исчерпаны все запасы и удовлетворены все потребности В1 А1 3 30 В3 2 4 6 3 1 2 5 30 3 А3 В4 20 2 А2 Потребн ость в товаре В2 2 5 7 4 20 30 Наличие товара 25 30 25 50 40 20 110 33 3.3. Метод северо-западного угла Условия разрешимости задачи: 1 условие – число загруженных клеток должно быть равно (m+n-1) 2 условие загруженные клетки не должны образовывать замкнутого цикла 34 3.3. Метод северо-западного угла 4 этап. Подсчет стоимости перевозки В1 А1 3 30 30 3 запас В4 2 4 6 3 1 2 5 30 3 А3 C В3 20 2 А2 спрос В2 2 5 7 4 20 30 25 20 2 5 3 30 25 30 1 5 2 50 40 20 110 20 4 265 Ответ: Общие затраты на доставку всей продукции, для начального решения, составляют 265 ден. ед. 3.4. Метод минимального тарифа 35 Метод минимального тарифа учитывает величины затрат на грузоперевозки, позволяет найти опорный план транспортной задачи, при котором общая стоимость перевозок груза меньше, чем стоимость перевозок при плане северо-западного угла 3.4. Метод минимального тарифа 36 Этапы метода минимального тарифа Этап 1 Выбирается клетка, имеющая минимальную стоимость перевозок (минимальный тариф). Если таких клеток более одной, то выбирается первая по порядку. В1 В2 В3 В4 А1 3 2 4 6 2 А2 2 3 5 2 4 А3 3 2 7 4 В1 В2 В3 В4 А1 3 2 4 6 А2 2 3 1 А3 3 2 7 3.4. Метод минимального тарифа 37 Этап 2 В клетку с наименьшим тарифом помещается наименьшее из чисел ai или bj В1 3 А1 В3 2 В4 запасы 4 6 1 2 7 4 min (30, 40) = 30 А2 А3 спрос В2 30 2 3 3 2 25 30 30 25 50 40 20 110 3.4. Метод минимального тарифа 38 Этап 3 Затем из рассмотрения исключается строка, соответствующая поставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. В1 3 А1 В3 2 В4 запасы 4 6 1 2 7 4 2 А2 3 30 3 А3 спрос В2 2 - 30 25 30 25 50 40 20 110 3.4. Метод минимального тарифа 39 Этап 4 Из оставшихся клеток таблицы снова выбирается клетка с наименьшим тарифом, и процесс распределения запасов продолжается до тех пор, пока все они не будут распределены, а спрос удовлетворен. minВ1 (25, 50) = В225 3 А1 2 А2 2 В4 запасы 4 6 1 2 7 4 3 30 3 А3 спрос 25 В3 2 - 30 25 30 25 50 40 40-30 = 10 20 110 3.4. Метод минимального тарифа 40 Этап 4 Из оставшихся клеток таблицы снова выбирается клетка с наименьшим тарифом, и процесс распределения запасов продолжается до тех пор, пока все они не будут распределены, а спрос удовлетворен. В1 3 А1 10 2 2 - запасы 4 6 1 2 7 4 30 2 - 30 В4 3 3 А3 спрос В3 25 min (30, 10) = 25 А2 В2 25 30 25 50-25 = 25 50 40 20 110 40-30 = 10 3.4. Метод минимального тарифа 41 Этап 4 Из оставшихся клеток таблицы снова выбирается клетка с наименьшим тарифом, и процесс распределения запасов продолжается до тех пор, пока все они не будут распределены, а спрос удовлетворен. min (20, 25) = 20 В1 А1 А2 20 спрос 3 25 10 В4 - 4 6 1 2 30 2 - - 7 4 25 запасы 3 3 30 В3 2 2 А3 30-10 = 20 В2 30 25 50-25 = 25 50 40 40-10-30 =0 20 110 3.4. Метод минимального тарифа 42 Этап 4 Из оставшихся клеток таблицы снова выбирается клетка с наименьшим тарифом, и процесс распределения запасов продолжается до тех пор, пока все они не будут распределены, а спрос удовлетворен. В1 А1 А2 А3 спрос В2 3 20 2 25 10 3 - 3 запасы 4 6 1 2 30 min (20, 25) = 20 2 30 В4 - 2 - В3 7 25 30 - 20 4 50-45 = 5 50 40 20 =5 25 25-20110 3.4. Метод минимального тарифа 43 Этап 4 Из оставшихся клеток таблицы снова выбирается клетка с наименьшим тарифом, и процесс распределения запасов продолжается до тех пор, пока все они не будут распределены, а спрос удовлетворен. min (5, 5) = 5 В1 А1 А2 А3 спрос В2 3 20 2 25 2 10 - - 2 5 2 - 4 20 30 запасы 6 7 - 25 В4 1 30 30 4 3 3 - В3 50-45 = 5 50 40 20 =5 25 25-20110 3.4. Метод минимального тарифа 44 Получается оптимальный план грузоперевозок по минимальному тарифу В1 А1 А2 А3 спрос В2 3 20 2 25 2 10 - - 6 1 2 2 - 7 - 25 запасы 5 30 30 В4 4 3 3 - В3 4 20 30 25 50 40 20 110 3.4. Метод минимального тарифа 45 Этап 5 В завершении проверяется число загруженных клеток (m + n – 1). Если число загруженных клеток будет меньше, то следует загрузить нулем клетку с наименьшим тарифом, но такую, чтобы она не образовывала замкнутого цикла. 3.4. Метод минимального тарифа 46 Ответ: Оптимальный опорный план грузоперевозок: В1 А1 А2 А3 спрос В2 3 20 2 25 2 10 - - 6 1 2 - 2 7 - 25 запасы 5 30 30 В4 4 3 3 - В3 4 20 30 25 50 40 20 110 Минимальная стоимость грузоперевозок: C 20 3 25 2 5 6 10 2 30 1 20 4 270 3.5. Метод потенциалов 47 Метод потенциалов процесс последовательного улучшения исходного плана грузоперевозок до оптимального Автор метода: Л. В. Канторович 1949 год 3.5. Метод потенциалов 48 Теорема: Если для некоторого плана транспортной задачи можно набрать систему из m+n чисел ui, называемых потенциалами поставщика и vj, называемыми потенциалами потребителя, удовлетворяющим условиям vj - ui = cij, если xij > 0 vj - ui ≤ cij, если xij = 0, то план оптимальный. 3.5. Метод потенциалов 49 Экономический смысл выражения vj - ui = cij, если xij > 0 Для поставщиков и потребителей, между которыми запланированы перевозки, разность потенциалов совпадает с затратами на транспортировку единицы груза. 3.5. Метод потенциалов 50 Экономический смысл выражения vj - ui ≤ cij, если xij = 0 Для всех остальных пар поставщиков и покупателей, между которыми перевозки не запланированы, разности потенциалов не превосходят затраты по транспортировке. 3.5. Метод потенциалов Если план перевозок оптимален, то можно присвоить грузам в пунктах отправления и пунктах назначения потенциалы при которых перевозка из любого пункта отправления в любой пункт назначения не могла дать «прибыль», и чтобы в то же время перевозки, внесенные в план, являлись безубыточными 51 Экономическ ий смысл потенциалов 3.5. Метод потенциалов 52 1. Набор – произвольная совокупность клеток в матрице перевозок. 2. Цепь – последовательный набор клеток, в котором каждые две соседние клетки расположены в одном ряду (строке или столбце). 3. Цикл – замкнутая цепь, последняя клетка которой расположена в одном ряду с первой. 3.5. Метод потенциалов 53 1 шаг. После того как найден исходный опорный план перевозок, каждому поставщику ai ставится в соответствие потенциал ui, а каждому потребителю bj ставится в соответствие потенциал vj Числа ui и vj выбираются так, чтобы в любой загруженной клетке сумма потенциалов равнялась стоимости перевозки в этой клетке: v +u =c j i ij 3.5. Метод потенциалов 54 В1 А1 А2 А3 спрос В2 3 В3 2 4 U1+V1=3 U1+V2=2 2 3 U2+V2=2 - 1 2 30 U2+V3=1 3 - В4 25 6 U1+V4=6 2 - 7 - запасы 4 U3+V4=4 30 25 50 40 20 110 3.5. Метод потенциалов 55 Предполагается, что U1 = 0, тогда U1 = 0 U2 = 0 U3 = -2 V1 = 3 V2 = 2 V3 = 2 V4 = 6 3.5. Метод потенциалов 56 2 шаг. Для оценки плана необходимо просмотреть свободные клетки, для которых определяются косвенные тарифы c’ij = ui + vj В1 А1 А2 А3 спрос В2 3 20 2 25 2 10 1 2 2 - 7 - 25 6 5 30 30 - - запас ы В4 4 3 3 - В3 30 4 20 25 50 40 20 110 C’13 = U1+V3 = 0+1=1 C’22 = U2+V2 = 0+2=2 C’24 = U2+V4=0+6=6 C’31 = U3+V1=-2+3=1 C’32 =U3+V2=-2+2=0 C’33 = U3+V3= -2+1=1 3.5. Метод потенциалов 57 3 шаг. Для каждой свободной клетки вычисляется оценка – разность между тарифом клетки и ее косвенным тарифом: ij = c – c’ ij ij План оптимален тогда, когда по каждой свободной клетке эта оценка неотрицательна. 3.5. Метод потенциалов 58 = C13 - C’13 = 4-1=3 22 = C22 - C’22 = 3-2=1 24 = C24 - C’24 = 2-6=-4 31 = C31- C’31 = 3-1=2 32 = C32 - C’32 = 2-0=2 33 = C33 - C’33 = 7-1=6 13 Полученный план перевозок не является оптимальным, так как среди оценок ij имеется отрицательная оценка 24 3.5. Метод потенциалов 59 4 шаг. Если есть хоть одна отрицательная оценка, то план надо улучшить, то есть построить новый план. Загружается та клетка, у которой оценка отрицательная. Если будет несколько отрицательных оценок, то выбирается клетка для загрузки, у которой отрицательная оценка наибольшая по абсолютной величине. 3.5. Метод потенциалов 60 В1 А1 А2 А3 спрос В2 3 20 В3 2 25 2 10 2 24 50 2 40 7 25 6 1 30 - запасы 5 3 3 30 4 - - - В4 4 20 20 30 25 110 = C24 - C’24 = 2-6= -4 3.5. Метод потенциалов 61 Для выбранной клетки строится замкнутый цикл, то есть замкнутый путь, соединяющий выбранную незаполненную клетку с ней же самой и проходящий через заполненные клетки. Для каждой свободной клетки существует только один цикл. В1 А1 А2 А3 спрос В2 3 20 2 25 2 10 - - 6 1 2 2 - 7 - 25 запасы 5 30 30 В4 4 3 3 - В3 4 20 30 25 50 40 20 110 3.5. Метод потенциалов 62 В каждой клетке цикла, начиная со свободной проставляются поочередно знаки «+» и «-». В клетках со знаком «-» (четные клетки) выбирается наименьший груз, который «перемещается» по клеткам замкнутого цикла, т.е. прибавляется к поставкам xij в клетках со знакам «+» (включая свободную) и вычитается в клетках со знаком «-». В1 А1 А2 А3 спрос В2 + 3 -10 2 20 2 25 1 30 2 6 2 + - 7 - 25 - запасы 5 - - 30 В4 4 3 3 - В3 4 20 30 25 50 40 20 110 В результате такого перемещения груза по циклу получим новый план перевозок. 3.5. Метод потенциалов 63 Строится новый план В1 А1 А2 А3 спрос В2 3 25 В3 2 25 2 5 2 2 5 7 - 25 6 1 30 - запасы - 3 3 30 4 - - - В4 4 20 30 25 50 40 20 110 Вычисления по методу потенциалов повторяются с 1 этапа 3.5. Метод потенциалов 64 В1 А1 А2 А3 спрос В2 3 U1+V1=3 2 U1+V2=2 2 U2+V2=2 - - 6 - 1 2 U2+V3=1 U2+V4=2 2 - 30 В4 4 3 3 - В3 7 - 25 4 U3+V4=4 30 25 запас ы 50 40 20 110 3.5. Метод потенциалов 65 Предполагается, что U1 = 0, тогда U1 = 0 U2 = 0 U3 = 2 V1 = 3 V2 = 2 V3 = 1 V4 = 2 3.5. Метод потенциалов В1 А1 А2 А3 спрос В2 3 25 В3 2 25 2 5 1 2 2 5 7 - 25 6 - 30 30 4 3 3 запас ы В4 - - - 66 30 4 20 25 = C13 - C’13 = 4-1=3 14 = C14 - C’14 = 6-2=4 22 = C22 - C’22 = 3-2=1 31 = C31- C’31 = 3-5=-2 32 = C32 - C’32 = 2-4=-2 33 = C33 - C’33 = 7-3=4 50 40 20 C’13 = U1+V3 = 0+1=1 C’14 = U1+V4 = 0+2=2 C’22 = U2+V2=0+2=2 C’31 = U3+V1=2+3=5 C’32 =U3+V2=2+2=4 C’33 = U3+V3= 2+1=3 110 13 Полученный план перевозок не является оптимальным, так как среди оценок ij имеется отрицательная оценка 31, 32 3.5. Метод потенциалов 67 План необходимо улучшить и построить новый В1 А1 А2 А3 спрос В2 3 25 В3 2 25 2 5 2 2 5 7 - 25 6 1 30 - запасы - 3 3 30 4 - - - В4 4 20 30 25 50 40 20 110 Загружается та клетка, у которой оценка отрицательная. 31 = C31- C’31 = 3-5=-2 32 = C32 - C’32 = 2-4=-2 3.5. Метод потенциалов 68 В1 А1 А2 А3 спрос В2 3 25 - В3 2 25 2 5 1 30 2 - 6 4 20 30 2 5+ 7 - 25 запасы - 3 3 30 4 - - +- В4 - 25 50 40 20 110 3.5. Метод потенциалов 69 Строится новый план В1 А1 А2 А3 спрос В2 3 25 В3 2 25 2 - 2 2 10 7 - 25 6 1 30 - запасы - 3 3 30 4 - - 5 В4 4 15 30 25 50 40 20 110 3.5. Метод потенциалов 70 Предполагается, что U1 = 0, тогда U1 = 0 U2 = -2 U3 = 0 V1 = 3 V2 = 2 V3 = 3 V4 = 4 3.5. Метод потенциалов В1 А1 А2 А3 71 В2 3 25 В3 2 25 2 - 3 1 2 - 2 10 7 - 25 6 - 30 3 5 спрос 30 4 - - запас ы В4 30 4 15 25 = C13 - C’13 = 4-3=1 14 = C14 - C’14 = 6-4=2 21 = C21- C’31 = 2-1=1 22 = C22 - C’22 = 3-0=3 32 = C32 - C’32 = 2-2=0 33 = C33 - C’33 = 7-3=4 50 40 20 C’13 = U1+V3 = 0+3=3 C’14 = U1+V4 = 0+4=4 C’21 = U2+V1=-2+3=1 C’22 = U2+V2=-2+2=0 C’32 =U3+V2=0+2=2 C’33 = U3+V3= 0+3=3 110 13 Полученный план перевозок является оптимальным, так как среди оценок ij нет отрицательных оценок 3.5. Метод потенциалов 72 Ответ: Оптимальный план грузоперевозок: В1 В2 3 А1 25 2 25 - - 5 спрос 4 2 30 2 10 7 - 25 6 1 30 - запасы - 3 3 А3 В4 - 2 А2 В3 4 15 30 25 50 40 20 110 Минимальная стоимость грузоперевозок: C 25 3 25 2 30 1 10 2 5 3 15 4 250 ден .ед . 3.5. Метод потенциалов 73