Размещено на http://www.allbest.ru/

2

Министерство транспорта Российской Федерации

Федеральное агентство железнодорожного транспорта

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

"Дальневосточный государственный университет путей сообщения"

Кафедра "Прикладная математика"

Курсовая работа

Методы принятия управленческих решений для перевозки грузов из пунктов отправления в пункты потребления

Выполнила: студентка группы Ц16

направления 080200

специальности 080200.62

"Менеджмент", Гриднева Ю.И.

Проверил:

Кадура Е.В.

Хабаровск, 2014



Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Список используемых источников



Введение

Одна из наиболее распространённых задач математического программирования -- транспортная задача. Транспортная задача -- математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки.

Транспортная задача (классическая) -- задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

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

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

Ограничения транспортной задачи:

1. Весь груз от -го поставщика должен быть выведен полностью



2. Ограничения по спросу

-й потребитель должен быть полностью обеспечен грузом.

3. Суммарное предложение равно суммарному спросу.

4. Условие неотрицательных поставок

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



Каноническая задача линейного программирования

Условие 1.3 называется балансовым, а транспортная задача с этим условием - сбалансированной или задачей закрытого типа. Если ,то транспортная задача называется несьалансированной или задачей открытого типа.

Матрицей транспортных расходов(издержек) называется матрица вида:

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

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

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



Особенности транспортной задачи

1. Система ограничений системы линейных уравнений

2. Коэффициенты при переменных в системе линейных уравнений равны 1 или 0

3. Каждая переменная входит в систему ограничений дважды: один раз в систему ограничений по предложению (1.1); второй раз в систему ограничений по спросу (1.2)

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

5. Единицы измерений всех переменных одинаковы

6. Весь перевозимый груз должен быть однородным

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

Методы нахождения опорных планов для транспортной задачи:

· Метод северо-западного цикла

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

· Метод Фогеля

Метод северо-западного цикла

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

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

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

Алгоритм:

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

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

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

Метод Фогеля

1. В каждой строке находим клетку с минимальной транспортной издержкой и ближайшей к ней транспортной издержкой.

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

3. В столбце находим клетку с минимальной транспортной издержкой и ближайшей минимальной транспортной издержкой. Находим их разность и записываем её внизу таблицы(для каждого столбца своя разность)

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

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

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

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

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

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

Вырожденность опорного плана имеет значение для его оптимизации

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

Транспортная задача решается в 2 этапа:

1. Построение опорного плана (невырожденного)

2. Оптимизация опорного плана (медот потенциалов)

Алгоритм метода потенциалов:

1. Рассчитать начальный план перевозоки и выделить базисные клетки. Вычислить значение целевой функции.

2. Проверить опорный план на вырожденность. Если опорный план невырожденный, то применяем метод потенциала.

3. Рассчитать значения потенциалов. Положить . Остальные потенциалы рассчитать с помощью базисных клеток, исходя из уравнения

4. Для свободных клеток рассчитать оценки

.

Если все , тонайдено оптимальное решение.

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

Перепланировка опорного плана:

1. Выбираем клетку с минимальной разностью, если минимальный разностей несколько, то выбираем любую из них.

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

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

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

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

6. Пересчитать целевую функцию.



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

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

Дано поставщиков , предложение каждого -го поставщика составляет единиц, .

Дано потребителей спрос каждого -го потребителя составляет единиц, .

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

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

Обозначим - количество груза, перевозимое от -го поставщика к -му потребителю. Тогда общая стоимость перевозок равна:

Матрица транспортных расходов имеет вид:

Матрица перевозок (план перевозок) имеет вид:



Представлю исходные данные транспортной задачи в виде таблицы 1

Таблица 1

Исходные данные транспортной задачи

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

Проверим необходимое и достаточное условие разрешимости задачи:

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

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

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

План начинается заполняться с верхнего левого угла. В ячейку 11 делаю поставку 95, затем закрываю 1 столбец, т.к. потребности полностью удовлетворены. (Таблица 2)

Таблица 2

Выбираю ячейку 12 и делаю поставку 10, закрываю 1 строку, т.к. предложение исчерпано. (Таблица 3)

Таблица 3

Выбираю ячейку 22 и делаю поставку 70, закрываю 2 строку, т.к. предложение полностью исчерпано (Таблица 4)

Таблица 4

