Транспортная задача

Транспортная задача. Метод потенциалов

Задача:  Фирма должна отправить некоторое количество компьютеров с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 компьютеров, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 компьютеров. Стоимость перевозки одного компьютера со склада в магазин приведены в таблице.

Метод северо-западного угла (диагональный)

Пример 1: Составить опорный план задачи методом северо-западного угла.

Решение:

Вычислим суммарную стоимость перевозок для построенного плана:

F =

Метод наименьшего элемента

Пример 2: Составить опорный план методом наименьшего элемента.

Решение:

Вычислим суммарную стоимость перевозок для построенного плана:

F =

Метод потенциалов решения транспортных задач

Пример 3: См. пример 1. Проверить построенный план на оптимальность методом потенциалов.

Решение:  Возьмем таблицу с построенным планом и добавим еще столбец и строку потенциалов.

По  заполненным клеткам вычислим потенциалы по правилу :

Для пустых клеток вычислим их оценки .

Будем их записывать в верхний правый угол клетки.

Пример 4: Для плана примера 3 построим цикл перерасчета (в предыдущей таблице) и построим второй опорный план:

Вычислим суммарную стоимость перевозок для построенного плана:

F =

Проверим план на оптимальность методом потенциалов.

Так среди оценок пустых клеток есть отрицательные. План - ____________________.

Построим цикл перерасчета таблицы.

Третий опорный план:

Вычислим суммарную стоимость перевозок для построенного плана:

F =

Проверим план на оптимальность методом потенциалов. План - __________________.

Построим цикл перерасчета таблицы.

Четвертый опорный план:

При этом суммарная стоимость перевозок

F =

Проверим план на оптимальность методом потенциалов. План - __________________.

Ответ:

Контрольные вопросы:

1.     Как построить опорный план транспортной задачи?

2.     В чем суть метода потенциалов?

3.     Как строится цикл перерасчета?

Задача:

На трех базах  А₁, А₂, А₃ имеется однородный груз в количестве 160, 155,85 условных единиц соответственно. Этот груз требуется перевести в четыре пункта потребления В₁, В₂ , В₃ и В₄ в количестве 115, 85, 130, 70 условных единиц соответственно. Стоимости перевозок единицы груза от поставщиков потребителям указаны в таблице в  матрице стоимостей С. Составить такой план перевозки грузов, при котором транспортные расходы будут наименьшими.

План урока

Учебная дисциплина    МАТЕМАТИЧЕСКИЕ МЕТОДЫ

Тема урока        Транспортная задача. Метод потенциалов 

Цели урока  

Учебные:

1.    Изучить понятие транспортной задачи и методы ее решения.

2.    Развить и закрепить навыки решения транспортных задач при помощи метода потенциалов.

Развивающие и воспитательные:

1.    Развитие личностно смыслового отношения к изучаемой дисциплине.

2.    Развитие познавательного потенциала студентов, умений сравнивать, анализировать, делать выводы.

3.    Демонстрация применения получаемых знаний во многих профессиональных сферах нашей жизни.

4.    Развитие, в условиях рыночной экономики, предпринимательских способностей студентов.

5.    Воспитание сотрудничества в коллективной деятельности.

6.    Воспитание дисциплинированности, целеустремленности студентов.

Оснащение урока:  дидактический материал, опорный конспект,  компьютерный кабинет, проектор, электронная презентация, интерактивная доска.

Ход урока:

1.    Организационный момент: 

проверка отсутствующих, заполнение журнала.

2.    Актуализация опорных знаний:   новая тема

3.    Изучение нового материала:

 (1 слайд)

Тема лекции: «Транспортная задача»

План лекции

1.    Введение.

2.    Постановка транспортной задачи.

3.    Методы решения транспортных задач.

4.    Метод потенциалов решения транспортных задач.

1.  Введение

Здравствуйте, ребята.

На прошлых занятиях мы рассмотрели общие подходы к решению задач линейного программирования. Однако существуют частные типы задач линейного программирования, которые в силу своей структуры допускают решения более простыми методами. Сегодня мы остановимся на одной из них – так называемой, транспортной задаче.

