ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 28.04.2024
Просмотров: 25
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:
1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.
2. Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами.
3. Матрица ограничений задачи А транспонируется.
4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче определяют номера ограничений, имеющих форму неравенств в двойственной задаче .
5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче .
Из приведенного определения вытекает важное свойство — симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей.
((D*)*, (f*)*)≡(D, f),
Основные теоремы:
Теорема 1. Если одна из двойственных задач имеет конечный оптимум, то другая также имеет конечный оптимум, причем экстремальные значения целевых функций совпадают
Теорема 2 ( о дополняющей нежесткости). Для того чтобы план х* и у* являлись оптимальными решениями соответственно задач линейного программирования и двойственной к ним необходимо и достаточно, чтобы выполнялись следующие соотношения:
Теорема 3 (об оценках). Значение переменных в оптимальном решении двойственной задачи представляет собой оценки влияния свободных членов bi в системе ограничения прямой задачи на величину целевой функции f(x*)
2. Практический раздел
2.1 Решение транспортной задачи
На три базы: А1, А2, А3 поступил однородный груз в количествах : 120,150,100, соответственно. Груз требуется перевезти в пять пунктов:85 в пункт B1, 65 в пункт В2, 90 в пункт В3, 60 в пункт В4, 70 в пункт В5.
Спланировать перевозки так, чтобы общая их стоимость была минимальной.
Пункт отправления | В1 | В2 | В3 | В4 | В5 | Запасы, аi |
A1 | 7 | 4 | 15 | 9 | 14 | 120 |
A2 | 11 | 2 | 7 | 3 | 10 | 150 |
A3 | 4 | 5 | 12 | 8 | 17 | 100 |
Потребности,bj | 85 | 65 | 90 | 60 | 70 | 370 |
Решение:
Математическая модель транспортной задачи:
F = ∑∑cijxij, (1)
при условиях:
∑xij = ai, i = 1,2,…, m, (2)
∑xij = bj, j = 1,2,…, n, (3)
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
| 1 | 2 | 3 | 4 | 5 | Запасы |
1 | 7 | 4 | 15 | 9 | 14 | 120 |
2 | 11 | 2 | 7 | 2 | 10 | 150 |
3 | 4 | 5 | 12 | 8 | 17 | 100 |
Потребности | 85 | 65 | 90 | 60 | 70 | |
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 120 + 150 + 100 = 370
∑b = 85 + 65 + 90 + 60 + 70 = 370
Занесем исходные данные в распределительную таблицу.
| 1 | 2 | 3 | 4 | 5 | Запасы |
1 | 7 | 4 | 15 | 9 | 14 | 120 |
2 | 11 | 2 | 7 | 2 | 10 | 150 |
3 | 4 | 5 | 12 | 8 | 17 | 100 |
Потребности | 85 | 65 | 90 | 60 | 70 | |
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
| 1 | 2 | 3 | 4 | 5 | Запасы |
1 | 7 | 4 | 15[50] | 9 | 14[70] | 120 |
2 | 11 | 2[65] | 7[25] | 2[60] | 10 | 150 |
3 | 4[85] | 5 | 12[15] | 8 | 17 | 100 |
Потребности | 85 | 65 | 90 | 60 | 70 | |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы
, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
| v1=7 | v2=10 | v3=15 | v4=10 | v5=14 |
u1=0 | 7 | 4 | 15[50] | 9 | 14[70] |
u2=-8 | 11 | 2[65] | 7[25] | 2[60] | 10 |
u3=-3 | 4[85] | 5 | 12[15] | 8 | 17 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (1;2): 4
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| 1 | 2 | 3 | 4 | 5 | Запасы |
1 | 7 | 4[+] | 15[50][-] | 9 | 14[70] | 120 |
2 | 11 | 2[65][-] | 7[25][+] | 2[60] | 10 | 150 |
3 | 4[85] | 5 | 12[15] | 8 | 17 | 100 |
Потребности | 85 | 65 | 90 | 60 | 70 | |
Цикл приведен в таблице (1,2; 1,3; 2,3; 2,2; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | 5 | Запасы |
1 | 7 | 4[50] | 15 | 9 | 14[70] | 120 |
2 | 11 | 2[15] | 7[75] | 2[60] | 10 | 150 |
3 | 4[85] | 5 | 12[15] | 8 | 17 | 100 |
Потребности | 85 | 65 | 90 | 60 | 70 | |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
| v1=1 | v2=4 | v3=9 | v4=4 | v5=14 |
u1=0 | 7 | 4[50] | 15 | 9 | 14[70] |
u2=-2 | 11 | 2[15] | 7[75] | 2[60] | 10 |
u3=3 | 4[85] | 5 | 12[15] | 8 | 17 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (2;5): 10
Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| 1 | 2 | 3 | 4 | 5 | Запасы |
1 | 7 | 4[50][+] | 15 | 9 | 14[70][-] | 120 |
2 | 11 | 2[15][-] | 7[75] | 2[60] | 10[+] | 150 |
3 | 4[85] | 5 | 12[15] | 8 | 17 | 100 |
Потребности | 85 | 65 | 90 | 60 | 70 | |