Выбираю ячейку 32 и делаю поставку 80, закрываю 2 столбец, т.к. потребности полностью удовлетворены. (Таблица 5)

Таблица 5

Выбираю ячейку 33 и делаю поставку 135, закрываю 3 столбец, т.к. потребности полностью удовлетворены. (Таблица 6)

Таблица 6

Выбираю ячейку 34 и делаю поставку 25. Затем делаю поставку 85 в ячейку 44.(Таблица 7)

Таблица 7



Матрица перевозок:

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

Значение целевой функции для этого опорного плана равно:

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

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

Выбираю ячейку 21, т.к. данная ячейка содержит наименьшую транспортную издержку 6, и делаю поставку 70. Затем закрываю 2 строку, т.к. предложение полностью исчерпано. (Таблица 8)

Таблица 8

Выбираю ячейку 44 с наименьшей транспортной издержкой 7 и делаю поставку 85. Затем закрываю 4 строку, т.к. предложение полностью исчерпано. (Таблица 9)

Таблица 9

Выбираю ячейку 31 с наименьшей транспортной издержкой 10 и делаю поставку 25. Закрываю 1 столбец, т.к. потребности полностью удовлетворены. (Таблица 10)

Таблица 10

Выбираю ячейку 12 с наименьшей издержкой 12 и делаю поставку 105. Закрываю 1 строку, т.к. предложение полностью исчерпано. (Таблица 11)

Таблица 11

Выбираю ячейку 32 с наименьшей издержкой 19 и делаю поставку 55. Выбираю ячейку 33 с наименьшей издержкой 22 и делаю поставку 135. Делаю поставку 25 в ячейку 34. (Таблица 12)

Таблица 12

Матрица перевозок:

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

Значение целевой функции для этого опорного плана равно:

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

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

Нахожу разности по строкам:

1 строка: минимальная издержка 12, ближайшая к ней 17.

2 строка: минимальная издежка 6, ближайшая к ней 11.

транспортный перевозка план стоимость

3 строка: минимальная издежка 10, ближайшая к ней 19.

4 строка: минимальная издежка 7, ближайшая к ней 14.

Нахожу разности по столбцам:

1 столбец: минимальная издержка 6, ближайшая к ней 10.

2 столбец: минимальная издержка 11, ближайшая к ней 12

3 столбец: минимальная издержка 17, ближайшая к ней 20.

4 столбец: минимальная издержка 7, ближайшая к ней 21.

14 - максимальная разность, поэтому выбираю 4 столбец и делаю поставку 85 в ячейку 44 с минимальной издержкой 7. Закрываю 4 строку, т.к. предложение исчерпано. (Таблица 13)

Таблица 13

Нахожу разности по строкам:

1 строка: минимальная издержка 12, ближайшая к ней 17.

2 строка: минимальная издежка 6, ближайшая к ней 11.

3 строка: минимальная издежка 10, ближайшая к ней 19.

Нахожу разности по столбцам:

1 столбец: минимальная издержка 6, ближайшая к ней 10.

2 столбец: минимальная издержка 11, ближайшая к ней 12

3 столбец: минимальная издержка 17, ближайшая к ней 20.

4 столбец: минимальная издержка 21, ближайшая к ней 27.

9 - максимальная разность, поэтому выбираю 3 строку и делаю поставку 95 в ячейку 31 с минимальной издержкой 10. Закрываю 1 столбец, т.к. потребности полностью удовлетворены. (Таблица 14)

Таблица 14

Нахожу разности по строкам:

1 строка: минимальная издержка 12, ближайшая к ней 17.

2 строка: минимальная издежка 11, ближайшая к ней 20.

3 строка: минимальная издежка 19, ближайшая к ней 22.

Нахожу разности по столбцам:

2 столбец: минимальная издержка 11, ближайшая к ней 12

3 столбец: минимальная издержка 17, ближайшая к ней 20.

4 столбец: минимальная издержка 21, ближайшая к ней 27.

9 - максимальная разность, поэтому выбираю 2 строку и делаю поставку 70 в ячейку 22 с минимальной издержкой 11. Закрываю 2 строку, т.к. предложение исчерпано. (Таблица 15)

Таблица 15

Нахожу разности по строкам:

1 строка: минимальная издержка 12, ближайшая к ней 17.

3 строка: минимальная издежка 19, ближайшая к ней 22.

Нахожу разности по столбцам:

