Транспортные задачи

Транспортные задачи

Содержание

Введение

. Транспортная модель закрытого типа

.1 Условие задачи

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

.2.1 Построение опорного плана методом северо-западного угла

.2.2 Построение опорного плана методом минимальной стоимости

.2.3 Построение опорного плана методом Фогеля

.3 Оптимизация транспортной модели закрытого типа

.3.1 Метод потенциалов на основе опорного плана, построенного методом северо-западного угла

.3.2 Метод потенциала на основе опорного плана, построенного методом минимальной стоимости

.3.3 Метод потенциалов на основе опорного плана, построенного методом Фогеля

. Транспортная модель открытого типа

.1 Условия задачи

.2.1 Построение опорного плана методом северо-западного угла

.2.2 Построение опорного плана методом минимальной стоимости

.2.3 Построение опорного плана методом Фогеля

.3 Оптимизация транспортной модели открытого типа

.3.1 Метод потенциала на основе опорного плана, построенного методом северо-западного угла

.3.1 Метод потенциала на основе опорного плана, построенного методом минимальной стоимости

.3.1 Метод потенциала на основе опорного плана, построенного методом Фогеля

Заключение

Список использованных источников

Введение

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

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

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления в п пунктов назначения . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через - запасы груза в i-м пункте отправления, через - потребности в грузе в j-м пункте назначения, а через - количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

Для решения транспортной задачи используются три основных способа:

метод северо-западного угла;

метод минимальной стоимости;

метод Фогеля.

С помощью указанных методов строятся опорные планы перевозок и корректируются с применением метода потенциалов.

Решение транспортной задачи позволяет принять оптимальное решение по построению плана перевозок.

Целью данной работы является решение транспортной задачи в заданных условиях.

В связи с поставленной целью необходимо решить ряд задач:

построить опорные планы транспортной модели методами северо-западного угла, минимальной стоимости и методом Фогеля;

произвести оценку полученных решений методом потенциалов;

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

.       
Транспортная модель закрытого типа

транспортный модель оптимизация

1.1    Условие задачи

В соответствии с заданием на курсовую работу необходимо решить транспортную задачу. Первичный опорный план необходимо найти тремя способами: методом северо-западного угла, методом минимальной стоимости, методом Фогеля. Для каждого найденного опорного плана произвести перепланировку поставок методом потенциалов.

Исходные данные:

а1 =120

а2 =110

а3 = 20

а4 = 70

b1 = 225= 135= 140

1.2    Построение опорных планов транспортной модели

1.2.1 Построение опорного плана методом северо-западного угла

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

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

Согласно условию задачи составим таблицу. (тарифы Сij располагаются в нижнем правом углу ячейки).

Рассмотрим маршрут доставки от поставщика A1 к потребителю B1 (ячейка A1B1).

Запасы поставщика A1 составляют 120 единиц продукции. Потребность потребителя B1 составляет 225 единиц продукции.

От поставщика A1 к потребителю B1 будем доставлять min = (120 , 225) = 120 единиц продукции.

Разместим в ячейку A1B1 значение равное 120.

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

Рассмотрим маршрут доставки от поставщика A2 к потребителю B1 (ячейка A2B1).

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B1 составляет 105 единиц продукции.

От поставщика A2 к потребителю B1 будем доставлять min = (110 , 105) = 105 единиц продукции.

Разместим в ячейку A2B1 значение равное 105

Мы полностью удовлетворили потребность потребителя B1. Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Рассмотрим маршрут доставки от поставщика A2 к потребителю B2 (ячейка A2B2).

Запасы поставщика A2 составляют 5 единиц продукции. Потребность потребителя B2 составляет 135 единиц продукции.

От поставщика A2 к потребителю B2 будем доставлять min = ( 5 , 135 ) = 5 единиц продукции.

Разместим в ячейку A2B2 значение равное 5

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

Рассмотрим маршрут доставки от поставщика A3 к потребителю B2 (ячейка A3B2).

Запасы поставщика A3 составляют 20 единиц продукции. Потребность потребителя B2 составляет 130 единиц продукции.