Под названием  “транспортная задача” объединяется широкий круг задач с единой математической моделью.

? вопрос?  Кто нам напомнит основную задачу математических методов?

(2 слайд)

Мы рассмотрим классическую транспортную задачу – это задача об оптимальном плане перевозок продукта(-ов) из пунктов отправления в пункты потребления, встречается чаще всего в практических приложениях линейного программирования.

(проф. направленность)

Где могут пригодиться вам полученные сегодня знания.

На каждом предприятии есть отдел логистики. Его работа заключается в организации рационального процесса продвижения товаров от производителей к потребителям, создания инфраструктуры товародвижения.

Логисты обязательно должны уметь работать в Word, Excel, Access. Так как все эти знания вы имеете, то вполне можете работать логистами в дальнейшем.

Логистов иначе называют «транспортными богами».

 (цель)  Сегодня на уроке нам необходимо разобрать транспортную задачу,  научиться строить математическую модель этой задачи и решать ее.

Как всегда изучение теоретического материала будем сопровождать примерами для лучшего понимания темы.

 (3 слайд)

(Историческая справка)  Но прежде, чем перейти к самой задаче, обратимся к истории:

Историческую справку нам сообщит ______________________.

(сообщение студента)

_______________________________________________________________

Проблема транспортной задачи была впервые формализована французским математиком Гаспаром Монжем в 1781 году, который выполнил работу о наиболее экономном способе перемещения масс для строительства военных укреплений.

А основное продвижение было сделано советским математиком и экономистом Леонидом Канторовичем.

В 1939 году к 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Леонид Витальевич писал: “оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения”. И уже летом 1939 года была сдана в набор книга Л.В.Канторовича “Математические методы организации и планирования производства”.

Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.

В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за “вклад в разработку теории и оптимального использования ресурсов в экономике”.

______________________________________________________________________

Прослушав данное сообщение, вы еще раз можете убедиться, какое широкое применение имеет транспортная задача.

(4 слайд)

2. Постановка транспортной задачи

Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2, ..., Аm соответственно в количествах а1, а2, ..., аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) В1, В2, ..., Вn соответственно в количествах b1, b2, ..., bn единиц. Стоимость перевозки (тариф) единицы продукции из Аi в Вj известна для всех маршрутов Ai, Bj и равна c_ij (i = 1, m; j = 1, n).

Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится, и запросы всех пунктов потребления удовлетворяются, а суммарные транспортные расходы минимальны.

Замечание:

Задача в данной формулировке, когда выполняется равенство

называется закрытой.

Чтобы мы могли решать данную задачу нам необходимо записать ее математическую модель.

? вопрос?  Кто нам напомнит, что такое математическая модель?

(5 слайд)

Математическая модель транспортной задачи

Наша задача найти значения х, которые удовлетворяют системе ограничений и целевой функции.

При этом нам понадобятся несколько определений:

Определение: Построенный план называется опорным, если в нем отличны от нуля m+n-1 базисных перевозок, а остальные перевозки равны 0.

Определение: Опорный план называется оптимальным, если он приводит к минимальной суммарной стоимости перевозок.

3.Методы решения транспортных задач

Перейдем  к решению задачи.

Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще.

(6слайд)

Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза X_ij ≥ 0, а в маленькие клетки – соответствующие тарифы C_ij.

(пояснения)

Наша задача заполнить все клетки числами x_ij (количеством перевозимого товара) так, чтобы их сумма по строкам была равна а_i  , по столбцам -b _j.  Затем эти числа умножаем на стоимости перевозок C_ij и складываем. И эта сумма должна принимать минимальное значение.

? вопрос? Сколько клеток нам необходимо заполнить, чтобы план был опорным?

(7 слайд)

Решение задачи разбивается на два этапа:

1.    Определение опорного плана.

2.    Нахождение оптимального решения путем последовательных операций.

Рассмотрим подробно каждый из этапов:

1.               Опорный план транспортной задачи можно найти, используя метод "северо-западного угла" или метод "минимального элемента".

