Методы оптимальных решений транспортной задачи

  • Вид работы:
    Контрольная работа
  • Предмет:
    Математика
  • Язык:
    Русский
    ,
    Формат файла:
    MS Word
    12,66 Кб
  • Опубликовано:
    2016-02-16
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

Методы оптимальных решений транспортной задачи















«Методы оптимальных решений»

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

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

Необходимо:

1)  свести исходные данные в таблицу 1.1.

Таблица 1.1

Строительный объект Склад

Запасы стройматериалов на складах, тыс.ед.

























Потребности строительных объектов, тыс.ед.         






2)  составить математическую модель задачи;

3)      привести её к стандартной транспортной задаче с балансом запасов и потребностей;

)        построить начальный опорный план задачи методом минимального элемента;

)        решить задачу методом потенциалов;

)        проанализировать полученные результаты.

Таблица 2

Строительный объект Склад

Запасы стройматериалов на складах, тыс.ед.






4836730







8465925







3585420







58106815







Потребности строительных объектов, тыс.ед.

10

20

18

12

25

90 85


2) составляем математическую модель задачи:

Ограничения по запасам:

математический задача транспортный


Ограничения по потребностям:


Целевая функция:


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

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на складах. Следовательно, модель исходной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную, фиктивную, потребность, равной 5 (90-85=5). Тарифы перевозки груза из склада во все объекты полагаем равной нулю. Занесем данные в таблицу:

Таблица 3

 

Запасы стройматериалов на складах, тыс.ед.







48367030








84659025








35854020








581068015








Потребности строительных объектов, тыс.ед.

10

20

18

12

25

5

90 90


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

Наименьшая стоимость = 3. Для этого элемента запасы равны 30, а потребности 18. Поскольку минимальным является 18, то вычитаем его:

Таблица 4

Строительный объект Склад          Запасы стройматериалов на складах,

тыс.ед.







 

48367030-18=12








84659025








35854020








581068015








Потребности строительных объектов, тыс.ед.

10

18-18=0

12

25

5

90 90


Наименьшая стоимость = 3. Для этого элемента запасы равны 20, а потребности 10. Поскольку минимальным является 10, то вычитаем его:

Таблица 5

Строительный объект Склад

Запасы стройматериалов на складах, тыс.ед.







48367012








84659025








35854020-10=10








581068015








Потребности строительных объектов, тыс.ед.

10-10=0

20

0

12

25

5

90 90


Наименьшая стоимость = 4. Для этого элемента запасы равны 25, а потребности 20. Поскольку минимальным является 20, то вычитаем его:

Таблица 6

Строительный объект Склад

Запасы стройматериалов на складах, тыс.ед.







48367012








84659025-20=5








35854010








581068015








Потребности строительных объектов, тыс.ед.

0

20-20=0

0

12

25

5

90 90


Таблица 7

Строительный объект Склад

Запасы стройматериалов на складах, тыс.ед.







48367012-7=5








8465900








3585400








581068015








Потребности строительных объектов, тыс.ед.

0

0

0

7-7=0

15

5

90 90


Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

Выбираем максимальную оценку свободной клетки с15=7

В эту клетку ставим знак +, а в остальных вершинах многоугольника чередующие знаки.

Таблица 9

Строительный объект Склад

 4 5 3 6 8 0Запасы стройматериалов на складах, тыс.ед.







 04(10)83(18)6(2)-7+030








 -184(20)65(5)9025








 -435854(20)020








 058106(5)+8(5)-0(5)15








Потребности строительных объектов, тыс.ед.

10

20

18

12

25

5

90 90


Таблица 10

Строительный объект Склад

 4 5 3 6 8 0Запасы стройматериалов на складах, тыс.ед.







 04(10)83(18)67(2)030








 -184(20)65(5)9025








 -435854(20)020








 058106(7)8(3)0(5)15








Потребности строительных объектов, тыс.ед.

10

20

18

12

25

5

90 90


Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

Потенциалы занесем в таблицу.

Проведем оценки свободных клеток:

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

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

6)

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

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

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

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

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

Похожие работы на - Методы оптимальных решений транспортной задачи

 

Не нашел материал для своей работы?
Поможем написать качественную работу
Без плагиата!