От поставщика A3 к потребителю B2 будем доставлять min = (20 , 130) = 20 единиц продукции.

Разместим в ячейку A3B2 значение равное 20

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

Рассмотрим маршрут доставки от поставщика A4 к потребителю B2 (ячейка A4B2).

Запасы поставщика A4 составляют 70 единиц продукции. Потребность потребителя B2 составляет 110 единиц продукции. От поставщика A4 к потребителю B2 будем доставлять min = ( 70 , 110) = 70 единиц продукции.

Разместим в ячейку A4B2 значение равное 70

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

Рассмотрим маршрут доставки от поставщика A5 к потребителю B2 (ячейка A5B2).

Запасы поставщика A5 составляют 180 единиц продукции. Потребность потребителя B2 составляет 40 единиц продукции. От поставщика A5 к потребителю B2 будем доставлять min = ( 180 , 40 ) = 40 единиц продукции.

Разместим в ячейку A5B2 значение равное 40

Мы полностью удовлетворили потребность потребителя B2. Вычеркиваем столбец 2 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Рассмотрим маршрут доставки от поставщика A5 к потребителю B3 (ячейка A5B3).

Запасы поставщика A5 составляют 140 единиц продукции. Потребность потребителя B3 составляет 140 единиц продукции. От поставщика A5 к потребителю B3 будем доставлять 140 единиц продукции.

Разместим в ячейку A5B3 значение равное 140

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

В результате решения получим следующую таблицу.

Заполненные нами ячейки будем называть базисными, остальные - свободными.

Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.

Количество базисных ячеек (задействованных маршрутов) равно 7, что и требовалось.

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

= 1 * 120 + 3 * 105 + 4 * 5 + 4 * 20 + 3 * 70 + 0 * 40 + 0 * 140 = 745 ден. ед.

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

Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем:

• Находим потенциалы поставщиков и потребителей для имеющегося решения.

• Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена.

• Выбираем свободную ячейку (с отрицательной оценкой), выбор которой, позволяет максимально снизить общую стоимость доставки всей продукции на данном шаге решения.

• Находим новое решение, как минимум, не хуже предыдущего.

• Вычисляем общую стоимость доставки всей продукции для нового решения.

.2.2   Построение опорного плана методом минимальной стоимости

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

Согласно условию задачи составим таблицу (тарифы cij располагаются в нижнем правом углу ячейки).

Минимальный элемент матрицы тарифов находится в ячейке A1B1 и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B1 наиболее рентабельный.

Запасы поставщика A1 составляют 120 единиц продукции. Потребность потребителя B1 составляет 225 единиц продукции.

От поставщика A1 к потребителю B1 будем доставлять min = (120 , 225) = 120 единиц продукции.

Разместим в ячейку A1B1 значение равное 120

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

Минимальный элемент матрицы тарифов находится в ячейке A2B3 и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B3 наиболее рентабельный.

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B3 составляет 140 единиц продукции. От поставщика A2 к потребителю B3 будем доставлять min = (110 , 140) = 110 единиц продукции.

Разместим в ячейку A2B3 значение равное 110

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

Минимальный элемент матрицы тарифов находится в ячейке A4B1 и равен 2, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A4 к потребителю B1 наиболее рентабельный.

Запасы поставщика A4 составляют 70 единиц продукции. Потребность потребителя B1 составляет 105 единиц продукции.

От поставщика A4 к потребителю B1 будем доставлять min = (70 , 105) = 70 единиц продукции.

Разместим в ячейку A4B1 значение равное 70

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

Минимальный элемент матрицы тарифов находится в ячейке A3B2 и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A3 к потребителю B2 наиболее рентабельный.

Запасы поставщика A3 составляют 20 единиц продукции. Потребность потребителя B2 составляет 135 единиц продукции.

От поставщика A3 к потребителю B2 будем доставлять min = (20 , 135) = 20 единиц продукции.

Разместим в ячейку A3B2 значение равное 20

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

Минимальный элемент матрицы тарифов находится в ячейке A5B1 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A5 к потребителю B1 наиболее рентабельный.

