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

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

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

Комментарии:

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

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

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

Главная страница >> Контрольная работа >> Математика и статистика >> Методы оптимальных решений транспортной задачи

Дата добавления на сайт: 14 февраля 2025

Заказать курсовую работу

Заказать реферат и др.

Скачать данную работу

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

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

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

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

строительных объектов. Потребности строительных объектов в материалах равны Методы оптимальных решений транспортной задачи (рис. 3)

тыс.ед.,

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

. Запасы стройматериалов на складах составляют Методы оптимальных решений транспортной задачи (рис. 5)

тыс.ед. Затраты на перевозку 1тыс.ед. стройматериалов в ден.ед представлены матрицей затрат Методы оптимальных решений транспортной задачи (рис. 6)

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

. Запланировать перевозку с минимальными затратами при заданном дополнительном условии.
Необходимо:
1)свести исходные данные в таблицу 1.1.

Таблица 1.1

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

Потребности строительных объектов, тыс.ед. Методы оптимальных решений транспортной задачи (рис. 7)

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

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

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

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

2)составить математическую модель задачи;
3)привести её к стандартной транспортной задаче с балансом запасов и потребностей;
)построить начальный опорный план задачи методом минимального элемента;
)решить задачу методом потенциалов;
)проанализировать полученные результаты.
Таблица 2

2) составляем математическую модель задачи:
Ограничения по запасам:
математический задача транспортный
Методы оптимальных решений транспортной задачи (рис. 12)

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

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

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

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

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

3) Проверим необходимое и достаточное условие разрешимости задачи:
Методы оптимальных решений транспортной задачи (рис. 15)

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

Таблица 3

	Запасы стройматериалов на складах, тыс.ед.
48367030
84659025
35854020
581068015
Потребности строительных объектов, тыс.ед.	10	20	18	12	25	5	90 90

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

Таблица 4
Строительный объект Склад Методы оптимальных решений транспортной задачи (рис. 16)

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

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

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

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

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

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

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

тыс.ед.
48367030-18=12
84659025
35854020
581068015
Потребности строительных объектов, тыс.ед.	10	20	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

Из грузов сij стоящих в минусовых клетках, выбираем наименьшее, т.е. у=min(2,5)=2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из сij, стоящих в минусовых клетках. В результате получим новый опорный план:

Таблица 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.

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

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

Потенциалы занесем в таблицу.
Проведем оценки свободных клеток:
Методы оптимальных решений транспортной задачи (рис. 23)

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

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Минимальные затраты составят:
Методы оптимальных решений транспортной задачи (рис. 25)

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

6)
Из 1-го склада необходимо груз направить в 1-й объект (10), в 3-й объект (18), в 5-й объект (2)
Из 2-го склада необходимо груз направить в 2-й объект (20), в 4-й объект (5)
Из 3-го склада необходимо весь груз направить в 5-й объект
Из 4-го склада необходимо груз направить в 4-й объект (7), в 5-й объект (3)
На 4-ом складе остался невостребованным груз в количестве 5 ед.

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

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

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