(8 слайд)

Метод северо-западного угла (диагональный)

Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj.

Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj.

И так как каждый теоретический вопрос лучше сразу рассмотреть на примере, то у каждого на столе лежит опорный конспект, которым мы будем пользоваться в этих целях.

В конспекте записана задача, которую мы будем решать различными методами.

(9 слайд)

Задача:  Фирма должна отправить некоторое количество компьютеров с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 компьютеров, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 компьютеров. Стоимость перевозки одного компьютера со склада в магазин приведены в таблице.

Пример 1: Составить опорный план задачи методом северо-западного угла.

Решение: (интерактивная доска)

Исходная транспортная таблица имеет вид:

Построим опорный план.

Магазин В1 подал заявку на 20 компьютеров, но со склада А1 мы можем перевести 15 компьютеров, ещё 5 компьютеров мы перевезём со склада А2. Спрос для магазина В1 удовлетворён. Рассмотрим магазин В2. В него необходимо доставить 12 компьютеров - доставим их со склада А2.

На складе А2 осталось 8 компьютеров. Выделим из них пять для магазина В3. На складе А2 осталось 3 компьютера. Выделим их на магазин В3, но потребности магазина ещё не удовлетворены, поэтому выделим ему со склада А3 ещё пять компьютеров. Осталось 15 компьютеров, столько, сколько требуется в магазин В5.

Все заявки удовлетворены, все запасы израсходованы.

Проверим, является ли полученный план опорным: количество ячеек с ненулевыми перевозками равно m+n-1 = 7.

Опорный план: Х₁₁ = 15, Х₂₁ = 5, Х₂₂ = 12, Х₂₃ = 5, Х₂₄ = 3, Х₃₄ = 5, Х₃₅ = 15.

Все остальные X_ij = 0. Такие клетки будем называть пустыми.

Вычислим суммарную стоимость перевозок для построенного плана:

F = 1*15+5*5+1*12+2*5+3*3+4*5+3*15 = 136

Будет ли это минимальная стоимость перевозок, а план – оптимальным, проверим позже.

А сейчас рассмотрим другой метод составления опорного плана.

(10 слайд)

Метод наименьшего элемента

Сущность метода в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них. В остальном действуют аналогично предыдущему способу.

(интерактивная доска)

Пример 2: Составить опорный план задачи методом наименьшего элемента.

Решение: Исходная транспортная таблица имеет вид:

Построим опорный план.

Находим в таблице наименьшую стоимость перевозки – это 0 в клетке A1B2. Записываем в этой клетке значение 12 (наименьшее из сумм по строке и столбцу).

Теперь вычеркиваем второй столбец, уменьшив сумму в первой строке на 12.

Находим следующую наименьшую по стоимости ячейку – их несколько, например, A1B1. Присваиваем ей значение 3, а сумму по столбцу заменяем на 17.

Вычеркиваем первую строку.

Выбираем ячейку A3B3, присваиваем ей значение 5. Вычеркиваем третий столбец. Сумму по третьей строке заменяем на 15.

Выбираем ячейку A2B5, записываем в ней 15, уменьшаем вторую строку на 15 и вычеркиваем пятый столбец.

Выбираем ячейку A3B1, присваиваем ей 15. Уменьшаем первый столбец на 15 и вычеркиваем третью строку.

Ячейке A2B1 присваиваем 2 и вычеркиваем первый столбец. Сумму по второй строке заменяем на 8.

Ячейке A2B4 присваиваем 8 и вычеркиваем четвертый столбец.

Опорный план построен.

Количество заполненных клеток  3+5-1=7.

Х₁₁ = 3, Х₁₂ = 12, Х₂₁ = 2, Х₂₄ = 8, Х₂₅ = 15, Х₃₁ = 15, Х₃₃ = 5.

Все остальные Х_ij = 0.

Вычислим суммарную стоимость перевозок для построенного плана:

F = 3*1+0*12+5*2+3*8+3*15+5*1 = 147.

147>136, т.е. данный план точно не оптимальный.