Запасы поставщика A5 составляют 180 единиц продукции. Потребность потребителя B1 составляет 35 единиц продукции.

От поставщика A5 к потребителю B1 будем доставлять min = (180 , 35) = 35 единиц продукции.

Разместим в ячейку A5B1 значение равное 35

Мы полностью удовлетворили потребность потребителя B1. Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Минимальный элемент матрицы тарифов находится в ячейке A5B2 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A5 к потребителю B2 наиболее рентабельный.

Запасы поставщика A5 составляют 145 единиц продукции. Потребность потребителя B2 составляет 115 единиц продукции. От поставщика A5 к потребителю B2 будем доставлять min = ( 145 , 115 ) = 115 единиц продукции.

Разместим в ячейку A5B2 значение равное 115

Мы полностью удовлетворили потребность потребителя B2. Вычеркиваем столбец 2 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Минимальный элемент матрицы тарифов находится в ячейке A5B3 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A5 к потребителю B3 наиболее рентабельный.

Запасы поставщика A5 составляют 30 единиц продукции. Потребность потребителя B3 составляет 30 единиц продукции.

От поставщика A5 к потребителю B3 будем доставлять 30 единиц продукции.

Разместим в ячейку A5B3 значение равное 30

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

Заполненные нами ячейки будем называть базисными, остальные - свободными.

Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.

Количество базисных ячеек (задействованных маршрутов) равно 7, что и требовалось.

Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.= 1 * 120 + 1 * 110 + 4 * 20 + 2 * 70 + 0 * 35 + 0 * 115 + 0 * 30 = 450 ден. ед.

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

.2.3   Построение опорного плана методом Фогеля

Согласно условию задачи построим опорный план методом Фогеля.

В каждой строке, найдем разность i между двумя ячейками (доступными для выбора) с наименьшими тарифами.

Из полученных разностей выберем наибольшую.

Наибольшей разностью обладает столбец 3. В данном столбце выберем ячейку A2B3, как обладающую наименьшим тарифом.

Стоимость доставки единицы продукции от поставщика A2 к потребителю B3, как минимум, на 2 ден.ед. меньше чем от остальных поставщиков к потребителю B3.

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B3 составляет 140 единиц продукции. От поставщика A2 к потребителю B3 будем доставлять min = (110 , 140) = 110 единиц продукции.

Разместим в ячейку A2B3 значение равное 110

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

Наибольшей разностью обладает столбец 3. В данном столбце выберем ячейку A4B3, как обладающую наименьшим тарифом.

Стоимость доставки единицы продукции от поставщика A4 к потребителю B3, как минимум, на 5 ден.ед. меньше чем от остальных поставщиков к потребителю B3 (см. правую таблицу).

Запасы поставщика A4 составляют 70 единиц продукции. Потребность потребителя B3 составляет 30 единиц продукции.

От поставщика A4 к потребителю B3 будем доставлять min = (70 , 30) = 30 единиц продукции.

Разместим в ячейку A4B3 значение равное 30

Мы полностью удовлетворили потребность потребителя B3. Вычеркиваем столбец 3 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Наибольшей разностью обладает строка 3. В данной строке выберем ячейку A3B2, как обладающую наименьшим тарифом.

Стоимость доставки единицы продукции от поставщика A3 к потребителю B2, как минимум, на 2 ден.ед. меньше чем к другим потребителям.

Запасы поставщика A3 составляют 20 единиц продукции. Потребность потребителя B2 составляет 135 единиц продукции.

От поставщика A3 к потребителю B2 будем доставлять min = (20 , 135) = 20 единиц продукции.

Разместим в ячейку A3B2 значение равное 20

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

Запасы поставщика A5 составляют 115 единиц продукции. Потребность потребителя B2 составляет 115 единиц продукции. От поставщика A5 к потребителю B2 будем доставлять 115 единиц продукции.

Разместим в ячейку A5B2 значение равное 115

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

Заполненные нами ячейки будем называть базисными, остальные - свободными.

Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.

