Задача - Транспортная задача - файл n1.docx
приобрестиЗадача - Транспортная задача
скачать (105.4 kb.)
Доступные файлы (1):
| n1.docx | 106kb. | 05.06.2012 06:41 | скачать |
- Смотрите также:
- Курсовая работа - Математические основы теории систем (МОТС) (Курсовая)
- Лекция - Общая характеристика распределительной задачи (Лекция)
- Транспортная задача. Методы построения опорного плана. Метод оптимального распределения поставок (Документ)
- Лабораторная - Транспортная задача и задача динамического программирования (Лабораторная работа)
- Жилинская. Ответы на задачи по Гражданскому процессу (Документ)
- Лабораторная работа - Дослідження операцій в економіці, лінійне прорамування (Лабораторная работа)
- Реферат - Теорема Птолемея (Реферат)
- Ляпидов В.C. Теоретические основы кибернетики. Методы оптимизации (Документ)
- Решение задач по методам оптимизации (Лабораторная работа)
- Задача задача Задача задача 13 Список используемых источников 15 (Документ)
- Контрольная работа - Транспортная задача. Метод потенциалов. Модули Matlab (Лабораторная работа)
- Задача на Магнетизм б Задача на Электромагнитная индукция б Задача на Геометрическая оптика б (Документ)
n1.docx
выпускается однородная продукция в количестве 
, единиц. Себестоимость единицы продукции в пункте 
равна 
. Готовая продукция поставляется в пункты 
, потребности которых составляют 
единиц. Стоимость 
перевозки единицы продукции из пункта 
в пункт 
известна.Требуется:
Найти оптимальный план перевозок, который обеспечивает минимальные суммарные затраты на производство и доставку продукции;
Составить экономико-математическую модель задачи;
Найти величину
минимальных затрат.
Все необходимые данные даны в таблице:
 |  |  |  |  |  |  |  |  |  |  |
| 140 | 180 | 240 | 3 | 3 | 2 | 80 | 160 | 120 | 180 | 3 |
 |  |  |  |  |  |  |  |  |  |  |
| 2 | 6 | 6 | 5 | 1 | 4 | 8 | 7 | 10 | 6 | 3 |
Решение.
Задача является открытой, так как запасы суммарный спрос меньше суммарного предложения: 140+180+240 = 560 > 540 = 80+160+120+180 единиц. Для того, чтобы привести задачу к закрытому типу, необходимо ввести фиктивного потребителя
с потребностью в 560-540=20 единиц продукции. Стоимость перевозки в пункт потребления из всех пунктов производства считаем равным 0. Пусть
– количество единиц продукции, перевозимой из пункта 
в пункт 
. Задача заключается в минимизации общих транспортных расходов:
при ограничениях
и естественном условии неотрицательности количества поставляемой продукции
Математическая модель задачи выглядит следующим образом:
Составим опорный план методом северо-западного угла.
Рассмотрим "северо-западный угол" незаполненной таблицы, то есть клетку, соответствующую первому поставщику и первому потребителю. Поставим туда наименьшее из значений 140 и 80, т.е 80. Тогда спрос первого потребителя будет удовлетворён, вычеркнем из дальнейшего рассмотрения первый столбец, а у первого поставщика осталось 140-80=60 единиц нераспределённой продукции. Далее рассматриваем "северо-западный угол" оставшейся таблицы, то есть клетку, соответствующую первому поставщику и второму потребителю, ставим туда наименьшее из значений 160 и 60, т.е. 60. Вся продукция первого поставщика распределена, значит вычёркиваем первый столбец, у второго потребителя потребность уменьшилась до 160-60=100. Аналогично продолжаем заполнять таблицу. После n+m-1 шагов получаем опорный план:
| | 80 | 160 | 120 | 180 | 20 |
| 140 | 80 | 60 | - | - | - |
| 180 | - | 100 | 80 | - | - |
| 240 | - | - | 40 | 180 | 20 |
Составим начальный опорный план методом наименьшего элемента. В правом верхнем углу каждой ячейки записываем
  | 80 | 160 | 120 | 180 | 20 | |||||