Итак, мы изучили 2 способа построения первого опорного плана. При решении задачи вы выбираете тот способ, который вам больше понравился (долее понятен).

2.Теперь необходимо проверить, будет ли построенный план оптимальным, т.е. получим ли мы минимальную стоимость перевозок.

Для этого воспользуемся методом потенциалов.

4.Метод потенциалов решения транспортных задач

(11 слайд)

Метод потенциалов:

Введем строку потенциалов u_i и столбец потенциалов v_j.

Полагая, что u₁=0,  остальные u_i и v_j найдем так, чтобы

а) для заполненных клеток  выполнялись равенства ;

б) для незаполненных клеток  выполнялись равенства  (оценки пустых клеток).

(12 слайд)

Критерий оптимальности:

Если известны потенциалы решения Х₀ транспортной задачи и для всех незаполненных ячеек выполняются условия то Х₀ является оптимальным планом транспортной задачи.

Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались.

Пример3: Проверить план,  построенный методом северо-западного угла на оптимальность методом потенциалов.

Возьмем таблицу с построенным планом и добавим еще столбец и строку потенциалов.

(перепишите в свою заготовленную таблицу план, полученный методом северо-западного угла).

По  заполненным клеткам вычислим потенциалы по правилу :

Таким образом, мы вычислили потенциалы заполненных клеток.

Для пустых клеток вычислим их оценки .

Будем их записывать в верхний правый угол клетки.

Так среди оценок пустых клеток есть отрицательные – план не оптимальный.

Необходимо построить следующий план. Для этого построим цикл перерасчета таблицы.

(13 слайд)

Цикл перерасчёта таблицы – это последовательность клеток, удовлетворяющая условиям:

§    Одна клетка пустая с отрицательной оценкой, все остальные  заполненные.

§    Любые две соседние клетки находятся в одной строке или в одном столбце.

§  Пустой клетке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".

 (14 слайд)

Далее составляем новую таблицу по следующему правилу:

§  Клетки вне цикла остаются без изменения.

§  В  минусовых клетках находят число X = min(X_ij).

§  В плюсовых клетках  цикла добавляем Х.

§  Из минусовых клеток цикла вычитаем Х.

Получим новую таблицу, дающую новое решение Х, такое, что F (X₁) ≤ F (X₀); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.

(интерактивная доска)

Пример4: Для плана примера 3 построим цикл перерасчета.

Заполним одну из пустых клеток с отрицательной оценкой. Возьмем клетку А3В3, так как в ней стоимость меньше, чем в клетке А3В1.

Построим цикл перерасчета:

Построим второй опорный план:

Заполненных клеток должно быть 3+5-1=7.

Вычислим суммарную стоимость перевозок для построенного плана:

F = 15*1+5*5+12*1+0*2+5*1+8*3+15*3=126.

Проверим план на оптимальность методом потенциалов.

Так среди оценок пустых клеток есть отрицательные – план не оптимальный.

Построим следующий план.  

Для этого построим цикл перерасчета таблицы.

Третий опорный план:

Вычислим суммарную стоимость перевозок для построенного плана:

F = 15*1+5*5+12*1+5*1+8*3+0*3+15*3=126.

Проверим план на оптимальность методом потенциалов.

Так среди оценок пустых клеток есть отрицательные – план не оптимальный.

Построим следующий план.

Для этого построим цикл перерасчета таблицы.

Четвертый опорный план:

Так как среди оценок пустых клеток нет отрицательных значений, то построенный план оптимальный.

При этом суммарная стоимость перевозок

F = 15*1+5*4+12*1+5*1+8*3+0*3+15*3=121 является минимальной.

Запишем ответ задачи:

Ответ: Чтобы транспортные расходы были минимальными 121 ден.ед. необходимо перевозить: с 1-го склада – 15 компьютеров в 1-ый магазин; со 2-ого склада – 12 - во 2-ой магазин, 8 - в 4-ый и 5 - в 5-ый магазин; с 3-его склада – 5 компьютеров в 1-ый магазин, 5 – во 2-ой и 10 – в 5-ый.