Количество базисных ячеек (задействованных маршрутов) равно 7, что и требовалось.

Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.= 1 * 120 + 1 * 110 + 4 * 20 + 2 * 40 + 3 * 30 + 0 * 65 + 0 * 115 = 480 ден. ед.

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

По результатам построения опорных планов минимальное значение затрат было получено при построении опорного плана методом наименьшей стоимости и составили 450 ден.ед.

Перейдем к перепланировке перевозок методом потенциалов.

.3     
Оптимизация транспортной модели закрытого типа

1.3.1 Метод потенциалов на основе опорного плана, построенного методом северо-западного угла

Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем:

• Находим потенциалы поставщиков и потребителей для имеющегося решения.

• Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена.

• Выбираем свободную ячейку (с отрицательной оценкой), выбор которой, позволяет максимально снизить общую стоимость доставки всей продукции на данном шаге решения.

• Находим новое решение, как минимум, не хуже предыдущего.

• Вычисляем общую стоимость доставки всей продукции для нового решения.

Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij - тариф клетки AiBj)

Поскольку, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем v2 = 0.

v2 + u2 = c22 v2 + u2 = 4 u2 = 4 - 0 = 4+ u3 = c32 v2 + u3 = 4 u3 = 4 - 0 = 4+ u4 = c42 v2 + u4 = 3 u4 = 3 - 0 = 3+ u5 = c52 v2 + u5 = 0 u5 = 0 - 0 = 0+ u5 = c53 v3 + u5 = 0 v3 = 0 - 0 = 0+ u2 = c21 v1 + u2 = 3 v1 = 3 - 4 = -1

v1 + u1 = c11 v1 + u1 = 1 u1 = 1 - ( -1 ) = 2

Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):

12 = c12 - ( u1 + v2 ) = 2 - ( 2 + 0 ) = 0

= c13 - ( u1 + v3 ) = 9 - ( 2 + 0 ) = 7

= c23 - ( u2 + v3 ) = 1 - ( 4 + 0 ) = -3

= c31 - ( u3 + v1 ) = 6 - ( 4 + ( -1 ) ) = 3

= c33 - ( u3 + v3 ) = 8 - ( 4 + 0 ) = 4

= c41 - ( u4 + v1 ) = 2 - ( 3 + ( -1 ) ) = 0

= c43 - ( u4 + v3 ) = 3 - ( 3 + 0 ) = 0

= c51 - ( u5 + v1 ) = 0 - ( 0 + ( -1 ) ) = 1

Оценка свободной ячейки A2B3 (незадействованного маршрута) отрицательная (∆23 =-3) , следовательно решение не является оптимальным.

Построим цикл для выбранной ячейки A2B3:

Ячейки образующие цикл для свободной ячейки A2B3:B3 , A2B2 , A5B2 , A5B3

Пусть ячейка A2B3, для которой мы строили цикл, имеет порядковый номер один.

Среди ячеек цикла A2B2 , A5B3 , номера которых четные, найдем ячейку, обладающую наименьшим значением.= (5, 140) = 5

В данном случае, это ячейка A2B2.

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

От ячеек цикла с четными номерами отнимает 5. К ячейкам с нечетными номерами прибавляем 5.

Мы вводим новый маршрут доставки продукции от поставщика A2 к потребителю B3. По данному маршруту доставим 5 единиц продукции, по цене доставки 1 за единицу продукции. Общие затраты увеличатся на 1 * 5 ден. ед.

По маршруту от поставщика A2 к потребителю B2 мы полностью перестаем доставлять продукцию.

Общие затраты уменьшатся на 4 * 5 ден. ед.

От поставщика A5 к потребителю B2 дополнительно поставим 5 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты увеличатся на 0 * 5 ден. ед.

Сократим поставку от поставщика A5 к потребителю B3 на 5 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты уменьшатся на 0 * 5 ден. ед.

Общие расходы на доставку продукции от поставщиков к потребителям изменятся на

* 5 - 4 * 5 + 0 * 5 - 0 * 5 = ( 1 - 4 + 0 - 0 ) * 5 = -3 * 5 ден. ед.

