Презентация на тему Транспортная задача

сосредоточены запасы какого-либо однородного груза в объемах соответственно:
Величины at

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

Суммарный запас груза поставщиков составляет
Кроме того, имеется п пунктов назначения:

которые подали заявки на поставку грузов в объемах соответ­ственно:
Суммарная величина заявок составляет .

к потребителю Bj обозначим через cij (транспортный тариф). Общая

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

виде таблице, которая называется транспортной: С и X.

X, которая удовлетворяет условиям: 
∑xij=ai
 
∑xij=bj
 
F=∑∑cij*xij →min
 

перевозок всех грузов, которая долж­на быть минимальной.
Экономико-математическая модель транспортной

задачи содержит системы линейных уравнений, условие неотрицательности переменных xij и целевую функцию. 
Следует иметь в виду, что:
1. Всякое неотрицательное решение системы линейных уравнений, определяемое матрицей X = (хij), i = 1, k; j = 1, л; называется допустимым планом транспортной задачи.
2. Ранг матрицы, составленный из коэффициентов при не­известных системы линейных уравнений транспортной задачи, на единицу меньше числа уравнений, т. е. равен (т + п - 1). Следовательно, число линейно независимых уравнений равно (т + п - 1), они образуют базис, а соответствующие им (т + п - 1) переменных будут являться базисными.
3. Допустимый план транспортной задачи, имеющий не более (т + п - 1) отличных от нуля величин xij, называется опорным.

нуля компонент равно в точности (т + п -

1), то план является невырожденным, если меньше, то план называется вырожденным.
5. План X = (хij) (i = l, т; j = 1, п), при котором функция принимает свое минимальное значение, называется оп­тимальным планом транспортной задачи.
6. Для решения транспортной задачи необходимо и доста­точно, чтобы суммарные запасы груза в пунктах отправления были равны сумме заявок пунктов назначения:

7. Модель транспортной задачи, удовлетворяющая условию, называется закрытой. Если же указанное условие не вы­полняется, то модель называется открытой.

+ 1) пункт назначения с потребностью­ bn+1=∑ai-∑bj и

соответствующие тарифы считаются равными нулю ci,n+1=0.
При

вводится фиктивный (m + 1) пункт отправ­ления с запасом груза

и соответствующие тари­фы принимаются равными нулю:

если задача поставлена на минимум, наибольший тариф - если

задача поставлена на максимум целевой функции.
Алгоритм построения первого опорного плана методом наи­меньшей стоимости включает следующие этапы:
а) среди тарифов находится наименьший;
б) клетка с выбранным тарифом заполняется величиной, равной максимально возможному объему груза с учетом огра­ничений по строке и столбцу. При этом либо весь груз вывозит­ся от соответствующего поставщика, либо полностью удовлет­воряется заявка потребителя. Строка или столбец таблицы вы­черкивается и в дальнейшем распределении не участвует;
в) из оставшихся тарифов вновь находится наилучший (наи­меньший), и процесс продолжается до тех пор, пока не будет распределен весь груз.

фик­тивный поставщик или потребитель, то распределение осуществ­ляется сначала для

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

оптималь­ным, если существует система т + п чисел αi,

βj называемых потенциалами, удовлетворяющая условиям:
 
1. F(X) →min
ai+bj = cij для занятых клеток, где xij>0
ai+bj ≤ cij для занятых клеток, где xij=0
 
2. F(X) →max
ai+bj = cij для занятых клеток, где xij>0
ai+bj ≥ cij для занятых клеток, где xij=0

Потенциалы ai и bj являются переменными двойственной транспортной задачи и обозначают оплату за перевозку едини­цы груза в пунктах отправления (поставщиками) и назначения (потребителями) соответственно, поэтому их сумма равна транс­портному тарифу аi + bj = cij, а условия получены на основании второй теоремы двойственности.

оценок нет положительных (задача поставле­на

на минимум), то опорный план является оптимальным.
Алгоритм оценки оптимальности плана методом потенциа­лов включает следующие этапы.
а. Построение первого опорного плана.
б. Проверка вырожденности плана. Потенциалы ai и bj мо­гут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане меньше, чем (т + п - 1), то не хватит количества уравнений для определения потенциалов, поэтому вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным (т + п - 1). Нуль вводят в клетку с наименьшим тарифом, например в клетку од­новременно вычеркиваемых строки и столбца таблицы при со­ставлении нового плана. При этом фиктивно занятая нулем клетка не должна образовывать замкнутого прямоугольного контура с другими клетками таблицы.