4.  Закрепление нового материала:   ответы на контрольные вопросы: (15 слайд)

1.    Как построить опорный план транспортной задачи?

2.    В чем суть метода потенциалов?

3.    Как строится цикл перерасчета?

 (16, 17 слайды)

Еще хотелось бы обратить ваше внимание, на различные виды циклов перерасчета таблицы.

5. Подведение итогов урока: выводы, оценки, домашнее задание:

Наш урок подходит к концу.   Работой вашей на уроке я довольна, но хотелось бы обратить внимание _________________________________________.

За подготовленное сообщение _________________получает оценку _______.

За работу у доски ____________________________________________.

На следующем занятии - практическая работа №4 по изученной теме.

Чтобы лучше ее выполнить запишите  Домашнее задание.

Контрольные вопросы и задача записаны в опорном конспекте.

Если у вас остались вопросы по решению систем линейных уравнений, то еще не поздно их задать.

Спасибо за урок.

До свидания.

Домашнее задание:

Контрольные вопросы.

Задача:

На трех базах  А₁, А₂, А₃ имеется однородный груз в количестве а₁, а₂, а₃ условных единиц соответственно. Этот груз требуется перевести в четыре пункта потребления В₁, В₂ , В₃ и В₄ в количестве b₁, b₂ , b₃ и b₄ условных единиц соответственно. Стоимости перевозок единицы груза от поставщиков потребителям указаны в таблице в  матрице стоимостей С.

Составить такой план перевозки грузов, при котором транспортные расходы будут наименьшими.

а₁=160, а₂=155, а₃=85

b₁=115, b₂ =85, b₃=130, b₄=70

Подпись преподавателя

Приложение 1

Решение задачи методом минимального элемента

Найдём оптимальный план для рассмотренной выше задачи.

В качестве опорного плана возьмем план, полученный с помощью метода  "минимального элемента" Х₁₁ = 3, Х₁₂ = 12, Х₂₁ = 2, Х₂₄ = 8, Х₂₅ = 15, Х₃₁ = 15, Х₃₃ = 5. Все остальные элементы равны 0.

Так как у нас получились отрицательные значения, то полученный план не является оптимальным. Выберем ячейку для пересчета A2B2. Получим:

X = min(2, 12) = 2

Строим следующую транспортную таблицу.

Проверим полученный план на оптимальность с помощью метода потенциалов.

Т.к. есть отрицательные оценки пустых ячеек, то построенный план не является оптимальным, следовательно, производим пересчет. Выберем ячейку A3B5.

X = min(15, 10, 15) = 10, значит вычитать и прибавлять в ячейках, будем 10.

Строим следующую транспортную таблицу.

Проверим построенный план на оптимальность.

Т.к. отрицательных оценок пустых ячеек нет, то полученный план является оптимальным. Х₁₁ = 15, Х₂₂ = 12, Х₂₄ = 8, Х₂₅ = 5, Х₃₁ = 5, Х₃₃ = 5, Х₃₅ = 10. Все остальные Х_ij = 0.

F = 1*15+1*12+3*8+3*5+4*5+1*5+3*10 = 121.

Тема лекции: «Транспортная задача»

План лекции

1.     Построение математической модели транспортной задачи.

2.     Методы решения транспортных задач.

3.     Метод потенциалов решения транспортных задач.

1. Построение математической модели транспортной задачи

Мы рассмотрели общие подходы к решению задач линейного программирования. Однако существуют частные типы задач линейного программирования, которые в силу своей структуры допускают решения более простыми методами. Мы остановимся только на одной из них – так называемой транспортной задаче.