Выражение, стоящее в скобках, равно оценке свободной ячейки (незадействованного маршрута), для которой мы строили цикл.

Данные преобразования не изменят баланс между поставщиками и потребителями. Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.

Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 745 + ( - 15 ) = 730 ден. ед..

.3.2   Метод потенциала на основе опорного плана, построенного методом минимальной стоимости

Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij - тариф клетки AiBj)

Поскольку, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем v1 = 0.

v1 + u1 = c11 v1 + u1 = 1 u1 = 1 - 0 = 1+ u4 = c41 v1 + u4 = 2 u4 = 2 - 0 = 2+ u5 = c51 v1 + u5 = 0 u5 = 0 - 0 = 0+ u5 = c52 v2 + u5 = 0 v2 = 0 - 0 = 0+ u5 = c53 v3 + u5 = 0 v3 = 0 - 0 = 0+ u2 = c23 v3 + u2 = 1 u2 = 1 - 0 = 1+ u3 = c32 v2 + u3 = 4 u3 = 4 - 0 = 4

Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):

12 = c12 - ( u1 + v2 ) = 2 - ( 1 + 0 ) = 1

= c13 - ( u1 + v3 ) = 9 - ( 1 + 0 ) = 8

= c21 - ( u2 + v1 ) = 3 - ( 1 + 0 ) = 2

= c22 - ( u2 + v2 ) = 4 - ( 1 + 0 ) = 3

= c31 - ( u3 + v1 ) = 6 - ( 4 + 0 ) = 2

= c33 - ( u3 + v3 ) = 8 - ( 4 + 0 ) = 4

= c42 - ( u4 + v2 ) = 3 - ( 2 + 0 ) = 1

= c43 - ( u4 + v3 ) = 3 - ( 2 + 0 ) = 1

Все оценки свободных ячеек положительные, следовательно, найдено оптимальное решение.= 1 * 120 + 1 * 110 + 4 * 20 + 2 * 70 + 0 * 35 + 0 * 115 + 0 * 30 = 450

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

.3.3   Метод потенциалов на основе опорного плана, построенного методом Фогеля

Поскольку, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем v1 = 0.

v1 + u1 = c11 v1 + u1 = 1 u1 = 1 - 0 = 1+ u4 = c41 v1 + u4 = 2 u4 = 2 - 0 = 2+ u4 = c43 v3 + u4 = 3 v3 = 3 - 2 = 1+ u5 = c51 v1 + u5 = 0 u5 = 0 - 0 = 0+ u5 = c52 v2 + u5 = 0 v2 = 0 - 0 = 0+ u2 = c23 v3 + u2 = 1 u2 = 1 - 1 = 0

v2 + u3 = c32 v2 + u3 = 4 u3 = 4 - 0 = 4

Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):

12 = c12 - ( u1 + v2 ) = 2 - ( 1 + 0 ) = 1

= c13 - ( u1 + v3 ) = 9 - ( 1 + 1 ) = 7

= c21 - ( u2 + v1 ) = 3 - ( 0 + 0 ) = 3

= c22 - ( u2 + v2 ) = 4 - ( 0 + 0 ) = 4

= c31 - ( u3 + v1 ) = 6 - ( 4 + 0 ) = 2

= c33 - ( u3 + v3 ) = 8 - ( 4 + 1 ) = 3

= c42 - ( u4 + v2 ) = 3 - ( 2 + 0 ) = 1

= c53 - ( u5 + v3 ) = 0 - ( 0 + 1 ) = -1

Оценка свободной ячейки A5B3 (незадействованного маршрута) отрицательная (53 =-1) , следовательно решение не является оптимальным.

Построим цикл для выбранной ячейки A5B3:

Поставьте курсор мыши в выбранную свободную ячейку A5B3. Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку A5B3. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения.

Ячейки образующие цикл для свободной ячейки A5B3 :B3 , A5B1 , A4B1 , A4B3

Пусть ячейка A5B3, для которой мы строили цикл, имеет порядковый номер один.