2 столбец: минимальная издержка 12, ближайшая к ней 19

3 столбец: минимальная издержка 17, ближайшая к ней 22.

4 столбец: минимальная издержка 21, ближайшая к ней 27.

7 - максимальная разность, поэтому выбираю 2 столбец и делаю поставку 90 в ячейку 12 с минимальной издержкой 12. Закрываю 2 столбец, т.к. потребности удовлетворены. (Таблица 16)



Таблица 16

Нахожу разности по строкам:

1 строка: минимальная издержка 17, ближайшая к ней 21.

3 строка: минимальная издежка 22, ближайшая к ней 27.

Нахожу разности по столбцам:

3 столбец: минимальная издержка 17, ближайшая к ней 22.

4 столбец: минимальная издержка 21, ближайшая к ней 27.

6 - максимальная разность, поэтому выбираю 4 столбец и делаю поставку 15 в ячейку 14 с минимальной издержкой 21. Закрываю 1 строку, т.к. предложение исчерпано. (Таблица 17)

Таблица 17

Выбираю ячейку 33 с минимальной транспортной издержкой 22 и делаю поставку 135. В ячейку с издержкой 27 делаю поставку 10. (Таблица 18)

Таблица 18

Матрица перевозок:

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

Значение целевой функции для этого опорного плана равно:

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

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

Проверю опорный план (таблица 19) на вырожденность: всего заполненных клеток:

,

имею заполненных клеток: 7, тогда опорный план невырожденный. Поэтому применяю метод потенциалов.

Таблица 19

Проверю оптимальность опорного плана. Найду предварительные потенциалы по занятым клеткам таблицы, в которых , полагая, что .(Таблица 20)



Таблица 20

Работаю с пустыми клетками (Таблица 21):

Таблица 21

Так как существуют , то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 31 с минимальной разностью -14. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак "+". Знаки остальных вершин чередуются. (Таблица 22)

Таблица 22

Среди отрицательных вершин выбираю наименьшую поставку 80. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 23)

Таблица 23

Значение целевой функции для этого опорного плана равно:

,

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

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

Таблица 24

Работаю с пустыми клетками (Таблица 25):



Таблица 25

Так как существуют , то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 14 с минимальной разностью -13. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак "+". Знаки остальных вершин чередуются. (Таблица 26)

Таблица 26

Среди отрицательных вершин выбираю наименьшую поставку 15. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 27)



Таблица 27

Значение целевой функции для этого опорного плана равно:

,

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

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

Таблица 28

Работаю с пустыми клетками (Таблица 29):

Таблица 29

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

Минимальные затраты составят: .

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

Таблица 30

Проверю опорный план (таблица 30) на вырожденность: всего заполненных клеток:

,

имею заполненных клеток: 7, тогда опорный план невырожденный. Поэтому применяю метод потенциалов.

Проверю оптимальность опорного плана. Найду предварительные потенциалы по занятым клеткам таблицы, в которых , полагая, что .(Таблица 31)

Таблица 31

Работаю с пустыми клетками (Таблица 32):

Таблица 32

Так как существуют , то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 22 с минимальной разностью -4. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак "+". Знаки остальных вершин чередуются. (Таблица 33)

Таблица 33

Среди отрицательных вершин выбираю наименьшую поставку 55. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 34)

Таблица 34

Значение целевой функции для этого опорного плана равно:

,

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

Проверю оптимальность опорного плана. Найду предварительные потенциалы по занятым клеткам таблицы, в которых , полагая, что .(Таблица 35)



Таблица 35

Работаю с пустыми клетками (Таблица 36):

Таблица 36

Так как существуют , то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 14 с минимальной разностью -3. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак "+". Знаки остальных вершин чередуются. (Таблица 37)

Таблица 37

Среди отрицательных вершин выбираю наименьшую поставку 15. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 38)

Таблица 38

Значение целевой функции для этого опорного плана равно:

,

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

Проверю оптимальность опорного плана. Найду предварительные потенциалы по занятым клеткам таблицы, в которых , полагая, что . (Таблица 39)

Таблица 39

Работаю с пустыми клетками (Таблица 40):

Таблица 40

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

Минимальные затраты составят: .

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

Таблица 41

Проверю опорный план (таблица 41) на вырожденность: всего заполненных клеток:

,

имею заполненных клеток: 7, тогда опорный план невырожденный. Поэтому применяю метод потенциалов.

