Практика
.pdfПотребности |
4 |
6 |
8 |
8 |
|
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 6 + 8 + 10 = 24
∑b = 4 + 6 + 8 + 8 = 26
Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 2 (24—26). Тарифы перевозки единицы груза из базы ко всем потребителям полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
|
1 |
2 |
3 |
4 |
Запасы |
1 |
1 |
2 |
4 |
3 |
6 |
2 |
4 |
3 |
8 |
5 |
8 |
3 |
2 |
7 |
6 |
3 |
10 |
4 |
0 |
0 |
0 |
0 |
2 |
Потребности |
4 |
6 |
8 |
8 |
|
Этап I. Поиск первого опорного плана.
1. Используя метод северо-западного угла, построим первый опорный план транспортной
задачи.
План начинается заполняться с верхнего левого угла.
Искомый элемент равен c11=1. Для этого элемента запасы равны 6, потребности 4. Поскольку минимальным является 4, то вычитаем его.
x11 = min(6,4) = 4.
1 |
2 |
4 |
3 |
6 - 4 = 2 |
x |
3 |
8 |
5 |
8 |
x |
7 |
6 |
3 |
10 |
x |
0 |
0 |
0 |
2 |
4 - 4 = 0 |
6 |
8 |
8 |
|
Искомый элемент равен c12=2. Для этого элемента запасы равны 2, потребности 6. Поскольку минимальным является 2, то вычитаем его.
x12 = min(2,6) = 2.
1 |
2 |
x |
x |
2 - 2 = 0 |
x |
3 |
8 |
5 |
8 |
x |
7 |
6 |
3 |
10 |
x |
0 |
0 |
0 |
2 |
0 |
6 - 2 = 4 |
8 |
8 |
|
Искомый элемент равен c22=3. Для этого элемента запасы равны 8, потребности 4. Поскольку минимальным является 4, то вычитаем его.
x22 = min(8,4) = 4.
1 |
2 |
x |
x |
0 |
x |
3 |
8 |
5 |
8 - 4 = 4 |
x |
x |
6 |
3 |
10 |
x |
x |
0 |
0 |
2 |
0 |
4 - 4 = 0 |
8 |
8 |
|
Искомый элемент равен c23=8. Для этого элемента запасы равны 4, потребности 8. Поскольку минимальным является 4, то вычитаем его.
x23 = min(4,8) = 4.
1 |
2 |
x |
x |
0 |
x |
3 |
8 |
x |
4 - 4 = 0 |
x |
x |
6 |
3 |
10 |
x |
x |
0 |
0 |
2 |
0 |
0 |
8 - 4 = 4 |
8 |
|
Искомый элемент равен c33=6. Для этого элемента запасы равны 10, потребности 4. Поскольку минимальным является 4, то вычитаем его.
x33 = min(10,4) = 4.
1 |
2 |
x |
x |
0 |
x |
3 |
8 |
x |
0 |
x |
x |
6 |
3 |
10 - 4 = 6 |
x |
x |
x |
0 |
2 |
0 |
0 |
4 - 4 = 0 |
8 |
|
Искомый элемент равен c34=3. Для этого элемента запасы равны 6, потребности 8. Поскольку минимальным является 6, то вычитаем его.
x34 = min(6,8) = 6.
1 |
2 |
x |
x |
0 |
x |
3 |
8 |
x |
0 |
x |
x |
6 |
3 |
6 - 6 = 0 |
x |
x |
x |
0 |
2 |
0 |
0 |
0 |
8 - 6 = 2 |
|
Искомый элемент равен c44=0. Для этого элемента запасы равны 2, потребности 2. Поскольку минимальным является 2, то вычитаем его.
x44 = min(2,2) = 2.
1 |
2 |
x |
x |
0 |
x |
3 |
8 |
x |
0 |
x |
x |
6 |
3 |
0 |
x |
x |
x |
0 |
2 - 2 = |
|
|
|
|
0 |
0 |
0 |
0 |
2 - 2 = |
|
|
|
|
0 |
|
|
1 |
2 |
3 |
4 |
Запасы |
1 |
1[4] |
2[2] |
4 |
3 |
6 |
2 |
4 |
3[4] |
8[4] |
5 |
8 |
3 |
2 |
7 |
6[4] |
3[6] |
10 |
4 |
0 |
0 |
0 |
0[2] |
2 |
Потребности |
4 |
6 |
8 |
8 |
|
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 1*4 + 2*2 + 3*4 + 8*4 + 6*4 + 3*6 + 0*2 = 94
ОТВЕТ:
Анализ оптимального плана.
Из 1-го склада необходимо весь груз направить к 3-у потребителю.
Из 2-го склада необходимо груз направить к 1-у потребителю (2), к 2-у потребителю (6)
Из 3-го склада необходимо груз направить к 1-у потребителю (2), к 4-у потребителю (8)
Потребность 3-го потребителя остается неудовлетворенной на 2 ед.
Оптимальный план является вырожденным, так как базисная переменная x43=0.
Задача имеет множество оптимальных планов, поскольку оценка для (3;3) равна 0.
Задача 28
Используя метод потенциалов найти оптимальный план перевозок. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей.
Поставщик |
В1 |
В2 |
В3 |
Запас |
А1 |
2 |
1 |
2 |
100 |
А2 |
5 |
7 |
6 |
200 |
А3 |
3 |
2 |
5 |
300 |
Потребности |
150 |
150 |
300 |
|
РЕШЕНИЕ:
Запишем экономико-математическую модель для нашей задачи.
Переменные:
x11 – количество груза из 1-го склада к 1-у потребителю. x12 – количество груза из 1-го склада к 2-у потребителю. x13 – количество груза из 1-го склада к 3-у потребителю. x21 – количество груза из 2-го склада к 1-у потребителю. x22 – количество груза из 2-го склада к 2-у потребителю. x23 – количество груза из 2-го склада к 3-у потребителю. x31 – количество груза из 3-го склада к 1-у потребителю. x32 – количество груза из 3-го склада к 2-у потребителю. x33 – количество груза из 3-го склада к 3-у потребителю.
Ограничения по запасам:
x11 + x12 + x13 ≤ 100 (для 1 базы) x21 + x22 + x23 ≤ 200 (для 2 базы) x31 + x32 + x33 ≤ 300 (для 3 базы)
Ограничения по потребностям:
x11 + x21 + x31 = 150 (для 1-го потребителя.) x12 + x22 + x32 = 150 (для 2-го потребителя.) x13 + x23 + x33 = 300 (для 3-го потребителя.)
Целевая функция:
2x11 + 1x12 + 2x13 + 5x21 + 7x22 + 6x23 + 3x31 + 2x32 + 5x33 → min
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
|
1 |
2 |
3 |
Запасы |
1 |
2 |
1 |
2 |
100 |
2 |
5 |
7 |
6 |
200 |
3 |
3 |
2 |
5 |
300 |
Потребности |
150 |
150 |
300 |
|
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 100 + 200 + 300 = 600
∑b = 150 + 150 + 300 = 600
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.
|
1 |
2 |
3 |
Запасы |
1 |
2 |
1 |
2 |
100 |
2 |
5 |
7 |
6 |
200 |
3 |
3 |
2 |
5 |
300 |
Потребности |
150 |
150 |
300 |
|
Этап I. Поиск первого опорного плана.
1. Используя метод северо-западного угла, построим первый опорный план транспортной
задачи.
План начинается заполняться с верхнего левого угла.
Искомый элемент равен c11=2. Для этого элемента запасы равны 100, потребности 150. Поскольку минимальным является 100, то вычитаем его.
x11 = min(100,150) = 100.
2 |
x |
x |
100 - 100 = 0 |
5 |
7 |
6 |
200 |
3 |
2 |
5 |
300 |
150 - 100 = 50 |
150 |
300 |
|
Искомый элемент равен c21=5. Для этого элемента запасы равны 200, потребности 50. Поскольку минимальным является 50, то вычитаем его.
x21 = min(200,50) = 50.
2 |
x |
x |
0 |
5 |
7 |
6 |
200 - 50 = 150 |
x |
2 |
5 |
300 |
50 - 50 = 0 |
150 |
300 |
|
Искомый элемент равен c22=7. Для этого элемента запасы равны 150, потребности 150. Поскольку минимальным является 150, то вычитаем его.
x22 = min(150,150) = 150.
2 |
x |
x |
0 |
5 |
7 |
x |
150 - 150 = 0 |
x |
2 |
5 |
300 |
0 |
150 - 150 = 0 |
300 |
|
Искомый элемент равен c33=5. Для этого элемента запасы равны 300, потребности 300. Поскольку минимальным является 300, то вычитаем его.
x33 = min(300,300) = 300.
2 |
x |
x |
0 |
5 |
7 |
x |
0 |
x |
2 |
5 |
300 - 300 = 0 |
0 |
0 |
300 - 300 = 0 |
|
Далее, согласно алгоритму, ищем элементы среди не вычеркнутых.
2 |
1 |
2 |
100 |
5 |
7 |
6 |
200 |
3 |
2 |
5 |
300 |
150 |
150 |
300 |
|
Искомый элемент равен c12=1, но т.к. ограничения выполнены, то x12=0.
|
1 |
2 |
3 |
Запасы |
1 |
2[100] |
1[0] |
2 |
100 |
2 |
5[50] |
7[150] |
6 |
200 |
3 |
3 |
2 |
5[300] |
300 |
Потребности |
150 |
150 |
300 |
|
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 5. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*100 + 5*50 + 7*150 + 5*300 = 3000
ОТВЕТ:
Анализ оптимального плана.
Из 1-го склада необходимо весь груз направить к 3-у потребителю.
Из 2-го склада необходимо весь груз направить к 3-у потребителю.
Из 3-го склада необходимо груз направить к 1-у потребителю (150), к 2-у потребителю (150)
Задача имеет множество оптимальных планов, поскольку оценка для (3;3) равна 0.
Задача 29
В трех пунктах отправления имеется однородный груз в количестве соответственно. Этот груз нужно доставить пяти заказчикам . Потребности в грузе в каждом пункте известны и равны соответственно. Известны также тарифы перевозки - стоимость перевозки единицы груза из пункта в пункт. Нужно найти такой план перевозок, при котором весь груз из пунктов потребления будет вывезен, потребности всех заказчиков будут удовлетворены, и при этом общая стоимость перевозки всего груза будет наименьшей. Данные в таблице, в клетках которой проставлены элементы матрицы тарифов ; в последнем столбце таблицы указаны значения величин , в последней строке - значения величин.
Заказчики/пункты |
В1 |
В2 |
В3 |
В4 |
В5 |
aj |
А1 |
4 |
9 |
2 |
5 |
3 |
23 |
А2 |
4 |
6 |
2 |
1 |
8 |
25 |
А3 |
6 |
2 |
3 |
4 |
5 |
17 |
bi |
14 |
10 |
16 |
10 |
15 |
|
Требуется: найти оптимальное решение транспортной задачи методом
потенциалов.
|
|
|
|
|
РЕШЕНИЕ: |
|
|
|
|
||
Обозначим через |
|
|
̅̅̅̅ |
̅̅̅̅ |
|
|
|
|
|
|
|
|
( = 1,3; = 1,5) количество груза, перевозимого от j-го поставщика j- |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
му потребителю. Тогда общая стоимость перевозок равна: |
|
|
|
||||||||
3 |
5 |
|
|
|
|
|
|
|
|
|
|
min = ∑ ∑ |
|
= 4 ∙ |
+ 9 ∙ |
+ 2 ∙ |
+ 5 ∙ |
+ 3 ∙ |
+ 4 ∙ |
+ 6 ∙ + 2 |
|||
|
|
|
|
11 |
12 |
13 |
|
14 |
15 |
21 |
22 |
=1 =1 |
|
|
|
|
|
|
|
|
|
|
|
|
∙ 23 + 24 + 8 ∙ 25 + 6 ∙ 31 + 2 ∙ 32 |
+ 3 ∙ 33 + 4 ∙ 34 + 5 ∙ 35 |
|||||||||
Ограничения для поставщиков:
11 + 12 + 13 + 14 + 15 = 23 − для 1 − го поставщика { 21 + 22 + 23 + 24 + 25 = 25 − для 2 − го поставщика31 + 32 + 33 + 34 + 35 = 17 − для 3 − го поставщика
Ограничения для потребителей:
11 + 21 + 31 = 14 − для 1 − го потребителя12 + 22 + 32 = 10 − для 2 − го потребителя13 + 23 + 33 = 16 − для 3 − го потребителя14 + 24 + 34 = 10 − для 4 − го потребителя { 15 + 25 + 35 = 15 − для 5 − го потребителя
Объем суммарных поставок любого поставщика к потребителю не может быть отрицательным числом, поэтому справедливы ограничения: ≥ 0.
Проверка задачи на закрытость модели
Стандартная транспортная задача разрешима только в том случае, когда выполняется условие баланса:
3 5
∑ = ∑
=1 =1
В нашем случае:
3 5
∑ = 65 ; ∑ = 65
=1 =1
Модель транспортной задачи закрытая.
Метод потенциалов
Решать задачу будем методом потенциалов. Число занятых клеток должно быть + − 1. Потенциал 1-й строки принимаем равным нулю. После этого мы можем вычислить остальные потенциалы (если известны потенциал и тариф занятой клетки, то из соотношения v + u =c легко определить неизвестный потенциал).
1 = 03 + 1 = 2 → 3 = 2 − 0 = 2
5 + 1 = 3 → 5 = 3 − 0 = 32 + 5 = 8 → 2 = 8 − 3 = 53 + 5 = 5 → 3 = 5 − 3 = 21 + 2 = 4 → 1 = 4 − 5 = −12 + 3 = 2 → 2 = 2 − 2 = 04 + 5 = 1 → 4 = 1 − 5 = −4
Найдем оценки свободных клеток по формуле: ( , ) = − ( + )(1,1) = 4 − (0 − 1) = 5(1,2) = 9 − (0 + 0) = 9(1,4) = 5 − (0 − 4) = 9(2,2) = 6 − (5 + 0) = 1(2,3) = 2 − (5 + 2) = −5(3,1) = 6 − (2 − 1) = 5(3,3) = 3 − (2 + 2) = −1(3,4) = 4 − (2 − 4) = 6
Для клетки (2, 3) с минимальной отрицательной оценкой строим цикл.
Перемещаем груз, равный 1 из вершин, помеченных минусом к вершинам цикла, помеченным плюсом.
Вычисляем потенциалы:
Для клетки (3, 3) с минимальной отрицательной оценкой строим цикл.
Перемещаем груз, равный 7 из вершин, помеченных минусом к вершинам цикла, помеченным плюсом.
Вычисляем потенциалы: