Оптимизация опорного плана тз без ограничений с применением инструментария 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 |
||||
Как видно, пришлось ввести две искусственные клетки (2,5) и (4,4), в которых помещены перевозки, необходимые для баланса плана. Клетка (4,5) вспомогательная, она необходима для нахождения циклов, с помощью которых мы будем избавляться от вспомогательных искусственных клеток.
Ход, с которого можно начать эту работу: по циклу (2,5)→(2,2)→(3,2)→(3,4)→(4,4)→(4,5)→(2,5) можно перебросить две единицы продукции.
|
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 |
|
6 |
[+] |
|
|
5 |
|
0 |
[-] |
|||||
A3 |
15 |
5 |
8 |
4 |
12 |
6 |
∞ |
7 |
|
|
27 |
|||
8 |
|
6 |
[-] |
10 |
|
3 |
[+] |
|
|
|||||
|
|
|
|
|
|
|
∞ |
M |
∞ |
M |
|
|||
|
|
|
|
|
|
|
0 |
[-] |
M |
[+] |
|
|||
bj |
25 |
20 |
25 |
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 |
28 |
|
17 |
|
6 |
|
|
|
5 |
|
|||
A3 |
15 |
5 |
8 |
4 |
12 |
6 |
∞ |
7 |
27 |
|
8 |
|
6 |
|
10 |
|
3 |
|
|||
bj |
25 |
20 |
25 |
15 |
85 |
|||||
Целевая функция: Lф = 7*8 + 3*15 + 5*7 + 3*17 + 7*6 + 5*5 + 5*8 + 4*6 + 6*10 + 7*3 = 399. Это больше, если сравнивать с целевой функцией этой же транспортной задачи, но без ограничений (там было Lф = 319).