Методы оптимальных решений транспортной задачи
Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.
| Рубрика | Математика |
| Вид | задача |
| Язык | русский |
| Дата добавления | 16.02.2016 |
| Размер файла | 58,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
«Методы оптимальных решений»
1. Транспортная задача
Стройматериалы с складов поставляются на строительных объектов. Потребности строительных объектов в материалах равны тыс.ед., . Запасы стройматериалов на складах составляют тыс.ед. Затраты на перевозку 1тыс.ед. стройматериалов в ден.ед представлены матрицей затрат . Запланировать перевозку с минимальными затратами при заданном дополнительном условии.
Необходимо:
1) свести исходные данные в таблицу 1.1.
Таблица 1.1
|
Строительный объект Склад |
Запасы стройматериалов на складах, тыс.ед. |
|||||
|
Потребности строительных объектов, тыс.ед. |
2) составить математическую модель задачи;
3) привести её к стандартной транспортной задаче с балансом запасов и потребностей;
4) построить начальный опорный план задачи методом минимального элемента;
5) решить задачу методом потенциалов;
6) проанализировать полученные результаты.
Таблица 2
|
Строительный объект Склад |
Запасы стройматериалов на складах, тыс.ед. |
||||||
|
4 |
8 |
3 |
6 |
7 |
30 |
||
|
8 |
4 |
6 |
5 |
9 |
25 |
||
|
3 |
5 |
8 |
5 |
4 |
20 |
||
|
5 |
8 |
10 |
6 |
8 |
15 |
||
|
Потребности строительных объектов, тыс.ед. |
10 |
20 |
18 |
12 |
25 |
90 85 |
2) составляем математическую модель задачи:
Ограничения по запасам:
математический задача транспортный
Ограничения по потребностям:
Целевая функция:
3) Проверим необходимое и достаточное условие разрешимости задачи:
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на складах. Следовательно, модель исходной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную, фиктивную, потребность, равной 5 (90-85=5). Тарифы перевозки груза из склада во все объекты полагаем равной нулю. Занесем данные в таблицу:
Таблица 3
|
Запасы стройматериалов на складах, тыс.ед. |
||||||||
|
4 |
8 |
3 |
6 |
7 |
0 |
30 |
||
|
8 |
4 |
6 |
5 |
9 |
0 |
25 |
||
|
3 |
5 |
8 |
5 |
4 |
0 |
20 |
||
|
5 |
8 |
10 |
6 |
8 |
0 |
15 |
||
|
Потребности строительных объектов, тыс.ед. |
10 |
20 |
18 |
12 |
25 |
5 |
90 90 |
4) Используя метод наименьшей стоимости, построим первый опорный план задачи.
Наименьшая стоимость = 3. Для этого элемента запасы равны 30, а потребности 18. Поскольку минимальным является 18, то вычитаем его:
Таблица 4
|
Строительный объект Склад |
Запасы стройматериалов на складах, тыс.ед. |
|||||||
|
4 |
8 |
3 |
6 |
7 |
0 |
30-18=12 |
||
|
8 |
4 |
|
5 |
9 |
0 |
25 |
||
|
3 |
5 |
|
5 |
4 |
0 |
20 |
||
|
5 |
8 |
|
6 |
8 |
0 |
15 |
||
|
Потребности строительных объектов, тыс.ед. |
10 |
20 |
18-18=0 |
12 |
25 |
5 |
90 90 |
Наименьшая стоимость = 3. Для этого элемента запасы равны 20, а потребности 10. Поскольку минимальным является 10, то вычитаем его:
Таблица 5
|
Строительный объект Склад |
Запасы стройматериалов на складах, тыс.ед. |
|||||||
|
|
8 |
3 |
6 |
7 |
0 |
12 |
||
|
|
4 |
|
5 |
9 |
0 |
25 |
||
|
3 |
5 |
|
5 |
4 |
0 |
20-10=10 |
||
|
|
8 |
|
6 |
8 |
0 |
15 |
||
|
Потребности строительных объектов, тыс.ед. |
10-10=0 |
20 |
0 |
12 |
25 |
5 |
90 90 |
Наименьшая стоимость = 4. Для этого элемента запасы равны 25, а потребности 20. Поскольку минимальным является 20, то вычитаем его:
Таблица 6
|
Строительный объект Склад |
Запасы стройматериалов на складах, тыс.ед. |
|||||||
|
|
|
3 |
6 |
7 |
0 |
12 |
||
|
|
4 |
|
5 |
9 |
0 |
25-20=5 |
||
|
3 |
|
|
5 |
4 |
0 |
10 |
||
|
|
|
|
6 |
8 |
0 |
15 |
||
|
Потребности строительных объектов, тыс.ед. |
0 |
20-20=0 |
0 |
12 |
25 |
5 |
90 90 |
Таблица 7
|
Строительный объект Склад |
Запасы стройматериалов на складах, тыс.ед. |
|||||||
|
4 |
8 |
3 |
6 |
7 |
0 |
12-7=5 |
||
|
8 |
4 |
6 |
5 |
9 |
0 |
0 |
||
|
3 |
5 |
8 |
5 |
4 |
0 |
0 |
||
|
5 |
8 |
10 |
6 |
8 |
0 |
15 |
||
|
Потребности строительных объектов, тыс.ед. |
0 |
0 |
0 |
7-7=0 |
15 |
5 |
90 90 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
Выбираем максимальную оценку свободной клетки с15=7
В эту клетку ставим знак +, а в остальных вершинах многоугольника чередующие знаки.
Таблица 9
|
Строительный объект Склад |
4 |
5 |
3 |
6 |
8 |
0 |
Запасы стройматериалов на складах, тыс.ед. |
|
|
0 |
4(10) |
8 |
3(18) |
6(2)- |
7+ |
0 |
30 |
|
|
-1 |
8 |
4(20) |
6 |
5(5) |
9 |
0 |
25 |
|
|
-4 |
3 |
5 |
8 |
5 |
4(20) |
0 |
20 |
|
|
0 |
5 |
8 |
10 |
6(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 |
Запасы стройматериалов на складах, тыс.ед. |
|
|
0 |
4(10) |
8 |
3(18) |
6 |
7(2) |
0 |
30 |
|
|
-1 |
8 |
4(20) |
6 |
5(5) |
9 |
0 |
25 |
|
|
-4 |
3 |
5 |
8 |
5 |
4(20) |
0 |
20 |
|
|
0 |
5 |
8 |
10 |
6(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 ед.
Размещено на Allbest.ru
Подобные документы
Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента.
контрольная работа [333,3 K], добавлен 27.11.2011Описание метода потенциалов Математическая постановка задачи об оптимальных перевозках. Метод решения задачи об оптимальных перевозках средствами Ms Excel. Постановка параметрической транспортной задачи, ее математическое и компьютерное моделирование.
курсовая работа [802,5 K], добавлен 21.10.2014Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.
контрольная работа [23,5 K], добавлен 12.06.2011Решение систем уравнений по правилу Крамера, матричным способом, с использованием метода Гаусса. Графическое решение задачи линейного программирования. Составление математической модели закрытой транспортной задачи, решение задачи средствами Excel.
контрольная работа [551,9 K], добавлен 27.08.2009Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.
курсовая работа [219,4 K], добавлен 17.04.2013Методы определения объемов выпуска изделий каждой модели, при которых прибыль будет максимальна Составление математической модели задачи целочисленного программирования. Решение задачи симплекс-методом. Поиск целочисленного решения методом отсечения.
контрольная работа [156,9 K], добавлен 30.01.2011Графическое решение задачи линейного программирования. Общая постановка и решение двойственной задачи (как вспомогательной) М-методом, правила ее формирования из условий прямой задачи. Прямая задача в стандартной форме. Построение симплекс таблицы.
задача [165,3 K], добавлен 21.08.2010Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.
курсовая работа [118,7 K], добавлен 30.04.2011Применение математических и вычислительных методов в планировании перевозок. Понятие и виды транспортных задач, способы их решения. Особенности постановки задачи по критерию времени. Решение транспортной задачи в Excel, настройка параметров решателя.
курсовая работа [1,0 M], добавлен 12.01.2011Постановка задачи коммивояжера и основные алгоритмы решения. Маршруты и пути. Понятия транспортной сети. Понятие увеличивающая дуга, цепь, разрез. Алгоритм Флойда-Уоршелл. Решение задачи аналитическим методом. Создание приложения для решения задачи.
курсовая работа [541,3 K], добавлен 08.10.2015