Среди ячеек цикла A5B1 , A4B3 , номера которых четные, найдем ячейку, обладающую наименьшим значением.= ( 65, 30 ) = 30

В данном случае, это ячейка A4B3.

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

Мы вводим новый маршрут доставки продукции от поставщика A5 к потребителю B3. По данному маршруту доставим 30 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты увеличатся на 0 * 30 ден. ед.

Сократим поставку от поставщика A5 к потребителю B1 на 30 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты уменьшатся на 0 * 30 ден. ед.

От поставщика A4 к потребителю B1 дополнительно поставим 30 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты увеличатся на 2 * 30 ден. ед.

По маршруту от поставщика A4 к потребителю B3 мы полностью перестаем доставлять продукцию.

Общие затраты уменьшатся на 3 * 30 ден. ед.

Данные преобразования не изменят баланс между поставщиками и потребителями. Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.

Общие расходы на доставку продукции от поставщиков к потребителям изменятся на

* 30 - 0 * 30 + 2 * 30 - 3 * 30 = ( 0 - 0 + 2 - 3 ) * 30 = -1 * 30 ден. ед.

Выражение, стоящее в скобках, равно оценке свободной ячейки (незадействованного маршрута), для которой мы строили цикл.

Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 480 + ( - 30) = 450 ден. ед..

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

.       
Транспортная модель открытого типа

.1 Условия задачи

В соответствии с заданием на курсовую работу необходимо решить транспортную задачу. Первичный опорный план необходимо найти тремя способами: методом северо-западного угла, методом минимальной стоимости, методом Фогеля. Для каждого найденного опорного плана произвести перепланировку поставок методом потенциалов.

Исходные данные:

а1 =120

а2 =110

а4 = 70

b1 = 225= 100

b3 = 140

Решим поставленную задачу тремя способами: методом северо-западного угла, методом наименьшей стоимости и методом Фогеля.

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

.2.1 Построение опорного плана методом северо-западного угла

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

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

Маршруты доставки продукции от фиктивного поставщика A5 к потребителям мы будем рассматривать в последнюю очередь. Не факт, но, скорее всего, это позволит получить более рентабельное начальное решение.

Согласно условию задачи составим таблицу. (тарифы cij располагаются в нижнем правом углу ячейки)

При анализе методом северо-западного угла анализ начинаем с ячейки А1В1.

Рассмотрим маршрут доставки от поставщика A1 к потребителю B1 (ячейка A1B1).

Запасы поставщика A1 составляют 120 единиц продукции. Потребность потребителя B1 составляет 225 единиц продукции.

От поставщика A1 к потребителю B1 будем доставлять min = (120 , 225) = 120 единиц продукции.

Разместим в ячейку A1B1 значение равное 120

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

Рассмотрим маршрут доставки от поставщика A2 к потребителю B1 (ячейка A2B1).

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B1 составляет 105 единиц продукции.

От поставщика A2 к потребителю B1 будем доставлять min = (110 , 105) = 105 единиц продукции.

Разместим в ячейку A2B1 значение равное 105

Мы полностью удовлетворили потребность потребителя B1. Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Затем переходим к удовлетворению потребности поставщика В2 и так далее. В результате получим таблицу.

Затраты на перевозку составят:

S0 = 1*120+105*3+5*4+20*4+70*3+5*0+140*0 = 665 ден.ед.

2.2.2 Построение опорного плана методом минимальной стоимости

Минимальный элемент матрицы тарифов находится в ячейке A1B1 и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B1 наиболее рентабельный.

Запасы поставщика A1 составляют 120 единиц продукции. Потребность потребителя B1 составляет 225 единиц продукции.

От поставщика A1 к потребителю B1 будем доставлять min = (120 , 225) = 120 единиц продукции.

Разместим в ячейку A1B1 значение равное 120

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

Минимальный элемент матрицы тарифов находится в ячейке A2B3 и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B3 наиболее рентабельный.

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B3 составляет 140 единиц продукции. От поставщика A2 к потребителю B3 будем доставлять min = (110 , 140) = 110 единиц продукции.

Разместим в ячейку A2B3 значение равное 110

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

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

