Файл: Содержание Теоретический раздел 4.doc

Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

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 = ∑∑c_ijx_ij, (1)

при условиях:

∑x_ij = a_i, i = 1,2,…, m, (2)

∑x_ij = b_j, 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. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 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

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Выбираем максимальную оценку свободной клетки (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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 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

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Выбираем максимальную оценку свободной клетки (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

---