(удельных затрат) на объем перево­зимого груза по всем занятым

клетками таблицы.
г. Проверка условия оптимальности. Определяем потенциалы ai и bj. Для каждой занятой клетки таблицы записываем уравне­ние


Получим систему (т + п - 1) уравнений с (т + п) переменными.
Так как число переменных больше числа уравнений, то система является неопределенной и имеет беско­нечное множество решений. Поэтому одному из неизвестных потенциалов аi, bj задают произвольное значение, например, для простоты вычислений полагаем a1 = 0. Тогда остальные потен­циалы определяются из приведенных соотношений.
В транспортную таблицу добавляются дополнительная стро­ка и столбец, куда заносятся потенциалы.
Определяем оценки свободных клеток

(задача решается на минимум целевой фун­кции) либо все

(задача решается на максимум целевой функции), то оптимальный план найден. Если хотя бы одна оценка свободной клетки (задача поставлена на минимум) или (задача поставлена на максимум), план не является оптимальным, его можно улучшить, осуществив перераспреде­ление груза.
д. Построение нового опорного плана. Из всех положитель­ных оценок свободных клеток выбираем наибольшую (если зада­ча поставлена на минимум), из отрицательных — наибольшую по абсолютной величине (если задача поставлена на максимум). Клетку, которой соответствует наибольшая оценка, следует запол­нить,
т. е. направить груз.
Заполняя выбранную клетку, необхо­димо изменить объемы поставок, записанных в ряде других за­нятых и связанных с заполняемой так называемым циклом.

задачи называется ломаная линия, вершины кото­рой расположены в занятых

клетках таблицы, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, другое - в столбце. Если ломаная линия, образующая цикл, пересекается, то точки пересечения не являются вершинами. Для каждой сво­бодной клетки таблицы можно построить единственный цикл.
Вершинам цикла, начиная от вершины, находящейся в сво­бодной клетке, присваиваем поочередно знаки « + » и «-».
Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее и обозначим его γ. Перераспределяем величину γ по циклу, прибавляя γ к соответствующим объемам груза, стоящим в плюсовых клетках и вычитая у из объемов груза, находящих­ся в минусовых клетках таблицы. В результате клетка, которая ранее была свободной, становится занятой, а одна из занятых клеток цикла становится свободной.
Полученный новый опорный план проверяется на оптималь­ность, т. е. возвращаемся к четвертому этапу алгоритма.

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

груза освобождаются две (или несколько) клеток, и план становится вырожденным. Для про­должения решения необходимо одну или несколько освобожда­ющихся клеток таблицы занять нулем, причем предпочтение отдается клетке с наилучшим тарифом. Нулей вводится столько, чтобы во вновь полученном опорном плане число занятых кле­ток было равно (т + п - 1).
Если в оптимальном плане транспортной задачи оценка сво­бодной клетки равна нулю , то задача имеет множество оп­тимальных планов. Для клетки с нулевой оценкой можно постро­ить цикл и перераспределить груз. В результате полученный опти­мальный план будет иметь такое же значение целевой функции.

следующим образом:

(задача поставлена на минимум);
(задача поставлена на максимум),
где - величина перемещаемого по циклу объема груза;
- оценка свободной клетки, в которую направляется груз при переходе к новому плану;
  значение целевой функции на к-й итерации;
значение целевой функции на предыдущей итерации.

поступил однородный груз в количествах, соответственно равных 6, 8,

10 ед. Этот груз требуется перевезти в четыре магазина Вх, В2, В3, В4 соответ­ственно в количествах 4, 6, 8, 8 ед. Стоимость доставки едини­цы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов (тыс. руб. за ед. груза):
1 2 4 3
С = 4 3 8 5
2 7 6 3
i =1,2,3 j= 1,2,3,4
 
∑ai = 6+8+10=24
 
∑bj=4+6+8+8=26
 