Проверю оптимальность опорного плана. Найду предварительные потенциалы по занятым клеткам таблицы, в которых , полагая, что . (Таблица 42)

Таблица 42

Работаю с пустыми клетками (Таблица 43):

Таблица 43

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

Минимальные затраты составят: .



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

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

Дано поставщиков , предложение каждого -го поставщика составляет единиц, .

Дано потребителей спрос каждого -го потребителя составляет единиц, .

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

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

Обозначим - количество груза, перевозимое от -го поставщика к -му потребителю. Тогда общая стоимость перевозок равна:

Матрица транспортных расходов имеет вид:

Матрица перевозок (план перевозок) имеет вид:



Представлю исходные данные транспортной задачи в виде таблицы 44

Таблица 44

Исходные данные транспортной задачи

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

Проверим необходимое и достаточное условие разрешимости задачи:

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем фиктивного потребителя с предложением, равным 25. Издержки полагаем равными нулю.

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

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

План начинается заполняться с верхнего левого угла. В ячейку 11 делаю поставку 95, затем закрываю 1 столбец, т.к. потребности полностью удовлетворены. (Таблица 45)

Таблица 45

Выбираю ячейку 12 и делаю поставку 10, закрываю 1 строку, т. к. предложение исчерпано. (Таблица 46)

Таблица 46

Выбираю ячейку 22 и делаю поставку 70, закрываю 2 строку, т.к. предложение полностью исчерпано (Таблица 47)



Таблица 47

Выбираю ячейку 32 и делаю поставку 55, закрываю 2 столбец, т.к. потребности полностью удовлетворены. (Таблица 48)

Таблица48

Выбираю ячейку 33 и делаю поставку 135, закрываю 3 столбец, т.к. потребности полностью удовлетворены. (Таблица 49)

Таблица49

Выбираю ячейку 34 и делаю поставку 50, закрываю 3 строку, т. к. предложение исчерпано. (Таблица 49)

Таблица 49

Выбираю ячейку 44 и делаю поставку 60. Делаю поставку 25 в ячейку 45. (Таблица 49)

Таблица 50

Матрица перевозок:

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

Значение целевой функции для этого опорного плана равно:

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

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

Выбираю ячейку 21, т. к. данная ячейка содержит наименьшую транспортную издержку 6, и делаю поставку 70. Затем закрываю 2 строку, т.к. предложение полностью исчерпано. (Таблица 50)

Таблица 50

Выбираю ячейку 44, т. к. данная ячейка содержит наименьшую транспортную издержку 7, и делаю поставку 85. Затем закрываю 4 строку, т. к. предложение полностью исчерпано. (Таблица 51)

Таблица 51

Выбираю ячейку 31, т. к. данная ячейка содержит наименьшую транспортную издержку 10, и делаю поставку 25. Затем закрываю 1 столбец, т.к. потребности полностью удовлетворены. (Таблица 52)

Таблица 52

Выбираю ячейку 12, т. к. данная ячейка содержит наименьшую транспортную издержку 12, и делаю поставку 105. Затем закрываю 1 строку, т. к. предложение полностью исчерпано. (Таблица 53)

Таблица 53

Выбираю ячейку 32, т. к. данная ячейка содержит наименьшую транспортную издержку 19, и делаю поставку 30. Затем закрываю 2 столбец, , т.к. потребности полностью удовлетворены. (Таблица 54)



Таблица 54

Выбираю ячейку 33, т. к. данная ячейка содержит наименьшую транспортную издержку 22, и делаю поставку 135. Затем закрываю 3 столбец, т.к. потребности полностью удовлетворены. (Таблица 55)

Таблица 55

Выбираю ячейку 34, т. к. данная ячейка содержит наименьшую транспортную издержку 27, и делаю поставку 25. Делаю поставку 25 ячейку 35. (Таблица 56)

Таблица 56

Матрица перевозок:

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

Значение целевой функции для этого опорного плана равно:

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

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

Нахожу разности по строкам:

1 строка: минимальная издержка 12, ближайшая к ней 17.

2 строка: минимальная издежка 6, ближайшая к ней 11.

3 строка: минимальная издежка 10, ближайшая к ней 19.

4 строка: минимальная издежка 7, ближайшая к ней 14.

Нахожу разности по столбцам:

1 столбец: минимальная издержка 6, ближайшая к ней 10.