Заполненные нами ячейки будем называть базисными, остальные - свободными.

Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.

Количество базисных ячеек (задействованных маршрутов) равно 7, что и требовалось.

Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.= 1 * 120 + 1 * 110 + 4 * 20 + 2 * 70 + 0 * 35 + 0 * 80 + 0 * 30 = 450 ден. ед.

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

.2.3 Построение опорного плана методом Фогеля

В каждой строке, найдем разность i между двумя ячейками (доступными для выбора) с наименьшими тарифами.

Из полученных разностей выберем наибольшую.

Наибольшей разностью обладает столбец 3. В данном столбце выберем ячейку A2B3, как обладающую наименьшим тарифом.

Стоимость доставки единицы продукции от поставщика A2 к потребителю B3, как минимум, на 2 ден.ед. меньше чем от остальных поставщиков к потребителю B3.

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B3 составляет 140 единиц продукции. (см. таблицу пункта 1)

От поставщика A2 к потребителю B3 будем доставлять min = (110 , 140) = 110 единиц продукции.

Разместим в ячейку A2B3 значение равное 110

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

Затем по аналогии находим небольшую разность за исключением строки А2. Так до тех пор пока не удовлетворим потребности всех потребителей. В результате получим таблицу.

Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.= 1 * 120 + 1 * 110 + 4 * 20 + 2 * 40 + 3 * 30 + 0 * 65 + 0 * 80 = 480 ден. ед.

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

.3 Оптимизация транспортной модели открытого типа

.3.1 Метод потенциала на основе опорного плана, построенного методом северо-западного угла

Произведем оценку полученного решения методом северо-западногоугла.

Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij - тариф клетки AiBj)

Поскольку, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем v2 = 0.

v2 + u3 = c32 v2 + u3 = 4 u3 = 4 - 0 = 4+ u4 = c42 v2 + u4 = 3 u4 = 3 - 0 = 3+ u5 = c52 v2 + u5 = 0 u5 = 0 - 0 = 0+ u5 = c53 v3 + u5 = 0 v3 = 0 - 0 = 0+ u2 = c23 v3 + u2 = 1 u2 = 1 - 0 = 1+ u2 = c21 v1 + u2 = 3 v1 = 3 - 1 = 2

v1 + u1 = c11 v1 + u1 = 1 u1 = 1 - 2 = -1

Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):

12 = c12 - ( u1 + v2 ) = 2 - ( -1 + 0 ) = 3

= c13 - ( u1 + v3 ) = 9 - ( -1 + 0 ) = 10

= c22 - ( u2 + v2 ) = 4 - ( 1 + 0 ) = 3

= c31 - ( u3 + v1 ) = 6 - ( 4 + 2 ) = 0

= c33 - ( u3 + v3 ) = 8 - ( 4 + 0 ) = 4

= c41 - ( u4 + v1 ) = 2 - ( 3 + 2 ) = -3

= c43 - ( u4 + v3 ) = 3 - ( 3 + 0 ) = 0

= c51 - ( u5 + v1 ) = 0 - ( 0 + 2 ) = -2

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

Затраты на перевозку по данному плану составят:

S =120*1+110*1+20*4+70*3+105*0+10*0+30*0 = 520 ден.ед.

.3.1 Метод потенциала на основе опорного плана, построенного методом минимальной стоимости

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

Примем v1 = 0.

v1 + u1 = c11 v1 + u1 = 1 u1 = 1 - 0 = 1+ u4 = c41 v1 + u4 = 2 u4 = 2 - 0 = 2+ u5 = c51 v1 + u5 = 0 u5 = 0 - 0 = 0+ u5 = c52 v2 + u5 = 0 v2 = 0 - 0 = 0+ u5 = c53 v3 + u5 = 0 v3 = 0 - 0 = 0+ u2 = c23 v3 + u2 = 1 u2 = 1 - 0 = 1+ u3 = c32 v2 + u3 = 4 u3 = 4 - 0 = 4

12 = c12 - ( u1 + v2 ) = 2 - ( 1 + 0 ) = 1

