Практическое занятие 6. Моделирование задач транспортного типа
1.Цель и порядок выполнения работы.
1.1. Цель работы - овладеть приемами моделирования транспортных задач и их решения распределительным методом.
1.2. Порядок выполнения работы:
ознакомиться с описанием работы;
выполнить работу по указанному варианту;
оформить отчет.
2.Общие сведения
2.1.Формулировка транспортной задачи (Т3) и характеристика распределительного метода решения Т3.
Математическая модель транспортного типа относиться к классу моделей линейного программирования. Каноническая форма транспортной модели имеет следующий вид.
Найти такие значения переменных Хij ,i =1,...,n,j=1,...m, (Хij)-количество однородного груза, перевозимого из пункта отправления i в пункт назначения j ),которые удовлетворяли бы ограничениям:
суммарное количество груза , вывозимого из каждого i-го пункта отправления, равняется запасу Ai в этом пункте
б) суммарное количество груза, ввозимого в каждый пункт назначения, равняется потребности в этом пункте
и условиям неотрицательности:
так, чтобы целевая функция
где Сij -единичная стоимость перевозки груза из пункта i в пункт j , Z - суммарные транспортные расходы, удовлетворяла критерию
min Z
Если выполняется условие
то транспортная модель называется моделью закрытого типа , в противном случае - имеем модель открытого типа. В практических задачах, перевозки между некоторыми пунктами могут быть запрещены, например, из-за отсутствия транспортных путей сообщения. В такой ситуации имеет место транспортная модель с блокированием перевозок . Модели открытого типа, модели с наличием блокирования перевозок неоднародного взаимозаменяемого груза и ряд других моделей могут быть сведены к модели закрытого типа. Для этого класса моделей транспортных задач разработаны специальные методы решения.
Как и в задачах ЛП, решение транспортных задач состоит из двух этапов:
а) построение начального опорного решения;
б) поиск оптимального решения посредством направленного перебора опорных решений.
Процесс поиска решения осуществляется с помощью средств EXCEL.
5.Варианты заданий.
Пусть имеется три зернохранилища и четыре мукомольных комбината, на которые необходимо развести зерно. Транспортные расходы в тысячах рублей за тонну груза представлены в первых четырех столбцах таблицы, запасы зерна в каждом хранилище в тоннах в пятом столбце, потребности зерна на комбинатах - в шестом столбце. Необходимо представить оптимальный план перевозок, минимизирующий суммарные транспортные расходы, вручную и на ЭВМ.
Вариант 1 |
Транспортные расходы |
Запасы |
|||
5 |
8 |
3 |
10 |
40 |
|
10 |
7 |
9 |
6 |
120 |
|
7 |
3 |
6 |
4 |
600 |
|
Потребности |
400 |
150 |
100 |
110 |
|
Вариант 2 |
Транспортные расходы |
Запасы |
|||
8 |
3 |
10 |
4 |
120 |
|
7 |
9 |
6 |
5 |
600 |
|
3 |
6 |
4 |
12 |
400 |
|
Потребности |
200 |
500 |
300 |
120 |
|
Вариант 3 |
Транспортные расходы |
Запасы |
|||
3 |
10 |
4 |
5 |
600 |
|
9 |
6 |
5 |
10 |
150 |
|
6 |
4 |
12 |
7 |
250 |
|
Потребности |
500 |
250 |
150 |
100 |
|
Вариант 4 |
Транспортные расходы |
Запасы |
|||
6 |
3 |
1 |
4 |
400 |
|
2 |
5 |
2 |
7 |
400 |
|
4 |
10 |
8 |
9 |
600 |
|
Потребности |
300 |
200 |
400 |
500 |
|
Вариант 5 |
Транспортные расходы |
Запасы |
|||
3 |
2 |
4 |
1 |
500 |
|
2 |
3 |
1 |
5 |
400 |
|
3 |
2 |
4 |
4 |
200 |
|
Потребности |
200 |
200 |
200 |
500 |
|
Вариант 6 |
Транспортные расходы |
Запасы |
|||
3 |
5 |
6 |
1 |
250 |
|
6 |
6 |
11 |
5 |
250 |
|
10 |
6 |
14 |
4 |
250 |
|
Потребности |
250 |
300 |
50 |
150 |
|
Вариант 7 |
Транспортные расходы |
Запасы |
|||
12 |
3 |
5 |
8 |
200 |
|
1 |
4 |
10 |
15 |
200 |
|
5 |
6 |
1 |
3 |
230 |
|
Потребности |
70 |
130 |
150 |
280 |
|
Вариант 8 |
Транспортные расходы |
Запасы |
|||
1 |
4 |
19 |
15 |
200 |
|
5 |
6 |
1 |
3 |
200 |
|
13 |
11 |
2 |
10 |
230 |
|
Потребности |
70 |
130 |
150 |
280 |
|
Вариант 9 |
Транспортные расходы |
Запасы |
|||
7 |
11 |
10 |
5 |
40 |
|
4 |
1 |
2 |
6 |
120 |
|
7 |
12 |
10 |
2 |
600 |
|
Потребности |
400 |
150 |
100 |
110 |
|
Вариант 10 |
Транспортные расходы |
Запасы |
|||
11 |
10 |
53 |
3 |
120 |
|
1 |
2 |
6 |
4 |
600 |
|
12 |
10 |
2 |
1 |
400 |
|
Потребности |
200 |
500 |
300 |
120 |
|
Вариант 11 |
Транспортные расходы |
Запасы |
|||
4 |
1 |
2 |
6 |
400 |
|
7 |
12 |
10 |
2 |
400 |
|
3 |
4 |
5 |
6 |
600 |
|
Потребности |
200 |
300 |
400 |
500 |
|
Вариант 12 |
Транспортные расходы |
Запасы |
|||
1 |
2 |
4 |
6 |
200 |
|
12 |
10 |
2 |
1 |
400 |
|
4 |
5 |
6 |
7 |
100 |
|
Потребности |
200 |
500 |
100 |
300 |
|
Вариант 13 |
Транспортные расходы |
Запасы |
|||
7 |
5 |
4 |
3 |
400 |
|
7 |
4 |
6 |
6 |
400 |
|
4 |
8 |
7 |
9 |
320 |
|
Потребности |
200 |
500 |
200 |
220 |
|
Вариант 14 |
Транспортные расходы |
Запасы |
|||
4 |
8 |
7 |
9 |
600 |
|
7 |
3 |
5 |
6 |
400 |
|
6 |
7 |
4 |
5 |
350 |
|
Потребности |
500 |
250 |
350 |
300 |
|
Вариант 15 |
Транспортные расходы |
Запасы |
|||
8 |
7 |
9 |
7 |
400 |
|
3 |
5 |
6 |
4 |
600 |
|
7 |
4 |
5 |
3 |
120 |
|
Потребности |
200 |
500 |
300 |
120 |
|
6.Контрольные вопросы
6.1.Математическая модель транспортной задачи.
6.2.Модели открытого и закрытого типа.
6.3.Блокирование перевозок.
6.4.Этапы решения задачи.