2 столбец: минимальная издержка 11, ближайшая к ней 12

3 столбец: минимальная издержка 17, ближайшая к ней 20.

4 столбец: минимальная издержка 7, ближайшая к ней 21.

14 - максимальная разность, поэтому выбираю 4 столбец и делаю поставку 85 в ячейку 44 с минимальной издержкой 7. Закрываю 4 строку, т.к. предложение исчерпано. (Таблица 57)



Таблица 57

Нахожу разности по строкам:

1 строка: минимальная издержка 12, ближайшая к ней 17.

2 строка: минимальная издежка 6, ближайшая к ней 11.

3 строка: минимальная издежка 10, ближайшая к ней 19.

Нахожу разности по столбцам:

1 столбец: минимальная издержка 6, ближайшая к ней 10.

2 столбец: минимальная издержка 11, ближайшая к ней 12

3 столбец: минимальная издержка 17, ближайшая к ней 20.

4 столбец: минимальная издержка 21, ближайшая к ней 27.

9 - максимальная разность, поэтому выбираю 3 строку и делаю поставку 95 в ячейку 31 с минимальной издержкой 10. Закрываю 1 столбец, т.к. потребности полностью удовлетворены. (Таблица 58)

Таблица 58

Нахожу разности по строкам:

1 строка: минимальная издержка 12, ближайшая к ней 17.

2 строка: минимальная издежка 11, ближайшая к ней 20.

3 строка: минимальная издежка 19, ближайшая к ней 22.

Нахожу разности по столбцам:

2 столбец: минимальная издержка 11, ближайшая к ней 12

3 столбец: минимальная издержка 17, ближайшая к ней 20.

4 столбец: минимальная издержка 21, ближайшая к ней 27.

9 - максимальная разность, поэтому выбираю 2 строку и делаю поставку 70 в ячейку 22 с минимальной издержкой 11. Закрываю 2 строку, т.к. предложение исчерпано. (Таблица 59)

Таблица 59

Нахожу разности по строкам:

1 строка: минимальная издержка 12, ближайшая к ней 17.



3 строка: минимальная издежка 19, ближайшая к ней 22.

Нахожу разности по столбцам:

2 столбец: минимальная издержка 12, ближайшая к ней 19

3 столбец: минимальная издержка 17, ближайшая к ней 22.

4 столбец: минимальная издержка 21, ближайшая к ней 27.

7 - максимальная разность, поэтому выбираю 2 столбец и делаю поставку 65 в ячейку 12 с минимальной издержкой 12. Закрываю 2 столбец, т.к. потребности удовлетворены. (Таблица 60)



Таблица 60

Нахожу разности по строкам:

1 строка: минимальная издержка 17, ближайшая к ней 21.

3 строка: минимальная издежка 22, ближайшая к ней 27.

Нахожу разности по столбцам:

3 столбец: минимальная издержка 17, ближайшая к ней 22

4 столбец: минимальная издержка 21, ближайшая к ней 27.



6 - максимальная разность, поэтому выбираю 4 столбец и делаю поставку 25 в ячейку 14 с минимальной издержкой 21. Закрываю 4 столбец, т.к. потребности удовлетворены. (Таблица 61)

Таблица 61

Выбираю ячейку 13 с минимальной транспортной издержкой 17 и делаю поставку 15. В ячейку с издержкой 22 делаю поставку 120 и в ячейку 35 делаю поставку 25. (Таблица 62)

Таблица 62

Матрица перевозок:

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

Значение целевой функции для этого опорного плана равно:

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

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

Проверю опорный план (таблица 63) на вырожденность: всего заполненных клеток:

имею заполненных клеток: 8, тогда опорный план невырожденный. Поэтому применяю метод потенциалов.

Таблица 63

Проверю оптимальность опорного плана. Найду предварительные потенциалы и по занятым клеткам таблицы, в которых , полагая, что.(Таблица 64)

Таблица 64

Работаю с пустыми клетками (Таблица 65)



Таблица 65

Так как существуют ?C_ij<0, то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 35 с минимальной разностью -20. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак "+". Знаки остальных вершин чередуются. (Таблица 66)

Таблица 66

Среди отрицательных вершин выбираю наименьшую поставку 25. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 67)



Таблица 67

S1 (8290 )>S2, из этого следует, что оптимизация прошла успешно