= c13 - ( u1 + v3 ) = 9 - ( 1 + 0 ) = 8

= c21 - ( u2 + v1 ) = 3 - ( 1 + 0 ) = 2

= c22 - ( u2 + v2 ) = 4 - ( 1 + 0 ) = 3

= c31 - ( u3 + v1 ) = 6 - ( 4 + 0 ) = 2

33 = c33 - ( u3 + v3 ) = 8 - ( 4 + 0 ) = 4

= c42 - ( u4 + v2 ) = 3 - ( 2 + 0 ) = 1

= c43 - ( u4 + v3 ) = 3 - ( 2 + 0 ) = 1

Все оценки свободных ячеек имеют положительное значение. Следовательно найдено оптимальное решение.= 1 * 120 + 1 * 110 + 4 * 20 + 2 * 70 + 0 * 35 + 0 * 80 + 0 * 30 = 450

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

.3.1 Метод потенциала на основе опорного плана, построенного методом Фогеля

Произведем оценку решения методом потенциала.

Примем v1 = 0.

v1 + u1 = c11 v1 + u1 = 1 u1 = 1 - 0 = 1+ u4 = c41 v1 + u4 = 2 u4 = 2 - 0 = 2+ u5 = c51 v1 + u5 = 0 u5 = 0 - 0 = 0+ u5 = c52 v2 + u5 = 0 v2 = 0 - 0 = 0+ u5 = c53 v3 + u5 = 0 v3 = 0 - 0 = 0+ u2 = c23 v3 + u2 = 1 u2 = 1 - 0 = 1

v2 + u3 = c32 v2 + u3 = 4 u3 = 4 - 0 = 4

Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):

12 = c12 - ( u1 + v2 ) = 2 - ( 1 + 0 ) = 1

= c13 - ( u1 + v3 ) = 9 - ( 1 + 0 ) = 8

= c21 - ( u2 + v1 ) = 3 - ( 1 + 0 ) = 2

= c22 - ( u2 + v2 ) = 4 - ( 1 + 0 ) = 3

= c31 - ( u3 + v1 ) = 6 - ( 4 + 0 ) = 2

= c33 - ( u3 + v3 ) = 8 - ( 4 + 0 ) = 4

= c42 - ( u4 + v2 ) = 3 - ( 2 + 0 ) = 1

= c43 - ( u4 + v3 ) = 3 - ( 2 + 0 ) = 1

Все оценки свободных ячеек положительные, следовательно, найдено оптимальное решение.= 1 * 120 + 1 * 110 + 4 * 20 + 2 * 70 + 0 * 35 + 0 * 80 + 0 * 30 = 450

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

Заключение

В начале данной работы ставились следующие задачи:

построение опорных планов методами северо-западного угла, методом минимальной стоимости и методом Фогеля;

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

Поставленные задачи выполнены в полном объеме. Как показали проведенные расчеты метод минимальной стоимости дает более точные результаты уже при построении опорного плана, то же касается метода Фогеля. В то время как метод северо-западного угла требует неоднократной корректировки.

По результатам расчетов минимальные затраты на перевозку составят 450 ден. единиц.

Список использованных источников

. Шапкин А. С. Математические методы и модели исследования операций [Текст] : учебник / А. С. Шапкин, Н. П. Мазаева. - М. : Издательско-торговая корпорация «Дашков и Ко», 2004. - 400 с., С. 119 - 146.

. Кремер, Н. Ш. Исследование операций в экономике [Текст] : учебное пособие для вузов / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман; под ред. Н. Ш. Кремера. - М. : ЮНИТИ, 2003. - 407 с., С. 123 - 153.

. Кузнецов, Б. Т. Математические методы и модели исследования операций [Текст] : учебное пособие / Б. Т. Кузнецов. - М. : ЮНИТИ-ДАНА, 2005. - 390 с., С. 103 - 129.

. Хазанова, Л. Э. Математическое моделирование в экономике [Текст] : учебное пособие / Л. Э. Хазанова. - М. : Издательство БЕК, 1998. - 141 с., С. 45 - 76.