Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.
Расширенная матрица A.
14 4 252
4 14 120
2 12 240
30 40
Транспонированная матрица AT.
14 4 2 30
4 14 12 40
252 120 240
Неравенства, соединенные стрелочками (↔), называются сопряженными.
Исходная задача I
Двойственная задача II
x1 ≥ 0 ↔ 14y1+4y2+2y3≥30
x2 ≥ 0 ↔ 4y1+14y2+12y3≥40
30x1+40x2 → max
↔ 252y1+120y2+240y3 → min
14x1+4x2≤252 ↔ y1 ≥ 0
4x1+14x2≤120 ↔ y2 ≥ 0
2x1+12x2≤240 ↔ y3 ≥ 0
Имеем двойственную задачу:
Z(y)=252y1+120y2+240y3 → min
14y1+4y2+2y3≥304y1+14y2+12y3≥40y1 ≥ 0y2 ≥ 0y3 ≥ 0
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
y1=14/9, y2=24/9, y3=0
Это же решение можно получить, применив теоремы двойственности.
Из теоремы двойственности следует, что Y = C∙A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
A = (A1, A2, A5) = 14 4 0
4 14 0
2 12 1
Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
D = A-1 = 7/90 -1/45 0
-1/45 7/90 0
1/9 -8/9 1
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных.
Тогда Y = C∙A-1 =(30, 40, 0) x 7/90 -1/45 0
-1/45 7/90 0
1/9 -8/9 1
= (13/9;22/9;0)
Оптимальный план двойственной задачи равен:
y1 = 14/9, y2 = 24/9, y3 = 0.
Z(Y) = 252∙14/9+120∙24/9+240∙0 = 6571/3.
2) На трех станциях отправления сосредоточен однородный груз, который следует перевезти в четыре пункта назначения, имеющих потребность в этом грузе. Стоимость перевозок единицы груза от каждой станции до каждого пункта назначения считается известной и содержится в таблице. Требуется составить такой план перевозок, при котором их общая стоимость окажется минимальной.
Решить транспортную задачу методом потенциалов.
поставщик потребитель Запасы груза
В1 В2 В3 В4
А1 10 14 2 12 12
А2 8 4 9 7 18
А3 6 25 3 8 20
потребность 15 15 10 10
Нужно полное решение этой работы?
Решение
Проверим необходимое и достаточное условие разрешимости задачи.∑a = 12 + 18 + 20 = 50∑b = 15 + 15 + 10 + 10 = 50
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен c13=2
. Для этого элемента запасы равны 12, потребности 10. Поскольку минимальным является 10, то вычитаем его.x13 = min(12,10) = 10.
10 14 2 12 12 - 10 = 2
8 4 x 7 18
6 25 x 8 20
15 15 10 - 10 = 0 10
Искомый элемент равен c22=4. Для этого элемента запасы равны 18, потребности 15. Поскольку минимальным является 15, то вычитаем его.x22 = min(18,15) = 15.
10 x 2 12 2
8 4 x 7 18 - 15 = 3
6 x x 8 20
15 15 - 15 = 0 0 10
Искомый элемент равен c31=6. Для этого элемента запасы равны 20, потребности 15. Поскольку минимальным является 15, то вычитаем его.x31 = min(20,15) = 15.
x x 2 12 2
x 4 x 7 3
6 x x 8 20 - 15 = 5
15 - 15 = 0 0 0 10
Искомый элемент равен c24=7. Для этого элемента запасы равны 3, потребности 10. Поскольку минимальным является 3, то вычитаем его.x24 = min(3,10) = 3.
x x 2 12 2
x 4 x 7 3 - 3 = 0
6 x x 8 5
0 0 0 10 - 3 = 7
Искомый элемент равен c34=8. Для этого элемента запасы равны 5, потребности 7
Задать вопрос
на новый заказ в Автор24.