| 140 | | 6 | | 5 | | 9 | | 9 | | 3 |
| 80 | | | | 40 | | | | 20 | | |
| 180 | | 8 | | 4 | | 7 | | 11 | | 3 |
| | | 160 | | 20 | | | | | | |
| 240 | | 9 | | 12 | | 8 | | 5 | | 2 |
| | | | | 60 | | 180 | | | | |
Введем некоторые обозначения: Ai* - излишек нераспределенного груза от поставщика Ai, Bj* - недостача в поставке груза потребителю Bj.
Находим незанятую клетку с минимальным тарифом (рассматриваем нефиктивных потребителей): (2,2). Помещаем туда меньшее
из чисел A2*=180 и B2*=160. Спрос потребителя B2 удовлетворён (B2*=0), A2* стало равным 180-160=20.
Находим незанятую клетку с минимальным тарифом: (3,4). Помещаем туда меньшее
из чисел A3*=240 и B4*=180. Спрос потребителя B4 удовлетворён (B4*=0), A3* стало равным 240-180=60.
Находим незанятую клетку с минимальным тарифом: (1,1). Помещаем туда меньшее
из чисел A1*=140 и B1*=80. Спрос потребителя B1 удовлетворён (B1*=0), A1* стало равным 140-80=60.
Находим незанятую клетку с минимальным тарифом: (2,3). Помещаем туда меньшее
из чисел A2*=20 и B3*=120. Продукция пункта A2 распределена (A2*=0), B3* стало равным 120-20=100.
Находим незанятую клетку с минимальным тарифом: (3,3). Помещаем туда меньшее
из чисел A3*=60 и B3*=100. Продукция пункта A3 распределена (A3*=0), B3* стало равным 100-60=40.
Находим незанятую клетку с минимальным тарифом: (1,3). Помещаем туда меньшее из чисел A1*=60 и B3*=40. Спрос потребителя B3 удовлетворён (B3*=0), A1* стало равным 60-40=20.
Осталось распределить 20 единиц груза из пункта А1. Неудовлетворённым остался только спрос фиктивного потребителя – пункта В5. Помещаем туда 20, после чего вся продукция становится распределённой и спрос всех потребителей удовлетворён.
Таким образом, начальным опорным планом является
.Проверим, является ли план, полученный методом наименьшего элемента, оптимальным, используя метод потенциалов. Так как m+n-1=5+3-1=7 и имеем 7 загруженных клеток, план является ацикличным.
Пусть Ui и Vj - потенциалы i-го склада и j-го магазина соответственно.
Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=C'i,j,
просматривая все занятые клетки. Получим:
U1 = 0
V1 = C'1,1 – U1 = 6 - 0 = 6
V3 = C'1,3 - U1 = 9 – 0 = 9
V5 = C'1,5 – U1 = 3 – 0 = 3
U2 = C'2,3 - V3 = 7 – 9 = -2
U3 = C'3,3 – V3 = 8 – 9 = -1
V2 = C'2,2 – U2 = 5 – (-1) = 6
V4 = C'3,4 – U3 = 5 – (-1) = 6
Для свободных клеток определим значения оценок (разностей между прямыми и
косвенными тарифами).
S1,2 = C'1,2 - (U1 + V2) = -1
S1,4 = C'1,4 - (U1 + V4) = 3
S2,1 = C'2,1 - (U2 + V1) = 4
S2,4 = C'2,4 - (U2 + V4) = 7
S2,5 = C'2,5 - (U2 + V5) = 2
S3,1 = C'3,1 - (U3 + V1) = 4
S3,2 = C'3,2 - (U3 + V2) = 7
S3,5 = C'3,5 - (U3 + V5) = 0
Имеем одну клетку с отрицательной оценкой – клетка (1,2). Строим для нее цикл так, чтобы он начинался и заканчивался в этой клетке, а остальными узлами были бы загруженные клетки таблицы.
| | 80 | 160 | 120 | 180 | 20 | |||||
| 140 | | 6 | + | 5 | - | 9 | | 9 | | 3 |
| 80 | | | | 40 | | | | 20 | | |
| 180 | | 8 | - | 4 | + | 7 | | 11 | | 3 |
| | | 160 | | 20 | | | | | | |
| 240 | | 9 | | 12 | | 8 | | 5 | | 2 |
| | | | | 60 | | 180 | | | | |
Перемещаем по циклу груз величиной в 40 единиц (выбирается минимальное количество груза из значений, указанных в заполненных клетках цикла, помеченных знаком "минус", так как мы не можем отнять больше единиц продукции, чем есть), прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".
В результате перемещения по циклу получим новый план:
| | 80 | 160 | 120 | 180 | 20 | |||||
| 140 | | 6 | | 5 | | 9 | | 9 | | 3 |
| 80 | | 40 | | | | | | 20 | | |
| 180 | | 8 | | 4 | | 7 | | 11 | | 3 |
| | | 120 | | 60 | | | | | | |
| 240 | | 9 | | 12 | | 8 | | 5 | | 2 |
| | | | | 60 | | 180 | | | | |
Целевая функция (суммарные транспортные расходы и расходы на производство по полученному плану)
. Значение целевой функции уменьшилось на 40 единиц по сравнению с предыдущим этапом.Проверим полученный план на оптимальность. Подсчитаем потенциалы.
U1 = 0
V1 = C'1,1 – U1 = 6 - 0 = 6
V2 = C'1,2 - U1 = 5 – 0 = 5
V5 = C'1,5 – U1 = 3 – 0 = 3
U2 = C'2,2 – V2 = 4 – 5 = -1
V3 = C'2,3 – U2 = 7 – (-1) = 8
U3 = C'3,3 – V3 = 8 – 8 = 0
V4 = C'3,4 – U3 = 5 – 0 = 5
Для свободных клеток определим значения оценок
S1,3 = C'1,1 - (U1 + V1) = 3
S1,4 = C'1,4 - (U1 + V4) = 3
S2,1 = C'2,1 - (U2 + V1) = 3
S2,4 = C'2,4 - (U2 + V4) = 7
S2,5 = C'2,5 - (U2 + V5) = 1
S3,1 = C'3,1 - (U3 + V1) = 3
S3,2 = C'3,2 - (U3 + V2) = 7
S3,5 = C'3,5 - (U3 + V5) = -1
План не оптимален, так как имеется клетка с отрицательной оценкой – (3,5). Строим для нее цикл.
| | 80 | 160 | 120 | 180 | 20 | |||||
| 140 | | 6 | + | 5 | | 9 | | 9 | - | 3 |
| 80 | | 40 | | | | | | 20 | | |
| 180 | | 8 | - | 4 | + | 7 | | 11 | | 3 |
| | | 120 | | 60 | | | | | | |
| 240 | | 9 | | 12 | - | 8 | | 5 | + | 2 |
| | | | | 60 | | 180 | | | | |
Перемещаем по циклу груз величиной в 20 единиц.
В результате перемещения по циклу следующий план:
| | 80 | 160 | 120 | 180 | 20 | |||||
| 140 | | 6 | | 5 | | 9 | | 9 | | 3 |
| 80 | | 60 | | | | | | | | |
| 180 | | 8 | | 4 | | 7 | | 11 | | 3 |
| | | 100 | | 80 | | | | | | |
| 240 | | 9 | | 12 | | 8 | | 5 | | 2 |
| | | | | 40 | | 180 | | 20 | | |
Целевая функция (транспортные расходы)
. Значение целевой функции уменьшилось на 20 единиц по сравнению с предыдущим этапом.Проверим полученный план на оптимальность. Подсчитаем потенциалы.
U1 = 0
V1 = C'1,1 – U1 = 6 - 0 = 6
V2 = C'1,2 - U1 = 5 – 0 = 5
U2 = C'2,2 – V2 = 4 – 5 = -1
V3 = C'2,3 – U2 = 7 – (-1) = 8
U3 = C'3,3 – V3 = 8 – 8 = 0
V4 = C'3,4 – U3 = 5 – 0 = 5
V5 = C'3,5 – U3 = 2 – 0 = 2
Для свободных клеток определим значения оценок
S1,3 = C'1,1 - (U1 + V1) = 1
S1,4 = C'1,4 - (U1 + V4) = 4
S1,5 = C'1,5 - (U1 + V5) = 1
S2,1 = C'2,1 - (U2 + V1) = 3
S2,4 = C'2,4 - (U2 + V4) = 7
S2,5 = C'2,5 - (U2 + V5) = 2
S3,1 = C'3,1 - (U3 + V1) = 3
S3,2 = C'3,2 - (U3 + V2) = 7
Так как все оценки Si,j>=0, то полученный план является оптимальным, минимальные
транспортные расходы равны 3000.
Как видим, опорный план, полученный методом северо-западного угла, оказался оптимальным.
Ответ: Оптимальный план перевозок представлен в таблице
| | 80 | 160 | 120 | 180 | 20 | |||||
| 140 | | 6 | | 5 | | 9 | | 9 | | 3 |
| 80 | | 60 | | | | | | | | |
| 180 | | 8 | | 4 | | 7 | | 11 | | 3 |
| | | 100 | | 80 | | | | | | |
| 240 | | 9 | | 12 | | 8 | | 5 | | 2 |
| | | | | 40 | | 180 | | 20 | | |