Математическое моделирование

 

Конец итераций: индексная  строка не содержит отрицательных элементов - найден оптимальный план

Окончательный вариант симплекс-таблицы:

Базис	В	x1	x2	x3	x4	x5	x6
x4	164.29	0	0.0714	0	1	0.21	-1.14
x3	64.29	0	0.0714	1	0	0.21	-0.14
x1	57.14	1	1.29	0	0	-0.14	0.43
F(X3)	542.86	0	3.71	0	0	0.14	1.57

Оптимальный план можно записать так:

x₄ = 164.29

x₃ = 64.29

x₁ = 57.14

F(X) = 5*57.14 + 4*64.29 = 542.86

Задание 3.  К прямой задаче линейного программирования, полученной при выполнении задания 2, составить двойственную задачу. Найти оптимальный план двойственной задачи из решения прямой.

Составим двойственную задачу к прямой задаче.

3y₁ + 2y₂ + 3y₃≥5

4y₁ + 3y₂ + 4y₃≥3

y₁ + 6y₂ + 2y₃≥4

400y₁ + 500y₂ + 300y₃ → min

y₁ ≥ 0

y₂ ≥ 0

y₃ ≥ 0

Решение двойственной задачи дает оптимальную систему оценок ресурсов.

Используя последнюю итерацию прямой задачи, найдем оптимальный план двойственной задачи.

Из теоремы двойственности следует, что Y = C*A^-1.

Составим матрицу A из компонентов  векторов, входящих в оптимальный  базис.

 

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

 

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.

Тогда Y = C*A^-1 =

 

Оптимальный план двойственной задачи равен:

y₁ = 0

y₂ = ¹/₇

y₃ = 1⁴/₇

Z(Y) = 400*0+500*¹/₇+300*1⁴/₇ = 542⁶/₇

Задание 4. Имеется три завода, объем производства которых соответственно равен тонн в сутки. Эти заводы ежедневно удовлетворяют потребности четырех строительных объектов в количествах тонн в сутки соответственно. Стоимость перевозки (тыс.руб.) перевозки единицы продукции с каждого завода на каждый строительный объект задана матрицей тарифов С=(С_ij), i=1..4, j=1..3. Найти такой план транспортировки груза, чтобы общие затраты на перевозки грузов были минимальными.

Математическая модель транспортной задачи:

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	Запасы
1	1	5	4	2	30
2	12	10	16	8	40
3	4	13	14	10	80
Потребности	20	70	10	50

Проверим необходимое  и достаточное условие разрешимости задачи.

∑a = 30 + 40 + 80 = 150

∑b = 20 + 70 + 10 + 50 = 150

Этап I. Поиск первого  опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

 

 

	1	2	3	4	Запасы
1	1[20]	5	4	2[10]	30
2	12	10	16	8[40]	40
3	4	13[70]	14[10]	10	80
Потребности	20	70	10	50

2. Подсчитаем число занятых  клеток таблицы, их 5, а должно  быть m + n - 1 = 6. Следовательно, опорный план является вырожденным.

Строим новый план.

	1	2	3	4	Запасы
1	1	5	4	2[30]	30
2	12	10[20]	16	8[20]	40
3	4[20]	13[50]	14[10]	10	80
Потребности	20	70	10	50

В результате получен первый опорный план, который является допустимым, так как все грузы из баз  вывезены, потребность магазинов  удовлетворена, а план соответствует  системе ограничений транспортной задачи.

2. Подсчитаем число занятых  клеток таблицы, их 6, а должно  быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

Этап II. Улучшение  опорного плана.

Проверим оптимальность  опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=-5	v2=4	v3=5	v4=2
u1=0	1	5	4	2[30]
u2=6	12	10[20]	16	8[20]
u3=9	4[20]	13[50]	14[10]	10

 

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

Выбираем максимальную оценку свободной клетки (1;3): 4

Для этого в перспективную  клетку (1;3) поставим знак «+», а в  остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	1	5	4[+]	2[30][-]	30
2	12	10[20][-]	16	8[20][+]	40
3	4[20]	13[50][+]	14[10][-]	10	80
Потребности	20	70	10	50

Цикл приведен в таблице (1,3; 1,4; 2,4; 2,2; 3,2; 3,3; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	1	5	4[10]	2[20]	30
2	12	10[10]	16	8[30]	40
3	4[20]	13[60]	14	10	80
Потребности	20	70	10	50

Проверим оптимальность  опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=-5	v2=4	v3=4	v4=2
u1=0	1	5	4[10]	2[20]
u2=6	12	10[10]	16	8[30]
u3=9	4[20]	13[60]	14	10

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

Выбираем максимальную оценку свободной клетки (3;4): 10

Для этого в перспективную  клетку (3;4) поставим знак «+», а в  остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	1	5	4[10]	2[20]	30
2	12	10[10][+]	16	8[30][-]	40
3	4[20]	13[60][-]	14	10[+]	80
Потребности	20	70	10	50

Цикл приведен в таблице (3,4; 3,2; 2,2; 2,4; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	1	5	4[10]	2[20]	30
2	12	10[40]	16	8	40
3	4[20]	13[30]	14	10[30]	80
Потребности	20	70	10	50

 

Проверим оптимальность  опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=-4	v2=5	v3=4	v4=2
u1=0	1	5	4[10]	2[20]
u2=5	12	10[40]	16	8
u3=8	4[20]	13[30]	14	10[30]