Отсюда следует, что транспортная задача является открытой. Введем дополнительную базу А4 с запасом груза 26-24=2 ед. Тарифы перевозки полагаем равными нулю.

3 + 4- 8 + 2- 6 + 8-

3 + 2- 0 = 88 тыс. руб,

то план IV является оптимальным, что можно представить в

виде матрицы:







Анализ плана. С первой базы необходимо весь груз напра­вить в третий магазин, со второй базы направить в первый и второй магазины в количестве 2 ед. и 6 ед., а груз с третьей базы следует вывозить в первый и четвертый магазины в количестве 2 и 8 ед. соответственно. При этом потребность третьего магази­на В3 остается неудовлетворенной в объеме 2 ед. Общая сто­имость доставки груза потребителям будет минимальной и со­ставляет 78 тыс. руб. Так как оценка свободной клетки Δ24 = О, то задача имеет множество оптимальных планов.

снабжения.
Три фермерских хозяйства Л1, Л2, Л3 ежедневно могут доставлять

в город соответственно 60, 60 и 50 ц молока для обеспечения пяти торговых точек: В1 В2, В3, В4, В5. Стоимость перевозки 1 ц молока и потребности торговых точек в молоке указаны в таблице:

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

= 1,5) — количество молока, постав­ляемое фермерским хозяйством J

в I -ю торговую точку.
Целевая функция — суммарные транспортные издержки, кото­рые необходимо минимизировать:

результат реше­ния.
Изменяемые ячейки — В11: F13. В эти ячейки

в результате ре­шения задачи будут записаны оптимальные значения Хij.
2. Ввести исходные данные.

3. Ввести зависимости для ограничений.

Поместите курсор в ячейку G11.
Выберите функцию СУММ.
Выделите необходимые для суммирования ячейки B11:F11.
Нажмите кнопку ОК для подтверждения ввода формулы для суммирования

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

для ее вычисления:
Запустите Мастер функций (значок fx).
В окне Категория выберите Математические.
В окне Функция выберите СУММПРОИЗВ.
Нажмите кнопку ОК.
В окне СУММПРОИЗВ укажите адреса массивов, элементы которых обрабатываются этой функцией
В нашей задаче целевая функция представляет собой произ­ведение затрат на доставку молока (ячейки B3:F5) и объемов поставок для каждого потребителя (содержимое ячеек В11 :F13). В поле Массив1 укажите адреса B3:F5.
В поле Массив2 укажите адреса B11:F13.
Нажмите кнопку ОК.
В поле ячейки G14 появится некоторое числовое значение, равное произведению поставок на коэффициенты затрат по до­ставке грузов

диа­логовое окно Добавление ограничения.
Первая запись в поле В соответствии

с ограничениями представляет собой ограничения по уровню спроса, вторая запись — ограничения по уровню запасов.
После ввода всех ограничений нажмите кнопку ОК.
Ввести параметры для решения ЗЛП.
Установите флажок: Сделать переменные без ограничений неотрицатель­ными.
В окне Выберите метод решения укажите Поиск решения линейных задач симплекс-методом.
Нажмите кнопку Найти решение — на экране появится диалого­вое окно Результаты поиска решения

ден. ед. Спрос торговых точек удовлетворен полностью — они

получат 150 ц молока. У первого фермерского хозяйства останется нереализованным 20 ц молока.
Следует иметь в виду, что при решении задач в Excel резуль­таты иногда выдаются в экспоненциальной форме записи. Данный формат используется для отображения и вывода очень больших (45 ООО ООО ООО ООО, в Excel это 4.5Е+13) или очень малых чисел (0,000 000 002 1, в Excel это 2.1Е-09).
Надстройка Поиск решения при заданной точности решения такие числа (например, 2.1Е-09) не отличает от нуля.

которой для выполнения каждой работы требуется один и только

один ресурс (один человек, одна автомашина и т.д.) и каждый ресурс может быть использован на одной и только одной работе, т.е. ресурсы неделимы между работами, а работы недели­мы между ресурсами. Таким образом, задача о назначениях явля­ется частным случаем транспортной задачи. Задача о назначени­ях имеет место при распределении людей на должности или ра­боты, автомашин на маршруты, водителей на машины, групп по аудиториям, научных тем по научно-исследовательским лабора­ториям и т.п.