Контрольная работа по дисциплине «Методы оптимальных решений»

Вычислим значения Di по строкам как частное от деления: bi / ai1  и из них выберем наименьшее: min (- , 9 : 1/2 , 12 : 2 ) = 6

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x2	8	0	1	0	1	2	0	-
x3	9	1/2	0	1	1	21/2	0	18
x6	12	2	0	0	0	1	1	6
F(X3)	-32	2	0	0	-3	-10	0	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x6 в план 3 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 3, получена в результате деления всех элементов строки x6 плана 2 на разрешающий элемент РЭ=2

На месте разрешающего элемента в плане 3 получаем 1.

В остальных клетках столбца x1 плана 3 записываем нули.

Таким образом, в новом плане 3 заполнены строка x1 и столбец x1.

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

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6
x2	8	0	1	0	1	2	0
x3	6	0	0	1	1	9/4	-1/4
x1	6	1	0	0	0	1/2	1/2
F(X3)	-44	0	0	0	-3	-11	-1

1. Проверка критерия оптимальности.

Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.

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

x2 = 8   x3 = 6   x1 = 6    F(X) = 5•8 -8•6 -6•6 = -44

 

 

Задание 3

Составьте оптимальный план перевозки грузов от поставщиков с грузами 160, 60, 180 т к потребителям с запросами 80, 60, 60 и 200 т. Стоимости перевозок единицы груза от каждого поставщика к каждому потребителю даны матрицей

Решение

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

∑a = 160 + 60 + 180 = 400

∑b = 80 + 60 + 60 + 200 = 400

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

	1	2	3	4	Запасы
1	8	6	9	2	160
2	7	16	12	12	60
3	6	15	8	3	180
Потребности	80	60	60	200

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

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

План начинается заполняться с верхнего левого угла.

Искомый элемент равен 8

Для этого элемента запасы равны 160, потребности 80. Поскольку минимальным является 80, то вычитаем его.

x11 = min(160,80) = 80.

8	6	9	2	160 - 80 = 80
x	16	12	12	60
x	15	8	3	180
80 - 80 = 0	60	60	200	0

 

Искомый элемент равен 6

Для этого элемента запасы равны 80, потребности 60. Поскольку минимальным является 60, то вычитаем его.

x12 = min(80,60) = 60.

8	6	9	2	80 - 60 = 20
x	x	12	12	60
x	x	8	3	180
0	60 - 60 = 0	60	200	0

Искомый элемент равен 9

Для этого элемента запасы равны 20, потребности 60. Поскольку минимальным является 20, то вычитаем его.

x13 = min(20,60) = 20.

8	6	9	x	20 - 20 = 0
x	x	12	12	60
x	x	8	3	180
0	0	60 - 20 = 40	200	0

 

Искомый элемент равен 12

Для этого элемента запасы равны 60, потребности 40. Поскольку минимальным является 40, то вычитаем его.

x23 = min(60,40) = 40.

8	6	9	x	0
x	x	12	12	60 - 40 = 20
x	x	x	3	180
0	0	40 - 40 = 0	200	0

Искомый элемент равен 12

Для этого элемента запасы равны 20, потребности 200. Поскольку минимальным является 20, то вычитаем его.

x24 = min(20,200) = 20.

8	6	9	x	0
x	x	12	12	20 - 20 = 0
x	x	x	3	180
0	0	0	200 - 20 = 180	0

Искомый элемент равен 3

Для этого элемента запасы равны 180, потребности 180. Поскольку минимальным является 180, то вычитаем его.

x34 = min(180,180) = 180.

8	6	9	x	0
x	x	12	12	0
x	x	x	3	180 - 180 = 0
0	0	0	180 - 180 = 0	0

 

 

	1	2	3	4	Запасы
1	8[80]	6[60]	9[20]	2	160
2	7	16	12[40]	12[20]	60
3	6	15	8	3[180]	180
Потребности	80	60	60	200

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

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

Значение целевой функции для этого опорного плана равно:

F(x) = 8*80 + 6*60 + 9*20 + 12*40 + 12*20 + 3*180  = 2440

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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 8; 0 + v1 = 8; v1 = 8

u1 + v2 = 6; 0 + v2 = 6; v2 = 6

u1 + v3 = 9; 0 + v3 = 9; v3 = 9

u2 + v3 = 12; 9 + u2 = 12; u2 = 3

u2 + v4 = 12; 3 + v4 = 12; v4 = 9

u3 + v4 = 3; 9 + u3 = 3; u3 = -6

	v1=8	v2=6	v3=9	v4=9
u1=0	8[80]	6[60]	9[20]	2
u2=3	7	16	12[40]	12[20]
u3=-6	6	15	8	3[180]

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

(1;4): 0 + 9 > 2; ∆14 = 0 + 9 - 2 = 7

(2;1): 3 + 8 > 7; ∆21 = 3 + 8 - 7 = 4

max(7,4) = 7

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

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

	1	2	3	4	Запасы
1	8[80]	6[60]	9[20][-]	2[+]	160
2	7	16	12[40][+]	12[20][-]	60
3	6	15	8	3[180]	180
Потребности	80	60	60	200