Постановка транспортной задачи

Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2, ..., Аm соответственно в количествах а1, а2, ..., аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) В1, В2, ..., Вn соответственно в количествах b1, b2, ..., bn единиц. Стоимость перевозки (тариф) единицы продукции из Аi в Вj известна для всех маршрутов Ai, Bj и c_ij (i = 1, m; j = 1, n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится, и запросы всех пунктов потребления удовлетворяются (закрытая модель), т. е:   а суммарные транспортные расходы минимальны.

Математическая модель транспортной задачи

План, будем называть опорным, если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны 0.

План будет называться оптимальным, если он, среди всех допустимых планов, приводит к минимальной суммарной стоимости перевозок.

2.Методы решения транспортных задач

Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще.

Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза X_ij ≥ 0, а в маленькие клетки – соответствующие тарифы C_ij.

Затем решение задачи разбивается на два этапа:

1.     Определение опорного плана.

2.     Нахождение оптимального решения путем последовательных операций.

1.Найдем вначале допустимое (опорное) решение транспортной задачи. Это решение можно найти, используя метод "северо-западного угла" или метод "минимального элемента".

Метод северо-западного угла (диагональный)

Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, удовлетворяют ли найденные компоненты плана Х_ij горизонтальным и вертикальным уравнениям.

Пример 1: Построим опорный план методом северо-западного угла.

Метод наименьшего элемента

Сущность метода в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них. В остальном действуют аналогично предыдущему способу.

Пример 2: Построим опорный план методом наименьшего элемента.

3.Метод потенциалов решения транспортных задач

Для проверки построенного опорного плана на оптимальность применяется метод потенциалов.

Метод потенциалов:

Введем строку потенциалов u_i и столбец потенциалов v_j. Полагая, что u₁=0, а остальные u_i и v_j найдем так, чтобы

а) для заполненных ячеек выполнялись равенства ;

б) для незаполненных ячеек выполнялись равенства

Критерий оптимальности

Если известны потенциалы решения Х₀ транспортной задачи и для всех незаполненных ячеек выполняются условия то Х₀ является оптимальным планом транспортной задачи.

Для построения второго опорного плана необходимо применить цикл перерасчёта таблицы – это последовательность ячеек, удовлетворяющая условиям:

1.     Одна ячейка пустая, все остальные занятые.

2.     Любые две соседние ячейки находятся в одной строке или в одном столбце.

Пустой ячейке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".

В минусовых клетках находят число X = min(X_ij). Далее составляют новую таблицу по следующему правилу:

3.     В плюсовых клетках добавляем Х.

4.     Из минусовых клеток вычитаем Х.

5.     Все остальные клетки вне цикла остаются без изменения.

Пример 3: См. пример 2. Проверить построенный план на оптимальность методом потенциалов.

Решение:  Возьмем таблицу с построенным планом и добавим еще столбец и строку потенциалов.

По  заполненным клеткам вычислим потенциалы по правилу :

Для пустых клеток вычислим их оценки .

Будем их записывать в верхний правый угол клетки.

Пример 4: Для плана примера 3 построим цикл перерасчета (в предыдущей таблице) и построим второй опорный план: Заполняем клетку_________

Вычислим суммарную стоимость перевозок для построенного плана:

F =

Проверим план на оптимальность методом потенциалов.

План - ______________________________________________________________________________

Построим цикл перерасчета таблицы. Заполняем клетку_________

Третий опорный план:

Вычислим суммарную стоимость перевозок для построенного плана:

F =

Проверим план на оптимальность методом потенциалов.

План - ________________________________________

Ответ: _________________________________________________________________________

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Контрольные вопросы:

1.     Приведите пример транспортной задачи.

2.     В чем суть метода потенциалов?

3.     Что находится изначально: опорный план перевозок или оптимальный план перевозок?

Задачи на закрепление:

На трех базах  А₁, А₂, А₃ имеется однородный груз в количестве а₁, а₂, а₃ условных единиц соответственно. Этот груз требуется перевести в четыре пункта потребления В₁, В₂ , В₃ и В₄ в количестве b₁, b₂ , b₃ и b₄ условных единиц соответственно. Стоимости перевозок единицы груза от поставщиков потребителям указаны в таблице в  матрице стоимостей С. Составить такой план перевозки грузов, при котором транспортные расходы будут наименьшими.

1) а₁=140, а₂=120, а₃=170    

b₁=98, b₂ =122, b₃=100, b₄=110

2)а₁=160, а₂=140, а₃=100             

b₁=90, b₂ =54, b₃=176, b₄=80