Лабораторная работа №5
.pdf
ЛАБОРАТОРНАЯ РАБОТА №8 Поиск оптимальных решений. Транспортная задача
Краткий комментарий
Транспортная задача
В современных условиях большие транспортные расходы связаны с простоями в ожидании обслуживания на погрузочно-разгрузочных работах, порожними пробегами, встречными и нерациональными перевозками, затратами на бензин, техническое обслуживание и заработную плату водителей. В связи с этим необходимо решать задачи оптимального планирования перевозок грузов из пунктов отправления (баз, станций, фабрик, совхозов, заводов) в пункты назначения (магазины, склады) методами, позволяющими оптимизировать план по какому-либо экономическому показателю, например финансовых затрат или времени на перевозку грузов.
Для решения подобного рода задач в линейном программировании существуют специально разработанные методы, а задачи такого рода называются транспортными задачами.
Постановка задачи
Требуется составить план перевозок однородного груза таким образом, чтобы об-
щая стоимость перевозок была минимальной. |
|
|
Исходная информация: |
|
|
ai - количество единиц груза в i- м пункте отправления(i= |
); |
|
bj - потребность в j- м пункте назначения (j= |
), в единицах груза; |
|
cij - стоимость перевозки единицы груза из i- го пункта в j- й. |
||
Найти: xij – планируемое количество единиц |
груза для |
перевозки iиз-го пункта |
отправления в j-й пункт назначения. |
|
|
Цель: минимум затрат на перевозку.
Математическая модель задачи выглядит следующим образом.
Целевая функция:
→min.
ЦФ представляет суммарную стоимость перевозок.
Ограничения:
, i= 
, вывоз груза из i-го пункта отправления равен запасу груза в этом
пункте.
, j=
доставка груза в j-ый пункт назначения равен спросу на груз в
этом пункте.
Граничное условие: xij ³ 0, i = 1, m j = 1, n , объем перевозимого груза не может быть отрицательным.
Согласно уравнениям ограничений модели количество вывезенного груза должно
быть равно количеству принятого .
Задание и технология выполнения
Три поставщика одного и того же продукта располагают в планируемый период следующими запасами этого продукта: первый - 120 условных единиц, второй - 100
и третий 80 единиц. Этот продукт должен быть |
перевезен к трем потребителям, |
|
Корпоративные информационные системы |
Финансы и кредит |
1 |
спросы которых соответственно равны 90, 90 и 120 условных единиц. Приведенная ниже таблица содержит показатели затрат, связанных с перевозкой продукта из i-го пункта отправления в j-й пункт потребления.
Поставщики |
|
Потребители |
|
Запасы |
|
А |
Б |
В |
|||
|
|
||||
I |
7 |
6 |
4 |
120 |
|
II |
3 |
8 |
5 |
100 |
|
III |
2 |
3 |
7 |
80 |
|
Спрос |
90 |
90 |
120 |
|
Требуется перевезти продукт с минимальными затратами.
Математическая модель
Целевая функция имеет вид:
7x11 + 6x12 + 4x13 + 3x21 +8x22 + 5x23 + 2x31 + 3x31 + 7x33 ® min
Ограничения имеют вид:
ì x |
+ x |
+ x |
=120; |
ì x |
+ x |
+ x |
= 90; |
ï 11 |
12 |
13 |
=100; |
ï 11 |
21 |
31 |
= 90; |
íx21 |
+ x22 + x23 |
í x12 + x22 + x32 |
|||||
ï x |
+ x |
+ x |
= 80. |
ïx |
+ x |
+ x |
=120. |
î 31 |
32 |
33 |
|
î 31 |
23 |
33 |
|
Граничные условия
xij ³ 0, i =1,3, j =1,3.
Электронная таблица
Вид электронной таблицыExcel, созданной для решения задачи, представлен на рисунке.
Искомые значения xij находятся в блоке ячеек B12:D14. Требования к ограничениям по спросу и запасам представлены соответственно в ячейкахB7:D7 и E4:E6. Коэффициенты ЦФ, означающие затраты на доставку расположены в блоке ячеек B4:D4. Формулы целевой функции и ограничений находятся соответственно в ячейкеE15 и ячейках B15:D15 (ограничения по спросу), E12:E14 (ограничения по запасам).
Таблица в режиме отображения значений
Корпоративные информационные системы Финансы и кредит |
2 |
Вид электронной таблицы в режиме отображения формул
3
Поиск оптимального решения
1.Выполнить команду меню Сервис►Поиск решения.
2.Ввести параметры поиска в окне диалога Поиск решения:
Результат поиска оптимального решения
Корпоративные информационные системы Финансы и кредит |
4 |
Самостоятельная работа
Составить оптимальный план перевозки груза от поставщиков к потребителям. Стоимость перевозки ед. груза, объемы производства и спрос потребителей представлены в таблице.
Вариант 1
Задание 1
Затраты на поставку единицы груза
Поставщики |
|
Потребители |
|
Запас |
|||
B1 |
B2 |
B3 |
B4 |
||||
|
|
|
|||||
A1 |
|
8 |
11 |
1 |
4 |
20 |
|
A2 |
|
5 |
2 |
7 |
3 |
67 |
|
A3 |
|
10 |
4 |
3 |
5 |
39 |
|
|
|||||||
Спрос |
|
44 |
32 |
25 |
25 |
|
|
Ответ: 462
Задание 2
Решить задачу 1 при условии, что запрещена перевозка груза от 3-го поставщика 4- му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.
Задание 3
Решить задачу 1 при условии, что поставка груза от 1-го поставщика 2-му потребителю зафиксирована и равна20 единиц. Оценить удорожание перевозок груза по сравнению с оптимальным вариантом.
Задание 4
Затраты на перевозку груза
Пункты отправления |
Пункты назначения |
Запасы |
||||
B1 |
B2 |
B3 |
B4 |
|||
|
|
|||||
A1 |
5 |
4 |
3 |
4 |
160 |
|
A2 |
3 |
2 |
5 |
5 |
140 |
|
A3 |
1 |
6 |
3 |
2 |
60 |
|
Потребности |
80 |
80 |
60 |
80 |
|
|
Ответ: 780
Вариант 2
Задание 1
Затраты на поставку единицы груза
|
Поставщики |
|
|
Потребители |
|
|
Запас |
|
|||
|
|
|
|
|
|
||||||
|
|
B1 |
B2 |
|
B3 |
B4 |
|
||||
|
|
|
|
|
|
|
|||||
|
A1 |
|
|
15 |
7 |
|
11 |
7 |
|
300 |
|
|
|
|
|
|
|||||||
|
A2 |
|
|
6 |
4 |
|
12 |
18 |
|
1200 |
|
|
A3 |
|
|
7 |
11 |
|
5 |
10 |
|
600 |
|
|
Спрос |
|
|
500 |
550 |
|
550 |
500 |
|
|
|
|
|
|
|
Ответ: 13 100 |
|
|
|
|
|
||
|
Корпоративные информационные системы |
Финансы и кредит |
5 |
||||||||
Задание 2
Решить задачу 1 при условии, что запрещена перевозка груза от 2-го поставщика 3- му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.
Задание 3
Решить задачу 1 при условии, что поставка груза от 2-го поставщика 4-му потребителю зафиксирована и равна100 единиц. Оценить удорожание перевозок груза по сравнению с оптимальным вариантом.
Задание 4
Затраты на перевозку груза
Пункты отправления |
Пункты назначения |
Запасы |
||||
B1 |
B2 |
B3 |
B4 |
|||
|
|
|||||
A1 |
4 |
2 |
3 |
1 |
80 |
|
A2 |
6 |
3 |
5 |
6 |
140 |
|
A3 |
3 |
2 |
6 |
3 |
70 |
|
Потребности |
80 |
50 |
50 |
70 |
|
|
Ответ: 720
Вариант 3
Задание 1
Затраты на поставку единицы груза
|
Поставщики |
|
|
Потребители |
|
|
Запас |
|
||
|
|
|
|
|
|
|||||
|
|
B1 |
B2 |
B3 |
B4 |
|
||||
|
|
|
|
|
|
|||||
|
A1 |
|
|
3 |
8 |
10 |
5 |
|
90 |
|
|
|
|
|
|||||||
|
A2 |
|
|
1 |
4 |
6 |
2 |
|
190 |
|
|
A3 |
|
|
3 |
1 |
9 |
7 |
|
120 |
|
|
Спрос |
|
|
80 |
30 |
120 |
180 |
|
|
|
Ответ: 1 650
Задание 2
Решить задачу 1 при условии, что запрещена перевозка груза от 3-го поставщика 3- му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.
Задание 3
Решить задачу 1 при условии, что поставка груза от 1-го поставщика 3-му потребителю зафиксирована и равна50 единиц. Оценить удорожание перевозок груза по сравнению с оптимальным вариантом.
Корпоративные информационные системы Финансы и кредит |
6 |
Задание 4
Затраты на перевозку груза
Пункты отправления |
|
Пункты назначения |
|
Запасы |
|||
B1 |
|
B2 |
B3 |
|
B4 |
||
|
|
|
|
||||
A1 |
6 |
|
7 |
3 |
|
2 |
180 |
A2 |
5 |
|
1 |
4 |
|
3 |
90 |
A3 |
3 |
|
2 |
6 |
|
2 |
170 |
Потребности |
45 |
|
45 |
100 |
|
160 |
|
Ответ: 800
Вариант 4
Задание 1
Затраты на поставку единицы груза
|
Поставщики |
|
|
Потребители |
|
|
|
Запас |
|
||
|
|
|
|
|
|
|
|||||
|
|
B1 |
B2 |
B3 |
|
B4 |
|
||||
|
|
|
|
|
|
|
|||||
|
A1 |
|
|
14 |
20 |
11 |
|
18 |
|
50 |
|
|
|
|
|
|
|||||||
|
A2 |
|
14 |
11 |
15 |
|
16 |
|
20 |
|
|
|
A3 |
|
|
10 |
9 |
6 |
|
11 |
|
30 |
|
|
Спрос |
|
10 |
25 |
15 |
|
50 |
|
|
|
|
|
|
|
|
|
|||||||
Ответ: 1 295
Задание 2
Решить задачу 1 при условии, что запрещена перевозка груза от 3-го поставщика 2- му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.
Задание 3
Решить задачу 1 при условии, что поставка груза от 2-го поставщика 3-му потребителю зафиксирована и равна10 единиц. Оценить удорожание перевозок груза по сравнению с оптимальным вариантом.
Задание 4
Затраты на перевозку груза
Пункты отправления |
|
Пункты назначения |
|
Запасы |
|||
B1 |
|
B2 |
B3 |
|
B4 |
||
|
|
|
|
||||
A1 |
1 |
|
7 |
9 |
|
5 |
120 |
A2 |
4 |
|
2 |
6 |
|
8 |
280 |
A3 |
3 |
|
8 |
1 |
|
2 |
160 |
Потребности |
130 |
|
220 |
60 |
|
70 |
|
Ответ: 790
Корпоративные информационные системы Финансы и кредит |
7 |
Вариант 5
Задание 1 |
Затраты на поставку единицы груза |
|
|
|||||||
|
|
|
|
|||||||
|
Поставщики |
|
|
Потребители |
|
|
|
Запас |
||
|
|
B1 |
B2 |
B3 |
|
B4 |
|
|||
|
|
|
|
|
|
|
||||
|
A1 |
|
|
24 |
19 |
21 |
|
15 |
|
51 |
|
|
|
|
|
||||||
|
A2 |
|
14 |
21 |
15 |
|
16 |
|
19 |
|
|
A3 |
|
|
10 |
9 |
6 |
|
11 |
|
28 |
|
Спрос |
|
|
15 |
10 |
11 |
|
62 |
|
|
|
|
|
|
|
|
|||||
Ответ: 1 272
Задание 2
Решить задачу 1 при условии, что запрещена перевозка груза от 3-го поставщика 4- му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.
Задание 3
Решить задачу 1 при условии, что поставка груза от 1-го поставщика 4-му потребителю зафиксирована и равна20 единиц. Оценить удорожание перевозок груза по сравнению с оптимальным вариантом.
Задание 4
Затраты на перевозку груза
Пункты |
|
Пункты назначения |
|
Запасы |
||
отправления |
B1 |
B2 |
B3 |
|
B4 |
|
|
|
|||||
A1 |
5 |
4 |
3 |
|
4 |
160 |
A2 |
3 |
2 |
5 |
|
5 |
140 |
A3 |
1 |
6 |
3 |
|
2 |
60 |
Потребности |
85 |
100 |
70 |
|
120 |
|
Ответ: 965
Вариант 6
Задание 1
Затраты на поставку единицы груза
Поставщики |
|
|
Потребители |
|
|
|
Запас |
||
|
B1 |
B2 |
B3 |
|
B4 |
||||
|
|
|
|
|
|||||
A1 |
|
|
3 |
8 |
10 |
|
5 |
|
50 |
|
|
|
|
||||||
A2 |
|
1 |
4 |
6 |
|
2 |
|
150 |
|
A3 |
|
|
3 |
1 |
9 |
|
7 |
|
100 |
Спрос |
|
30 |
70 |
90 |
|
110 |
|
|
|
|
|
|
|
||||||
Ответ: 1 070
Задание 2
Решить задачу 1 при условии, что запрещена перевозка груза от 3-го поставщика 1-
Корпоративные информационные системы Финансы и кредит |
8 |
му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.
Задание 3
Решить задачу 1 при условии, что поставка груза от 1-го поставщика 2-му потребителю зафиксирована и равна50 единиц. Оценить удорожание перевозок груза по сравнению с оптимальным вариантом.
Задание 4
Затраты на перевозку груза
Пункты отправления |
|
Пункты назначения |
|
Запасы |
|||
B1 |
|
B2 |
B3 |
|
B4 |
||
|
|
|
|
||||
A1 |
4 |
|
2 |
3 |
|
1 |
80 |
A2 |
6 |
|
3 |
5 |
|
6 |
140 |
A3 |
3 |
|
2 |
6 |
|
3 |
70 |
Потребности |
80 |
|
80 |
80 |
|
70 |
|
Ответ: 850
Вариант 7
Задание 1
|
|
Затраты на поставку единицы груза |
|
|
|
|||||
|
Поставщики |
|
|
Потребители |
|
|
Запас |
|
||
|
|
|
|
|
|
|||||
|
|
B1 |
B2 |
B3 |
B4 |
|
|
|||
|
|
|
|
|
|
|
||||
|
A1 |
|
|
8 |
11 |
1 |
4 |
|
20 |
|
|
|
|
|
|
||||||
|
A2 |
|
|
5 |
2 |
7 |
3 |
|
67 |
|
|
A3 |
|
|
10 |
4 |
3 |
5 |
|
39 |
|
|
Спрос |
|
|
54 |
32 |
25 |
15 |
|
|
|
Ответ: 482
Задание 2
Решить задачу 1 при условии, что запрещена перевозка груза от 3-го поставщика 3- му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.
Задание 3
Решить задачу 1 при условии, что поставка груза от 2-го поставщика 4-му потребителю зафиксирована и равна50 единиц. Оценить изменение перевозок груза по сравнению с оптимальным вариантом.
Корпоративные информационные системы Финансы и кредит |
9 |
Задание 4
Затраты на перевозку груза
Пункты |
|
Пункты назначения |
|
Запасы |
|||
отправления |
B1 |
|
B2 |
B3 |
|
B4 |
|
|
|
|
|||||
A1 |
6 |
|
7 |
3 |
|
2 |
200 |
A2 |
5 |
|
1 |
4 |
|
3 |
110 |
A3 |
3 |
|
2 |
6 |
|
2 |
170 |
Потребности |
100 |
|
150 |
100 |
|
160 |
|
Ответ: 1 020
Вариант 8
Задание 1
Затраты на поставку единицы груза
Поставщики |
|
|
|
|
Потребители |
|
|
|
|
Запас |
|||
|
|
B1 |
|
B2 |
|
B3 |
|
|
B4 |
||||
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|||||
A1 |
|
|
15 |
|
7 |
|
11 |
|
|
7 |
|
800 |
|
|
|
|
|
|
|
|
|||||||
A2 |
|
|
6 |
4 |
12 |
|
18 |
|
1290 |
||||
A3 |
|
|
|
7 |
11 |
5 |
|
10 |
|
900 |
|||
Спрос |
|
1000 |
550 |
490 |
|
950 |
|
|
|||||
|
|
|
|
|
|||||||||
Ответ: 18 010
Задание 2
Решить задачу 1 при условии, что запрещена перевозка груза от 1-го поставщика 4- му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.
Задание 3
Решить задачу 1 при условии, что поставка груза от 1-го поставщика 1-му потребителю зафиксирована и равна400 единиц. Оценить удорожание перевозок груза по сравнению с оптимальным вариантом.
Задание 4
Затраты на перевозку груза
Пункты |
|
Пункты назначения |
|
Запасы |
||
отправления |
B1 |
|
B2 |
B3 |
B4 |
|
|
|
|||||
A1 |
1 |
|
7 |
9 |
5 |
100 |
A2 |
4 |
|
2 |
6 |
8 |
200 |
A3 |
3 |
|
8 |
1 |
2 |
110 |
Потребности |
100 |
|
190 |
60 |
80 |
|
Ответ: 710
Корпоративные информационные системы Финансы и кредит |
10 |