Проверю оптимальность опорного плана. (Таблица 68)

Таблица 68

Работаю с пустыми клетками (Таблица 69)



Таблица 69

Так как существуют ?C_ij<0, то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 31 с минимальной разностью -14. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак "+". Знаки остальных вершин чередуются. Среди отрицательных вершин выбираю наименьшую поставку 55. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 70)



Таблица 70

S2 (7790 )>S3, из этого следует, что оптимизация прошла успешно

Проверю оптимальность опорного плана. (Таблица 71)

Таблица 71

Работаю с пустыми клетками (Таблица 72)

Таблица 72

Так как существуют ?C_ij<0, то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 14 с минимальной разностью -13. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак "+". Знаки остальных вершин чередуются. Среди отрицательных вершин выбираю наименьшую поставку 25. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 73)



Таблица 73

S3 (7020 )>S4, из этого следует, что оптимизация прошла успешно

Проверю оптимальность опорного плана. (Таблица 74)

Таблица 74



Работаю с пустыми клетками (Таблица 75)

Таблица 75

Так как существуют ?C_ij<0, то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 13 с минимальной разностью -12. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак "+". Знаки остальных вершин чередуются. Среди отрицательных вершин выбираю наименьшую поставку 25. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 76)

Таблица 76

Проверю оптимальность опорного плана. (Таблица 77)

Таблица 77

Работаю с пустыми клетками (Таблица 78)

Таблица 78

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

Минимальные затраты составят: 6515 у.е.

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

Проверю опорный план (таблица 79) на вырожденность: всего заполненных клеток:

имею заполненных клеток: 8, тогда опорный план невырожденный. Поэтому применяю метод потенциалов.

Таблица 79

Проверю оптимальность опорного плана. (Таблица 80)

Таблица 80

Работаю с пустыми клетками (Таблица 81)

Таблица 81

Так как существуют ?C_ij<0, то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 22 с минимальной разностью -4. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак "+". Знаки остальных вершин чередуются. Среди отрицательных вершин выбираю наименьшую поставку 30. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 82)



Таблица 82

S1 (6740 )>S2, из этого следует, что оптимизация прошла успешно

Проверю оптимальность опорного плана. (Таблица 83)

Таблица 83

Работаю с пустыми клетками. (Таблица 84)

Таблица 84

Так как существуют ?C_ij<0, то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 14 с минимальной разностью -3. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак "+". Знаки остальных вершин чередуются. Среди отрицательных вершин выбираю наименьшую поставку 25. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 85)



Таблица 85

S2 (6620 )>S3, из этого следует, что оптимизация прошла успешно

Проверю оптимальность опорного плана. (Таблица 85)

Таблица 85

Работаю с пустыми клетками. (Таблица 86)

Таблица 86

Так как существуют ?C_ij<0, то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 13 с минимальной разностью -2. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак "+". Знаки остальных вершин чередуются. Среди отрицательных вершин выбираю наименьшую поставку 30. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 87)



Таблица 87

Проверю оптимальность опорного плана. (Таблица 88)

Таблица 88

Работаю с пустыми клетками. (Таблица 89)

Таблица 89

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

Минимальные затраты составят:

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

Проверю опорный план (таблица 90) на вырожденность: всего заполненных клеток:

имею заполненных клеток: 8, тогда опорный план невырожденный. Поэтому применяю метод потенциалов.

Таблица 90

Проверю оптимальность опорного плана. (Таблица 91)

Таблица 91

Работаю с пустыми клетками. (Таблица 92)

Таблица 92

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

Минимальные затраты составят:



Заключение

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

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 2-й магазин (90), в 4-й магазин (15)

Из 2-го склада необходимо весь груз направить в 2-й магазин

Из 3-го склада необходимо груз направить в 1-й магазин (95), в 3-й магазин (135), в 4-й магазин (10)

Из 4-го склада необходимо весь груз направить в 4-й магазин

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

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 2-й магазин (65), в 3-й магазин (15), в 4-й магазин (25)

Из 2-го склада необходимо весь груз направить в 2-й магазин

Из 3-го склада необходимо груз направить в 1-й магазин (95), в 3-й магазин (120)

Из 4-го склада необходимо весь груз направить в 4-й магазин

На 3-ом складе остался невостребованным груз в количестве 25 ед.

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



Список используемых источников

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

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

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

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

Размещено на Allbest.ru