ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.04.2024
Просмотров: 18
Скачиваний: 0
-
Оптимизация опорного плана тз без ограничений с применением инструментария ms Excel.
Оптимизация доказала, что опорный план является оптимальным.
Минимальные затраты составят:
Lф = 3*25 + 5*5 + 3*25 + 5*3 + 4*20 + 7*7 = 319
-
Математическая модель задачи с учетом ограничений.
Постановка задачи предполагает следующее:
-
имеется n пунктов отправления некоей продукции A1, A2,… An и m пунктов получения этой продукции B1, B2,… Bm;
-
в пункте отправления Ai содержится ai единиц продукции, а в пункте назначения Bj требуется bj единиц продукции;
-
между каждым пунктом отправления Ai и каждым пунктом назначения Bj существует коммуникация Ai→Bj ;
-
стоимость перевозки единицы продукции по маршруту Ai→Bj составляет cij;
-
количество единиц продукции, отправляемой из пункта Ai в пункт Bj обозначим xij.
Необходимо составить план перевозок {xij}, при котором вся продукция из пунктов отправления полностью вывезена, все заявки пунктов назначения выполнены, а транспортные расходы на перевозки минимальны. Математическую модель такой ТЗ составляют система ограничений:
и целевая функция:
В данной лабораторной работе мы будем решать задачу с ограничением на пропускную способность коммуникации, при которых вводятся дополнительные ограничения вида:
Алгоритм метода минимальной стоимости в задаче с ограничениями. В транспортной таблице ищут клетку с минимальной стоимостью перевозки cij. Для этой клетки выполняют сравнение ai , bj и dij. По результатам сравнения выполняем те же действия, что и при использовании метода северо-западного угла. После рассмотрения первой из минимальных клеток переходят к поиску клетки со следующей по минимальности стоимостью. Конечно, и при использовании данного метода возникает необходимость использования искусственных клеток. От искусственных клеток в базисном плане необходимо избавляться. Выполняются преобразования таблицы путем поиска соответствующих циклов перемещения перевозок. После получения опорного плана без фиктивных клеток возможно оценить оптимальность полученного плана с помощью метода потенциалов.
-
Составление опорного плана задачи с ограничениями на пропускную способность коммуникации; выбор метода минимальной стоимости составления опорного плана.
|
B1 |
B2 |
B3 |
B4 |
ai |
||||
A1 |
7 |
5 |
14 |
7 |
15 |
3 |
7 |
5 |
30 |
x11 |
|
x12 |
|
x13 |
|
x14 |
|
||
A2 |
17 |
3 |
10 |
7 |
12 |
8 |
5 |
5 |
28 |
x21 |
|
x22 |
|
x23 |
|
x24 |
|
||
A3 |
15 |
5 |
8 |
4 |
12 |
6 |
∞ |
7 |
27 |
x31 |
|
x32 |
|
x33 |
|
x34 |
|
||
bj |
25 |
20 |
25 |
15 |
85 |
Начнем формирование опорного плана методом минимальной стоимости в соответствием с изложенным выше алгоритмом. Клетка с минимальной стоимостью имеет номер (1,3), сравниваем: a1=30, b3=25, ограничение d13=15, следовательно, x13=15. Данная клетка в опорный план не войдет. Пересчитываем a1=30-15=15, b3=25-15=10.
|
B1 |
B2 |
B3 |
B4 |
ai |
||||
A1 |
7 |
5 |
14 |
7 |
15 |
3 |
7 |
5 |
30-15=15 |
x11 |
|
x12 |
|
15 |
|
x14 |
|
||
A2 |
17 |
3 |
10 |
7 |
12 |
8 |
5 |
5 |
28 |
x21 |
|
x22 |
|
x23 |
|
x24 |
|
||
A3 |
15 |
5 |
8 |
4 |
12 |
6 |
∞ |
7 |
27 |
x31 |
|
x32 |
|
x33 |
|
x34 |
|
||
bj |
25 |
20 |
25-15=10 |
15 |
85 |
Следующая по минимальности стоимость клетка c21=3. Но эта клетка тоже не войдет в опорный план.
|
B1 |
B2 |
B3 |
B4 |
ai |
||||
A1 |
7 |
5 |
14 |
7 |
15 |
3 |
7 |
5 |
15 |
x11 |
|
x12 |
|
15 |
|
x14 |
|
||
A2 |
17 |
3 |
10 |
7 |
12 |
8 |
5 |
5 |
28-17=11 |
17 |
|
x22 |
|
x23 |
|
x24 |
|
||
A3 |
15 |
5 |
8 |
4 |
12 |
6 |
∞ |
7 |
27 |
x31 |
|
x32 |
|
x33 |
|
x34 |
|
||
bj |
25-17=8 |
20 |
10 |
15 |
85 |
Продолжаем заполнять в соответствии с алгоритмом и получаем план, представленный в таблице ниже.
|
B1 |
B2 |
B3 |
B4 |
|
|
ai |
||||
A1 |
7 |
5 |
14 |
7 |
15 |
3 |
7 |
5 |
|
|
30 |
|
|
8 |
|
15 |
|
7 |
|
|
|
||
A2 |
17 |
3 |
10 |
7 |
12 |
8 |
5 |
5 |
∞ |
M |
28 |
17 |
|
4 |
|
|
|
5 |
|
2 |
|
||
A3 |
15 |
5 |
8 |
4 |
12 |
6 |
∞ |
7 |
|
|
27 |
8 |
|
8 |
|
10 |
|
1 |
|
|
|
||
|
|
|
|
|
|
|
∞ |
M |
∞ |
M |
|
|
|
|
|
|
|
|
2 |
|
M |
|
|
bj |
25 |
20 |
25 |
15 |
|
|
85 |