Каноническая, транспортная, сетевая задача и задача о назначениях

Размещено на http://www.allbest.ru/

Содержание

транспортная задача матрица назначение

1. Задача №1

2. Задача №2 (каноническая задача)

3. Задача №3 (транспортная задача)

4. Задача №4 (сетевая задача)

5. Задача №5 (задача о назначениях)

Задача № 1

Условно стандартная задача линейного программирования

Необходимо выполнить в указанном порядке следующие задания.

1. Найти оптимальный план прямой задачи:

а) графическим методом;

б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).

2. Построить двойственную задачу.

3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.

4. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».

5. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, который был получен графическим методом (см. п. 1а).

6. Найти оптимальное целочисленное решение:

а) графическим методом;

б) Методом Гомори.

Сравнить значения функций целочисленного и нецелочисленного решений.

Решение

1а) Изобразим на плоскости систему координат Ох1х2 и построим граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе) :

Область допустимых решений определяется многоугольником ОАВСD (рис. 1).

Для линий уровня 7х1 - 4х2 = h (h - const) строим нормальный вектор . Перпендикулярно нормальному вектору построим одну из линий уровня (на рис. 1 она проходит через начало координат) Так как задача на минимум, то перемещаем линию уровня в направлении, противоположном направлению вектора до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L1 и L2, т. е. через точку . Для определения координат точки В решаем систему уравнений

Получаем х1 = 13 / 14, х2 = 47 / 7. Это и будет оптимальным решением данной задачи, которому соответствует максимальное значение целевой функции Zmax:

.

Рис. 1 - Решение системы неравенств графическим образом

1б) Решим задачу симплекс-методом.

Для получения системы уравнений вводим дополнительные переменные х3, х4, х5, х6:

В 4 уравнение добавляем искусственную переменную R1 ? 0. Получим так называемую М-задачу:

при ограничениях:

Данная система является системой с базисом, в которой х3, х4, х5 и R1 - базисные переменные, а x1, x2, х6 свободные переменные, свободные члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:

Таблица 1

Базис	Свободн. коэфф-т	х1	х2v	х3	х4	х5	х6	R1
Х3 >	3	-4	1	1	0	0	0	0
х4	88	8	12	0	1	0	0	0
х5	25	3	-14	0	0	1	0	0
R1	28	5	6	0	0	0	-1	1
Z (x)		-7	4	0	0	0	0	0
строка оценок		5	6	0	0	0	-1	1

В таблицу добавлена строка «Строка оценок». Она соответствует коэффициентам строки с искусственной переменной (R1). Она будет присутствовать в таблице до тех пор, пока искусственная переменная есть в базисе.

Первое опорное решение:

Т. к. в строке оценок есть положительные числа, то преобразуем исходную таблицу. В строке оценок ищем максимальное по модулю положительное число. Это число 6, оно стоит в столбце х2. Значит, х2 - ведущий столбец. Теперь найдем отношение свободных членов к положительным элементам ведущего столбца и выберем минимальное.

Минимальное число оказалось в строке х3, это ведущая строка. На пересечении ведущего столбца и ведущей строки находится ведущий элемент.

Запишем новую таблицу, в которой базисом являются переменные х2, х4, х5, R1.

Таблица 2

Базис	Свободн. коэфф-т	х1v	х2	х3	х4	х5	х6	R1
х2	3	-4	1	1	0	0	0	0
х4	52	56	0	-12	1	0	0	0
х5	67	-53	0	14	0	1	0	0
R1>	10	29	0	-6	0	0	-1	1
Z (x)	-12	9	0	-4	0	0	0	0
строка оценок		29	0	6	0	0	1	-1

Второе опорное решение:

Т. к. в строке оценок есть положительные числа, то преобразуем исходную таблицу. В строке оценок ищем максимальное по модулю положительное число. Это число 29, оно стоит в столбце х1. Значит, х1 - ведущий столбец. Теперь найдем отношение свободных членов к положительным элементам ведущего столбца и выберем минимальное.

Минимальное число оказалось в строке R1, это ведущая строка. На пересечении ведущего столбца и ведущей строки находится ведущий элемент.

Запишем новую таблицу, в которой базисом являются переменные х2, х4, х5, х1.

Т. к. в базисе не остается искусственных переменных, то «строки оценок» в следующей таблице нет.

Таблица 3

Базис	Свободн. коэфф-т	х1	х2	х3	х4	х5	х6v	R1
х2	4 11/29	0	1	5/29	0	0	- 4/29	4/29
х4>	32 20/29	0	0	- 12/29	1	0	1 27/29	-1 27/29
х5	85 8/29	0	0	3 1/29	0	1	-1 24/29	1 24/29
х1	10/29	1	0	- 6/29	0	0	- 1/29	1/29
Z (x)	-15 3/29	0	0	-2 4/29	0	0	9/29	- 9/29

Третье опорное решение:

Т. к. в строке оценок есть положительные числа, то преобразуем исходную таблицу. В строке оценок ищем максимальное по модулю положительное число. Это число 9/29, оно стоит в столбце х6. Значит, х6 - ведущий столбец. Теперь найдем отношение свободных членов к положительным элементам ведущего столбца и выберем минимальное.

Минимальное число оказалось в строке х4, это ведущая строка. На пересечении ведущего столбца и ведущей строки находится ведущий элемент.

Запишем новую таблицу, в которой базисом являются переменные х2, х6, х5, х1.

Таблица 4

Базис	Свободн. коэфф-т	х1	х2	х3	х4	х5	х6	R1
х2	6 5/7	0	1	1/7	1/14	0	0	0
х6	16 13/14	0	0	- 3/14	29/56	0	1	-1
х5	116 3/14	0	0	2 9/14	53/56	1	0	0
х1	13/14	1	0	- 3/14	1/56	0	0	0
Z (x)	-20 5/14	0	0	-2 1/14	- 9/56	0	0	0

Четвертое опорное решение:

Это решение является оптимальным, т. к. в строке оценок нет положительных чисел.

Zmin = -20 5/14.

2) Построим двойственную задачу.

Так как исходная задача на минимизацию, то приведём все неравенства системы ограничений к виду «>«, для чего обе части 1, 2 и 3 неравенства умножим на (1). Получим



Составим расширенную матрицу системы

.

Найдём матрицу , транспонированную к А

.

Сформулируем двойственную задачу:

при ограничениях:

3. Найдем оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.

Решение исходной задачи х1 = , х2 =, х3 = 0, х4 = 0, х5 = , х6 =

Подставим оптимальное решение Х* в систему ограничений. Получим, что первое и второе ограничения выполняются как строгие неравенства:

По второй теореме двойственности следует, что соответствующие координаты оптимального решения исходной задачи, т. е. двойственной задачи равны нулю: .

Рассмотрим ограничения двойственной задачи. Каждое их них соответствует одной из переменных исходной задачи. Поскольку х1*>0, х2*>0, то оба ограничения двойственной задачи обращаются в верное равенство при подстановке в них оптимального плана y*. Учитывая, что , можем записать систему из двух уравнений с двумя неизвестными:

Решая систему, получим: y1*= , y2*=

Полностью решение двойственной задачи запишется так:

= (; ; 0; 0) ; = -3*-88* = - 20.

4. Найдем оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи. Проверим утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».

Находим оптимальное решение двойственной задачи

.

Т. о., получили решение y1*= , y2*= , y3* = 0, y4* = 0

Проверим правильность нахождения двойственных оценок: g = -3* () -88* () = - 20

Таким образом, Zmin = gmax = - 20д. ед.

5. Двойственную задачу решим симплекс-методом.

Имеем двойственную задачу:

при ограничениях:

Для получения системы уравнений вводим дополнительные переменные y5, y6:

Во второе уравнение добавляем искусственную переменную R2 ? 0. Получим М-задачу:

при ограничениях:

Данная система является системой с базисом, в которой y5 и R2 - базисные переменные, а y1, y2, y3, y4 и y6 свободные переменные, свободные члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:

Таблица 5

Базис	Свободн. коэфф-т	Y1	y2v	y3	y4	y5	y6	R2
y5	7	4	-8	-3	5	1	0	0
R2>	4	1	12	-14	-6	0	-1	1
g (y)	0	3	88	25	-28	0	0	0
строка оценок		-1	-12	14	6	0	1	-1

В таблицу добавлена строка «Строка оценок». Она соответствует коэффициентам строки с искусственной переменной (R2) с обратным знаком. Она будет присутствовать в таблице до тех пор, пока искусственная переменная есть в базисе.

Первое опорное решение:

Т. к. в строке оценок есть отрицательные числа, то преобразуем исходную таблицу. В строке оценок ищем максимальное по модулю отрицательное число. Это число -12, оно стоит в столбце y2. Значит, y2 - ведущий столбец. Единственное положительное число стоит в строке R2, это ведущая строка. На пересечении ведущего столбца и ведущей строки находится ведущий элемент.

Запишем новую таблицу, в которой базисом являются переменные y5, y2. Т. к. в базисе не остается искусственных переменных, то «строки оценок» в следующей таблице нет.

Таблица 6

Базис	Свободн. коэфф-т	y1v	y2	y3	y4	y5	y6	R2
y5>	9 2/3	4 2/3	0	-12 1/3	1	1	- 2/3	2/3
y2	1/3	1/12	1	-1 1/6	- 1/2	0	- 1/12	1/12
g (y)	-29 1/3	-4 1/3	0	127 2/3	16	0	7 1/3	-7 1/3

Второе опорное решение: . Оно также не оптимально, т. к. в строке оценок есть отрицательные числа.

Далее разрешающий столбец выбирается по g (y) -строке. В g (y) -строке максимальный по модулю отрицательный коэффициент стоит в столбце y1. Значит, это ведущий столбец.

Теперь найдем отношение свободных членов к положительным элементам ведущего столбца и выберем минимальное.

. Значит, y5 - ведущая строка. На пересечении ведущего столбца и ведущей строки находится ведущий элемент.

Поэтому строим новую таблицу с базисом y1, y2.

Таблица 7

Базис	Свободн. коэфф-т	y1v	y2	y3	y4	y5	y6	R2
y1	2 1/14	1	0	-2 9/14	3/14	3/14	- 1/7	1/7
y2	9/56	0	1	- 53/56	- 29/56	- 1/56	- 1/14	1/14
g (y)	-20 5/14	0	0	116 3/14	16 13/14	13/14	6 5/7	-6 5/7

Третье опорное решение:

Это решение является оптимальным, т. к. в строке оценок нет отрицательных чисел.

gmin= -20 5/14,

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

.

Т. о., получили решение х1*= , х2*= . Это решение соответствует полученному в п. 1 при решении графическим способом.

6. Найдем оптимальное целочисленное решение:

а) графическим методом;

б) Методом Гомори.

а)

Рис. 1 - Решение системы неравенств графическим образом

Непрерывный оптимум находится в т. А (; ), для которой Z (X) = -20 5/14.

Изучая точки с целыми координатами внутри области допустимых решений ОАВСD решений, мы констатируем, что целочисленный оптимум есть точка с координатами x1 = 1, x2 = 6, и Z (X) = 7*1-4*6 = -17, т. к. эта точка ближе всего расположена к оптимальному решению.

б) Найдем оптимальное целочисленное решение методом Гомори.

Перенесем последнюю симплекс таблицу, полученную в п. 1б)

Базис	Свободн. коэфф-т	х1	х2	х3	х4	х5	х6
х2	6 5/7	0	1	1/7	1/14	0	0
х6	16 13/14	0	0	- 3/14	29/56	0	1
х5	116 3/14	0	0	2 9/14	53/56	1	0
х1	13/14	1	0	- 3/14	1/56	0	0
Z (x)	-20 5/14	0	0	-2 1/14	- 9/56	0	0

.

Zmin = -20 5/14.

Наибольшая дробная часть свободного члена у переменной х6, поэтому по этой переменной составляем дополнительное ограничение:

q6-q61*x1-q62*x2-q63*x3-q64*x4-q65*x5 - q66*x6 < 0

q6 = b6 - [b6] = 16 13/14 - 16 = 13/14

q61 = a61 - [a61] = 0 - 0 = 0

q62 = a62 - [a62] = 0 - 0 = 0

q63 = a63 - [a61] = -3/14 + 1 = 11/14

q64 = a64 - [a64] = 29/56 - 0 = 29/56

q65 = a65 - [a65] = 0 - 0 = 0

q66 = a66 - [a66] = 1 - 1 = 0

Дополнительное ограничение имеет вид:

13/14 - 11/14*x3 - 29/56*x4 < 0

Преобразуем полученное неравенство в уравнение:

13/14 - 11/14*x3 - 29/56*x4 +х7 = 0, коэффициенты которого введем дополнительной строкой в оптимальную симплекс-таблицу:

Таблица 8

Базис	Свободн. коэфф-т	х1	х2	х3	х4v	х5	х6	х7
х2	6 5/7	0	1	1/7	1/14	0	0	0
х6	16 13/14	0	0	- 3/14	29/56	0	1	0
х5	116 3/14	0	0	2 9/14	53/56	1	0	0
х1	13/14	1	0	- 3/14	1/56	0	0	0
х7>	- 13/14	0	0	- 11/14	- 29/56	0	0	1
Z (x)	-20 5/14	0	0	-2 1/14	- 9/56	0	0	0

Применяя алгоритм двойственного симплекс-метода, проводим итерацию, в результате которой получаем следующую таблицу:

Таблица 9

Базис	Свободн. коэфф-т	х1	х2	х3	х4	х5	х6	х7
х2	6 17/29	0	1	1/29	0	0	0	4/29
х6	16	0	0	-1	0	0	1	1
х5	114 15/29	0	0	1 6/29	0	1	0	1 24/29
х1	26/29	1	0	- 7/29	0	0	0	1/29
x4	1 23/29	0	0	1 15/29	1	0	0	-1 27/29
Z (x)	-20 2/29	0	0	-1 24/29	0	0	0	- 9/29

Вводим новую переменную х8: 26/29 - 22/29*x3 - 1/29*x7 +х8 = 0

Таблица 10

Базис	Свободн. коэфф-т	х1	х2	х3	х4	х5	х6	х7	х8
х2	6 17/29	0	1	1/29	0	0	0	4/29	0
х6	16	0	0	-1	0	0	1	1	0
х5	114 15/29	0	0	1 6/29	0	1	0	1 24/29	0
х1	26/29	1	0	- 7/29	0	0	0	1/29	0
x4	1 23/29	0	0	1 15/29	1	0	0	-1 27/29	0
х8	- 26/29	0	0	- 22/29	0	0	0	- 1/29	1
Z (x)	-20 2/29	0	0	-1 24/29	0	0	0	- 9/29	0

Выведем из базиса переменную х8 и введем х3:

Таблица 11

Базис	Свободн. коэфф-т	х1	х2	х3	х4	х5	х6	х7	х8
х2	6 6/11	0	1	0	0	0	0	3/22	1/22
х6	17 2/11	0	0	0	0	0	1	1 1/22	-1 7/22
х5	113 1/11	0	0	0	0	1	0	1 17/22	1 13/22
х1	1 2/11	1	0	0	0	0	0	1/22	- 7/22
x4	0	0	0	0	1	0	0	-2	2
х3	1 2/11	0	0	1	0	0	0	1/22	-1 7/22
Z (x)	-17 10/11	0	0	0	0	0	0	- 5/22	-2 9/22

Вводим новую переменную х9: 6/11 - 3/22*x7 - 1/22*x8 +х9 = 0

Таблица 12

Базис	Свободн. коэфф-т	х1	х2	х3	х4	х5	х6	х7	х8	х9
х2	6 6/11	0	1	0	0	0	0	3/22	1/22	0
х6	17 2/11	0	0	0	0	0	1	1 1/22	-1 7/22	0
х5	113 1/11	0	0	0	0	1	0	1 17/22	1 13/22	0
х1	1 2/11	1	0	0	0	0	0	1/22	- 7/22	0
x4	0	0	0	0	1	0	0	-2	2	0
х3	1 2/11	0	0	1	0	0	0	1/22	-1 7/22	0
х9	- 6/11	0	0	0	0	0	0	- 3/22	- 1/22	1
Z (x)	-17 10/11	0	0	0	0	0	0	- 5/22	-2 9/22	0

Выведем из базиса переменную х9 и введем х7:

Таблица 13

Базис	Свободн. коэфф-т	х1	х2	х3	х4	х5	х6	х7	х8	х9
х2	6	0	1	0	0	0	0	0	0	1
х6	13	0	0	0	0	0	1	0	-1 2/3	7 2/3
х5	106	0	0	0	0	1	0	0	1	13
х1	1	1	0	0	0	0	0	0	- 1/3	1/3
x4	8	0	0	0	1	0	0	0	2 2/3	-14 2/3
х3	1	0	0	1	0	0	0	0	-1 1/3	1/3
х7	4	0	0	0	0	0	0	1	1/3	-7 1/3
Z (x)	-17	0	0	0	0	0	0	0	-2 1/3	-1 2/3

Получили целочисленное решение Х* = (1; 6; 1; 8; 106; 13; 4; 0; 0). Zmin (x) = -17. Значения функций целочисленного и нецелочисленного решений отличаются на 20 5/14 - 17 = 3 5/14.

Задача № 2

Каноническая задача

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

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

Необходимо последовательно выполнить следующие задания.

Задачу решить графическим методом.

Применяя симплекс-метод, решить задачу, т. е. найти ее оптимальный план и минимальное значение целевой функции или установить, что задача не имеет решения. Начальный план рекомендуется искать методом искусственного базиса.

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

Провести анализ полученного решения, применяя условия дополняющей нежесткости.

Если , то .

Если , то .

3	9	-4	-11	-2	min
5	9	-2	11	6	19
2	1	4	15	10	17
3	7	2	-1	8	21

Решение

при ограничениях:

1. Проверяем, применим ли графический метод при решении данной задачи. Нетрудно видеть, что любые два из векторов-условий, например

линейно независимы, так как их координаты непропорциональны. Поэтому ранг системы векторов-условий r = 3. Находим n r = 5 3 = 2 2. Следовательно, метод применим.

Приведём систему уравнений-ограничений к равносильной, разрешённой методом Жордана-Гаусса. Одновременно исключим разрешённые неизвестные из целевой функции. Для этого запишем коэффициенты целевой функции в последней (третьей) строке таблицы, под матрицей системы. Вычисления приведены в таблице 1.

Таблица 1

Х1	x2	x3	х4	x5	b
5	9	-2	11	6	19
2	1	4	15	10	17
3	7	2	-1	8	21
3	9	-4	-11	-2	0
5	9	-2	11	6	19
2	1	4	15	10	17
1	6	-2	-16	-2	4
1	8	-8	-26	-12	-17
0	-21	8	91	16	-1
0	-11	8	47	14	9
1	6	-2	-16	-2	4
0	2	-6	-10	-10	-21
0	-21	8	91	16	-1
0	22	-16	-94	-28	-18
1	6	-2	-16	-2	4
0	2	-6	-10	-10	-21
0	1	-8	-3	-12	-19
0	22	-16	-94	-28	-18
1	6	-2	-16	-2	4
0	2	-6	-10	-10	-21
0	1	-8	-3	-12	-19
0	0	160	-28	236	400
1	0	46	2	70	118
0	0	10	-4	14	17
0	1	-8	-3	-12	-19
0	0	1	-0, 175	1, 475	2, 5
1	0	46	2	70	118
0	0	10	-4	14	17
0	1	0	-4, 4	-0, 2	1
0	0	1	-0, 175	1, 475	2, 5
1	0	0	10, 05	2, 15	3
0	0	0	-2, 25	-0, 75	-8
0	5	0	-22	-1	5
0	0	40	-7	59	100
20	0	0	201	43	60
0	0	0	-9	-3	-32

Отбросим в уравнениях-ограничениях неотрицательные разрешённые неизвестные х1, х2 и заменим знаки равенства знаками ««. В результате получим эквивалентную задачу линейного программирования с двумя переменными, которая решается графическим методом (рис. 1) :

при ограничениях:

Так как задача на минимум, то перемещаем линию уровня в направлении, противоположном направлению вектора до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых х3=0 и L2, т. е. через точку . Для определения координат точки В решаем систему уравнений

Получаем х4* = 0, х5* = 60 / 43.

Используем систему ограничений исходной задачи, приведённой к каноническому виду, и оптимальное решение задачи с двумя переменными для нахождения оптимального решения исходной задачи:



Рис. 1

2. Применяя симплекс-метод, решим задачу, т. е. найдем ее оптимальный план и минимальное значение целевой функции

при ограничениях:

В 1, 2 и 3 уравнение добавляем искусственный переменные R1, R2 и R3 ? 0. Получим М-задачу:

при ограничениях:

Данная система является системой с базисом, в которой R1, R2, R3 - базисные переменные, а x1, x2, х3, х4, х5, х6 свободные переменные, свободные члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:

Таблица 1

Базис	Свободн. коэфф-т	х1	х2	х3	х4v	х5	R1	R2	R3
R1	19	5	9	-2	11	6	1	0	0
R2 >	17	2	1	4	15	10	0	1	0
R3	21	3	7	2	-1	8	0	0	1
Z (x)	0	-3	-9	4	11	2	0	0	0
строка оценок		10	17	4	25	24	1	1	1

В таблицу добавлена строка «Строка оценок». Она соответствует сумме коэффициентов строк с искусственной переменной (R1, R2, R3). Она будет присутствовать в таблице до тех пор, пока искусственная переменная есть в базисе.

Первое опорное решение:

Т. к. в строке оценок есть положительные числа, то преобразуем исходную таблицу. В строке оценок ищем максимальное по модулю положительное число. Это число 25, оно стоит в столбце х4. Значит, х4 - ведущий столбец. Теперь найдем отношение свободных членов к положительным элементам ведущего столбца и выберем минимальное.

. Минимальное число оказалось в строке R2, это ведущая строка. На пересечении ведущего столбца и ведущей строки находится ведущий элемент.

Запишем новую таблицу, в которой базисом являются переменные R1, х4, R3.

Базис	Свободн. коэфф-т	х1	х2v	х3	х4	х5	R1	R2	R3
R1>	6 8/15	3 8/15	8 4/15	-4 14/15	0	-1 1/3	1	- 11/15	0
x4	1 2/15	2/15	1/15	4/15	1	2/3	0	1/15	0
R3	22 2/15	3 2/15	7 1/15	2 4/15	0	8 2/3	0	1/15	1
Z (x)	-12 7/15	-4 7/15	-9 11/15	1 1/15	0	-5 1/3	0	- 11/15	0
строка оценок		6 2/3	15 1/3	-2 2/3	0	7 1/3	1	- 2/3	1

Второе опорное решение:

Т. к. в строке оценок есть положительные числа, то преобразуем исходную таблицу. В строке оценок ищем максимальное по модулю положительное число. Это число 15 1/3, оно стоит в столбце х2. Значит, х2 - ведущий столбец. Теперь найдем отношение свободных членов к положительным элементам ведущего столбца и выберем минимальное.

.

Минимальное число оказалось в строке R1, это ведущая строка. На пересечении ведущего столбца и ведущей строки находится ведущий элемент.

Запишем новую таблицу, в которой базисом являются переменные х2, х4, R3.

Базис	Свободн. коэфф-т	х1	х2	х3	х4	х5v	R1	R2	R3
х2	49/62	53/124	1	- 37/62	0	- 5/31	15/124	- 11/124	0
x4>	1 5/62	13/124	0	19/62	1	21/31	- 1/124	9/124	0
R3	16 17/31	7/62	0	6 15/31	0	9 25/31	- 53/62	43/62	1
Z (x)	-4 24/31	- 19/62	0	-4 23/31	0	-6 28/31	1 11/62	-1 37/62	0
строка оценок		7/62	0	6 15/31	0	9 25/31	- 53/62	43/62	1

Третье опорное решение:

Т. к. в строке оценок есть положительные числа, то преобразуем исходную таблицу. В строке оценок ищем максимальное по модулю положительное число. Это число 9 25/31, оно стоит в столбце х5. Значит, х5 - ведущий столбец. Теперь найдем отношение свободных членов к положительным элементам ведущего столбца и выберем минимальное.

Минимальное число оказалось в строке х4, это ведущая строка. На пересечении ведущего столбца и ведущей строки находится ведущий элемент.

Запишем новую таблицу, в которой базисом являются переменные х2, х5, R3.

Базис	Свободн. коэфф-т	Х1	х2	х3v	х4	х5	R1	R2	R3
х2	1 1/21	19/42	1	- 11/21	5/21	0	5/42	- 1/14	0
x5	1 25/42	13/84	0	19/42	1 10/21	1	- 1/84	3/28	0
R3>	19/21	-1 17/42	0	2 1/21	-14 10/21	0	- 31/42	- 5/14	1
Z (x)	6 5/21	16/21	0	-1 13/21	10 4/21	0	1 2/21	- 6/7	0
строка оценок		-1 17/42	0	2 1/21	-14 10/21	0	- 31/42	- 5/14	1

Четвертое опорное решение:

Т. к. в строке оценок есть положительные числа, то преобразуем исходную таблицу. В строке оценок ищем максимальное по модулю положительное число. Это число 2 1/21, оно стоит в столбце х3. Значит, х3 - ведущий столбец. Теперь найдем отношение свободных членов к положительным элементам ведущего столбца и выберем минимальное.

Минимальное число оказалось в строке R3, это ведущая строка. На пересечении ведущего столбца и ведущей строки находится ведущий элемент.

Запишем новую таблицу, в которой базисом являются переменные х2, х5, х3. Т. к. в базисе не остается искусственных переменных, то «строки оценок» в следующей таблице нет.

Базис	Свободн. коэфф-т	х1	х2	х3	х4	х5	R1	R2	R3
х2	1 12/43	4/43	1	0	-3 20/43	0	- 3/43	- 7/43	11/43
x5	1 17/43	20/43	0	0	4 29/43	1	13/86	8/43	- 19/86
х3	19/43	- 59/86	0	1	-7 3/43	0	- 31/86	- 15/86	21/43
Z (x)	6 41/43	- 15/43	0	0	-1 11/43	0	22/43	-1 6/43	34/43

Пятое опорное решение:

Это решение является оптимальным, т. к. в строке Z (x) нет положительных чисел.

Zmin = 6 41/43.

Это решение совпадает с решением, полученным графическим способом:

3. Построим двойственную задачу.

при ограничениях:



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

=

Т. о., получили решение y1*= , y2*= , y3* =

Вычислить максимальное значение функции :

.

Проведем анализ полученного решения, применяя условия дополняющей нежесткости, согласно которым:

- Если , то .

- Если , то .

х1* = 0. Тогда

х2* = 1 12/43. Тогда

х3* = 19/43. Тогда

х4* = 0. Тогда

х5* =1 17/43. Тогда

Задача № 3

Транспортная задача

Ниже приведены числовые данные транспортных задач. Стоимость перевозки единицы продукции записаны в клетках таблицы. Запасы указаны справа от таблиц, а потребности - снизу. Требуется построить начальный план методами: «северо-западного угла», «минимального элемента», «двойного предпочтения», методом Фогеля. Из каждого плана найти оптимальный план методом потенциалов.

17	13	20	8	4	53
21	35	30	29	3	85
19	25	24	38	2	72
26	30	31	4	5	50
61	61	40	48	50

Пункт отправления	В1	В2	В3	В4	В5	Запасы, ai, тонн
А1	17	13	20	8	4	53
А2	21	35	30	29	3	85
А3	19	25	24	38	2	72
А4	26	30	31	4	5	50
Потребности, bj	61	61	40	48	50	260

Решение

1) Метод северо-западного угла

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

ai bj	61	61	40	48	50
53	17 53	13 -	20 -	8 -	4 -
85	21 8	35 61	30 16	29 -	3 -
72	19 -	25 -	24 24	38 48	2 0
50	26 -	30 -	31 -	4 -	5 50

Имеем первый опорный план:

53	0	0	0	0
8	61	16	0	0
0	0	24	48	0
0	0	0	0	50

Х1 =

F1 = 53*17+8*21+61*35+16*30+24*24+ 48*38 +50*5 = 6334 д. ед.

Ранг системы ограничений r = m+n-1 = 8. Количество заполненных клеток р =7. Т. к. r > р, то план вырожденный. Поставим в клетку А3В5 нулевое значение. Можем переходить к оптимизации.

Введем потенциалы: - потенциалы поставщиков; - потенциалы потребителей. Проверим на оптимальность полученный план. Для этого находим потенциалы поставщиков и покупателей из системы:

Имеем систему из 8 уравнений и 9 неизвестных. Полагаем u1 = 0. Тогда v1 = 17, u2 = 4, v2 = 31, u3 = -2, v3 = 26, u4 = 1, v4 = 40, v5 = 4. Решаем задачу методом потенциалов.

ui vj	v1 = 17	v2 = 31	v3 = 26	v4 = 40	v5 = 4
U1 = 0	17 53	13 -	20 -	8 -	4 -
U2 = 4	21 8	35 61	30 16	29 -	3 -
U3 = -2	19 -	25 -	24 24	38 - 48	2 + 0
U4 = 1	26 -	30 -	31 -	4 + -	5 - 50

Для каждой свободной клетки считаем

Получаем

Наибольшим среди положительных значений является = 37, поэтому помечаем клетку (4, 4) знаком «+». Строим цикл.

Получим новый план перевозок. Пересчитаем потенциалы.

ui vj	v1 = 17	v2 = 31	v3 = 26	v4 = 3	v5 = 4
u1 = 0	17 - 53	13 + -	20 -	8 -	4 -
u2 = 4	21 + 8	35 - 61	30 16	29 -	3 -
u3 = -2	19 -	25 -	24 24	38 -	2 48
u4 = 1	26 -	30 -	31 -	4 48	5 2

Имеем второй опорный план:

53	0	0	0	0
8	61	16	0	0
0	0	24	0	48
0	0	0	48	2

Х2 =

Стоимость нового плана F2 = F1 - F1, где F1 = *37 = 1776 ден. ед.

F2 = 4558 ден. ед.

Для каждой свободной клетки считаем

Получаем

Наибольшим среди положительных значений является = 18, поэтому помечаем клетку (1, 2) знаком «+». Строим цикл.

Получим новый план перевозок. Пересчитаем потенциалы.

ui vj	v1 = -1	v2 = 13	v3 = 8	v4 = -15	v5 = -14
u1 = 0	17 -	13 53	20 -	8 -	4 -
u2 = 22	21 61	35 8	30 - 16	29 -	3 + -
u3 = 16	19 -	25 -	24 + 24	38 -	2 - 48
u4 = 19	26 -	30 -	31 -	4 48	5 2

Имеем третий опорный план:

0	53	0	0	0
61	8	16	0	0
0	0	24	0	48
0	0	0	48	2

Х2 =

Стоимость нового плана F3 = F2 - F2, где F2 = *18 = 954 ден. ед. F3 = 4558 - 954 = 3604 ден. ед.

Для каждой свободной клетки считаем

Получаем

Наибольшим среди положительных значений является = 5, поэтому помечаем клетку (2, 5) знаком «+». Строим цикл.

Получим новый план перевозок. Пересчитаем потенциалы.

ui vj	v1 = -1	v2 = 13	v3 = 3	v4 = -20	v5 = -19
u1 = 0	17 -	13 53	20 -	8 -	4 -
u2 = 22	21 61	35 - 8	30 -	29 -	3 + 16
u3 = 21	19 -	25 + -	24 40	38 -	2 - 32
u4 = 24	26 -	30 -	31 -	4 48	5 2

Имеем четвертый опорный план:

0	53	0	0	0
61	8	0	0	16
0	0	40	0	32
0	0	0	48	2

Х4 =

Стоимость нового плана F4 = F3 - F3, где F3 = *5 = 80 ден. ед. F3 = 3604 - 80 = 3524 ден. ед.

Для каждой свободной клетки считаем

Получаем

Наибольшим среди положительных значений является = 9, поэтому помечаем клетку (3, 2) знаком «+». Строим цикл.

Получим новый план перевозок. Пересчитаем потенциалы.

ui vj	v1 = 8	v2 = 13	v3 = 12	v4 = -11	v5 = -10
u1 = 0	17 -	13 53	20 -	8 -	4 -
u2 = 13	21 - 61	35 -	30 -	29 -	3 + 24
u3 = 12	19 + -	25 8	24 40	38 -	2 - 24
u4 = 15	26 -	30 -	31 -	4 48	5 2

Имеем пятый опорный план:



0	53	0	0	0
61	0	0	0	24
0	8	40	0	24
0	0	0	48	2

Х5 =

Стоимость нового плана F5 = F4 - F4, где F4 = *9 = 72 ден. ед. F4 = 3524 - 72 = 3452 ден. ед.

Для каждой свободной клетки считаем

Получаем

Единственным положительным значением является = 1, поэтому помечаем клетку (3, 1) знаком «+». Строим цикл.

Получим новый план перевозок. Пересчитаем потенциалы.

ui vj	v1 = 7	v2 = 13	v3 =12	v4 = -12	v5 = -11
u1 = 0	17 -	13 53	20 -	8 -	4 -
u2 = 14	21 37	35 -	30 -	29 -	3 48
u3 = 12	19 24	25 8	24 40	38 -	2 -
u4 = 16	26 -	30 -	31 -	4 48	5 2

Имеем шестой опорный план:

0	53	0	0	0
37	0	0	0	48
24	8	40	0	0
0	0	0	48	2

Х6 =

Стоимость нового плана F6 = F5 - F5, где F5 = *1 = 24 ден. ед. F5 = 3452 - 24 = 3428 ден. ед.

Для каждой свободной клетки считаем

Получаем

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

0	53	0	0	0
37	0	0	0	48
24	8	40	0	0
0	0	0	48	2

Ответ:

Х6 =,

Fmin = 3428

2) Метод минимального элемента

Из всей таблицы стоимостей выберем наименьшую и в клетку, которая ей соответствует, поместим меньшее из чисел и . Затем из рассмотрения исключим либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выберем наименьшую стоимость, и процесс распределения запасов продолжаем, пока все запасы не будут распределены, а потребности удовлетворены. В итоге получим таблицу:

Ai bj	61	61	40	48	50
53	17 -	13 53	20 -	8 -	4 -
85	21 39	35 6	30 40	29 -	3 -
72	19 22	25 -	24 -	38 -	2 50
50	26 -	30 2	31 -	4 48	5 -

Имеем первый опорный план:

0	53	0	0	0
39	6	40	0	0
22	0	0	0	50
0	2	0	48	0

Х1 =

F1 = 53*13+39*21+6*35+40*30+22*19+ 50*2 +2*30+48*4 = 3688 д. ед.

Ранг системы ограничений r = m+n-1 = 8. Количество заполненных клеток р =8. Т. к. r = р, то план невырожденный. Можем переходить к оптимизации.

Введем потенциалы: - потенциалы поставщиков; - потенциалы потребителей. Проверим на оптимальность полученный план. Для этого находим потенциалы поставщиков и покупателей из системы:

Имеем систему из 8 уравнений и 9 неизвестных. Полагаем u1 = 0. Тогда v1 = -1, u2 = 22, v2 = 13, u3 = 20, v3 = 8, u4 = 17, v4 = -13, v5 = -18. Решаем задачу методом потенциалов.

Ui vj	v1 = -1	v2 = 13	v3 = 8	v4 = -13	v5 = -18
u1 = 0	17 -	13 53	20 -	8 -	4 -
u2 =22	21+ 39	35 - 6	30 40	29 -	3 -
u3 = 20	19- 22	25 + -	24 -	38 -	2 50
u4 = 17	26 -	30 2	31 -	4 48	5 -

Для каждой свободной клетки считаем

Получаем

Наибольшим среди положительных значений является = 8, поэтому помечаем клетку (3, 2) знаком «+». Строим цикл.

Получим новый план перевозок. Пересчитаем потенциалы.

ui vj	v1 = 7	v2 = 13	v3 = 16	v4 = -13	v5 = -10
u1 = 0	17 -	13 53	20 -	8 -	4 -
u2 =14	21 + 45	35 -	30 - 40	29 -	3 -
u3 = 12	19- 16	25 6	24 + -	38 -	2 50
u4 = 17	26 -	30 2	31 -	4 48	5 -

Имеем второй опорный план:

0	53	0	0	0
45	0	40	0	0
16	6	0	0	50
0	2	0	48	0

Х2 =

Стоимость нового плана F2 = F1 - F1, где F1 = *8 = 48 ден. ед.

F2 = 3640 ден. ед.

Для каждой свободной клетки считаем

Получаем

Наибольшим среди положительных значений является = 4, поэтому помечаем клетку (3, 3) знаком «+». Строим цикл.

Получим новый план перевозок. Пересчитаем потенциалы.



ui vj	v1 = 3	v2 = 13	v3 = 12	v4 = -13	v5 = -10
u1 = 0	17 -	13 53	20 -	8 -	4 -
u2 =18	21 61	35 -	30 - 24	29 -	3 + -
u3 = 12	19 -	25 6	24 + 16	38 -	2 - 50
u4 = 17	26 -	30 2	31 -	4 48	5 -

Имеем третий опорный план:

0	53	0	0	0
61	0	24	0	0
0	6	16	0	50
0	2	0	48	0

Х3 =

Стоимость нового плана F3 = F2 - F2, где F2 = *4 = 64 ден. ед.

F3 = 3576 ден. ед.

Для каждой свободной клетки считаем

Получаем

Наибольшим среди положительных значений является = 5, поэтому помечаем клетку (2, 5) знаком «+». Строим цикл.

Получим новый план перевозок. Пересчитаем потенциалы.

ui vj	v1 = 8	v2 = 13	v3 = 12	v4 = -13	v5 = -10
u1 = 0	17 -	13 53	20 -	8 -	4 -
u2 = 13	21 61	35 -	30 -	29 -	3 24
u3 = 12	19 -	25 + 6	24 40	38 -	2 - 26
u4 = 17	26 -	30 - 2	31 -	4 48	5 + -

Имеем четвертый опорный план:

0	53	0	0	0
61	0	0	0	24
0	6	40	0	26
0	2	0	48	0

Х4 =

Стоимость нового плана F4 = F3 - F3, где F3 = *5 = 120 ден. ед.

F4 = 3456 ден. ед.

Для каждой свободной клетки считаем

Получаем

Наибольшим среди положительных значений является = 2, поэтому помечаем клетку (4, 5) знаком «+». Строим цикл.

ui vj	v1 = 8	v2 = 13	v3 = 12	v4 = -11	v5 = -10
u1 = 0	17 -	13 53	20 -	8 -	4 -
u2 = 13	21 - 61	35 -	30 -	29 -	3 + 24
u3 = 12	19 + -	25 8	24 40	38 -	2 - 24
u4 = 15	26 -	30 -	31 -	4 48	5 2

Имеем пятый опорный план:

0	53	0	0	0
61	0	0	0	24
0	8	40	0	24
0	0	0	48	2

Х5 =

Стоимость нового плана F5 = F4 - F4, где F4 = *2 = 4 ден. ед. F5 = 3452 ден. ед.

Для каждой свободной клетки считаем

Получаем

Единственным положительным значением является = 1, поэтому помечаем клетку (3, 1) знаком «+». Строим цикл.

Получим новый план перевозок. Пересчитаем потенциалы.

ui vj	v1 = 7	v2 = 13	v3 =12	v4 = -12	v5 = -11
U1 = 0	17 -	13 53	20 -	8 -	4 -
u2 = 14	21 37	35 -	30 -	29 -	3 48
u3 = 12	19 24	25 8	24 40	38 -	2 -
u4 = 16	26 -	30 -	31 -	4 48	5 2

Имеем шестой опорный план:

0	53	0	0	0
37	0	0	0	48
24	8	40	0	0
0	0	0	48	2

Х6 =

Стоимость нового плана F6 = F5 - F5, где F5 = *1 = 24 ден. ед. F5 = 3452 - 24 = 3428 ден. ед.

Для каждой свободной клетки считаем

Получаем

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

0	53	0	0	0
37	0	0	0	48
24	8	40	0	0
0	0	0	48	2

Ответ:

Х6 =, Fmin = 3428

3) Метод двойного предпочтения

В каждом столбце отметим знаком клетку с наименьшей стоимостью. Затем тоже проделываем в каждой строке.

Получим:

Пункт отправления	В1	В2	В3	В4	В5	Запасы, ai, тонн
А1	17*	13*	20*	8	4*	53
А2	21	35	30	29	3*	85
А3	19	25	24	38	2**	72
А4	26	30	31	4**	5	50
Потребности, bj	61	61	40	48	50	260

В клетки с двойной отметкой поместим максимально возможные объемы перевозок, каждый раз исключая и рассмотрения соответствующие столбцы или строки. Затем распределим перевозки по клеткам с единичной отметкой. Остальные перевозки распределим по наименьшей стоимости. В итоге получим

ai bj	61	61	40	48	50
53	17 -	13 53	20 -	8 -	4 -
85	21 39	35 6	30 40	29 -	3 -
72	19 22	25 -	24 -	38 -	2 50
50	26 -	30 2	31 -	4 48	5 -
0	53	0	0	0
37	0	0	0	48
24	8	40	0	0
0	0	0	48	2

Получили такой же начальный опорный план, как и в методе «минимального элемента». Поэтому решения этими методами не будут

отличаться.

Ответ: Х6 = Fmin = 3428 ден. ед.

4) Метод Фогеля.

При определении опорного плана методом аппроксимации Фогеля находим разность по всем столбцам и по всем строкам между двумя записанными в них минимальными тарифами. Среди указанных разностей выберем минимальную. В строке (или в столбце), которой данная разность соответствует, определим минимальную стоимость.

Пункт отправления	В1	В2	В3	В4	В5	Запасы, ai, тонн	Штрафы строк, di
А1	17 -	13 53	20 -	8 -	4 -	53	3	-	-	-	-	-
А2	21 61	35 -	30 -	29 -	3 24	85	1	1	5	5	27	-
А3	19 -	25 8	24 40	38 -	2 24	72	1	1	1	1	22	22
А4	26 -	30 -	31 -	4 48	5 2	50	1	1	1	1	26	26
Потребности, bj	61	61	40	48	50	260
Штрафы столбцов, dj	2	5	1	4	1
	2	5	1	9	1
	2	5	1	-	1
	-	5	1	-	1
	-	-	1	-	1
	-	-	7	-	3

Получили следующий опорный план:

0	53	0	0	0
61	0	0	0	24
0	8	40	0	24
0	0	0	48	2

Х1 =

Стоимость плана F1 = 53*13+61*21+24*3+8*25+40*24+24*2+48*4+2*5 = 3452 ден. ед.

Проверим план на оптимальность методом потенциалов. Для этого полагаем u1 = 0.

ui vj	v1 = 8	v2 = 13	v3 = 12	v4 = -11	v5 = -10
u1 = 0	17 -	13 53	20 -	8 -	4 -
u2 = 13	21 - 61	35 -	30 -	29 -	3 + 24
u3 = 12	19 + -	25 8	24 40	38 -	2 - 24
u4 = 15	26 -	30 -	31 -	4 48	5 2

Для каждой свободной клетки считаем

Получаем

Единственным положительным значением является = 1, поэтому помечаем клетку (3, 1) знаком «+». Строим цикл.

Получим новый план перевозок. Пересчитаем потенциалы.

ui vj	v1 = 7	v2 = 13	v3 =12	v4 = -12	v5 = -11
u1 = 0	17 -	13 53	20 -	8 -	4 -
u2 = 14	21 37	35 -	30 -	29 -	3 48
u3 = 12	19 24	25 8	24 40	38 -	2 -
u4 = 16	26 -	30 -	31 -	4 48	5 2

Имеем второй опорный план:



0	53	0	0	0
37	0	0	0	48
24	8	40	0	0
0	0	0	48	2

Х2 =

Стоимость нового плана F2 = F1 - F1, где F1 = *1 = 24 ден. ед. F1 = 3452 - 24 = 3428 ден. ед.

Для каждой свободной клетки считаем

Получаем

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

0	53	0	0	0
37	0	0	0	48
24	8	40	0	0
0	0	0	48	2

Ответ:

Х6 =

Fmin =

3428 ден. ед.

Задача № 4

Сетевая задача

Ниже приведен вариант транспортной задачи в сетевой постановке. Задача изображена в виде неориентированного связного графа. На ребрах проставлены значения тарифов , на вершинах (в кружках) - значения запасов-потребностей . Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.

Решение

Построение пробного плана.

Из 1 в 3 отправляем 28 единиц

Из 4 в 3 отправляем 40 единиц

Из 5 в 3 отправляем 27 единиц

Из 3 в 6 отправляем 95 единиц

Из 6 в 10 отправляем 65 единиц

Из 10 в 9 отправляем 20 единиц

Из 10 в 11 отправляем 25 единиц

Из 2 в 5 отправляем 20 единиц

Из 5 в 8 отправляем 22 единиц

Из 8 в 7 отправляем 25 единиц

Из 8 в 12 отправляем 15 единиц

Весь груз вывезен, потребности удовлетворены, число базисных коммуникаций равно 11 = n-1, план является опорным.

Перевозки, определенные для различных участков сети, поместим в кружок со стрелкой.

План X0 (см. рис. 1).

Рис. 1 Опорный план Х0

Суммарная стоимость перевозки:

f0 = 28*6 + 20 + 40*6 + 95 + 27*2 + 22*2 + 15*10 + 25*17+65*3 +20*2 +25*2 = 1481 руб.

Для вершин рассчитаем потенциалы. Пусть = 0, тогда, двигаясь по базисным ребрам, найдем: 3 = 0 + 6 = 6, 4 = 6 -6 = 0, 6 = 6 + 1 = 7. Затем 10 = 7 +3 = 10, 9 = 10+2 = 12, 11 =10+2 =12, 10 = -8 - 2 = -6, 5 = 6 - 2 = 4, 2 = 4 - 1 = 3, 8 = 4 +2 = 6, 12 = 6 +10 = 16. Найденные потенциалы запишем в прямоугольники и поместим около своих вершин (рис. 2).

Для небазисных ребер находим оценки: 1, 4 = |0 - 0| - 9= - 9, 4, 5 = |4 -0| - 5 = -1, 3, 2 = |3 - 6| - 3 = 0, 2, 8 = |6 - 3| - 12 = -9, 5, 7 = |23 - 4| - 18 = 1, 7, 9 = |12 - 23| - 9 = 2, 9, 11 = |12 - 12| - 5 = -5, 11, 12 = |16 - 12| - 10 = -6, 10, 12 = |16 - 10| - 17 = -11, 8, 10 = |10 - 6| - 19 = -15.

План не является оптимальным, так как имеются положительные оценки. Для улучшения плана строим цикл пересчета, который изобразим на рис. 2 пунктирной линией.

Рис. 2 Расчет потенциалов

Определим величину корректировки плана

= min (25, 22) = 22.

i, j:
	(9, 7)	(7, 8)	(8, 5)	(5, 3)	(3, 6)	(6, 10)	(10, 9)
		25	22	27	95	65	20
	+	-	-	+	+	+	+

Вносим изменение в план X0 перевозки из цикла, направленные против разрешающей стрелки уменьшим на ; перевозки из цикла, совпадающие по направлению с разрешающей стрелкой и перевозку по коммуникации (9, 7) увеличим на эту же величину; перевозки, не вошедшие в цикл пересчета, остаются без изменения. Получим новые значения перевозок: х9, 7 = 22, х7, 8 = 3, х5, 3 = 49, x3, 6 = 117, х6, 10 = 87, х10, 9 = 42. Перевозка x8, 5 исключается из базиса. Улучшенный план Х1 представлен на рис. 3.

Значение функции f1 = 1481 - 22*2 = 1437 руб.

Потенциалы рассчитываем непосредственно на схеме и записываем их около своих вершин.

Для небазисных ребер находим оценки: 1, 4 = |0 - 0| - 9= - 9, 4, 5 = |4 -0| - 5 = -1, 3, 2 = |3 - 6| - 3 = 0, 2, 8 = |5-3| - 12 = -10, 5, 7 = |21 - 4| - 18 = -1, 5, 8 = |4 - 4| - 2 = -2, 9, 11 = |12 - 12| - 5 = -5, 11, 12 = |14 - 12| - 10 = -8, 10, 12 = |14 - 10| - 17 = -13, 8, 10 = |10 - 4| - 19 = -13.



Рис. 3 Опорный план Х1

Таким образом, план Х1 оптимален. Минимальные издержки на перевозку всей продукции составляют величину равную 1437 руб.



Задача № 5

Задача о назначениях

Ниже приведены таблицы, в клетках которых проставлены элементы матрицы эффективностей Решить задачу методом потенциалов и венгерским методом.

32	47	21	15	37	20	21	18
6	35	18	48	43	38	16	44
41	28	2	15	33	0	14	32
20	5	43	50	35	17	27	42
39	29	17	45	3	33	36	18
46	24	19	15	23	23	27	9
4	36	12	35	4	12	26	24
33	12	37	14	1	40	42	14

Решение

Обозначим xij назначение на i-ое место j-го работника. xij может принимать только два целочисленных значения: 1, если на i-ое место назначен j-ый работник; 0, если не назначен.

Т. к. в условии не указано, решается задача на минимум или на максимум, то будем решать на минимум: :

С (х) =

1. Венгерский способ

В каждой строке таблицы найдем наименьший элемент и вычтем его из всех элементов данной строки:

min
32	47	21	15	37	20	21	18	15		17	32	6	0	22	5	6	3
6	35	18	48	43	38	16	44	6		0	29	12	42	37	32	10	38
41	28	2	15	33	0	14	32	0		41	28	2	15	33	0	14	32
20	5	43	50	35	17	27	42	5		15	0	38	45	30	12	22	37
39	29	17	45	3	33	36	18	3		36	26	14	42	0	30	33	15
46	24	19	15	23	23	27	9	9		37	15	10	6	14	14	18	0
4	36	12	35	4	12	26	24	4		0	32	8	31	0	8	22	20
33	12	37	14	1	40	42	14	1		32	11	36	13	0	39	41	13

Далее проводим аналогичную процедуру для всех столбцов: ищем наименьший элемент по столбцу и отнимаем его из всех элементов столбца. Получим:

min	17	32	6	0	22	5	6	3		17	32	4	0	22	5	0	3
	0	29	12	42	37	32	10	38		0	29	10	42	37	32	4	38
	41	28	2	15	33	0	14	32		41	28	0	15	33	0	8	32
	15	0	38	45	30	12	22	37		15	0	36	45	30	12	16	37
	36	26	14	42	0	30	33	15		36	26	12	42	0	30	27	15
	37	15	10	6	14	14	18	0		37	15	8	6	14	14	12	0
	0	32	8	31	0	8	22	20		0	32	6	31	0	8	16	20
	32	11	36	13	0	39	41	13		32	11	34	13	0	39	35	13
	0	0	2	0	0	0	6	0

Выбираем строку с одним нулем (строка №2), выделяем нуль жирным и зачеркиваем (выделено серым) оставшиеся нулевые значения этого столбца (столбца №1).

Выбираем строку с одним нулевым значением (строка №4), выделяем нуль.

Выбираем строку с одним нулем (строка №5), выделяем нуль жирным и зачеркиваем (выделено серым) оставшиеся нулевые значения этого столбца (столбца №5).

Видим, что 7 и 8 строки не имеют нулей. Значит, дальше преобразуем последнюю таблицу.

Проведем минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице. С этой целью исключаем строки 1, 3 и 6, столбцы 1, 2, 5.

17	32	4	0	22	5	0	3
0	29	10	42	37	32	4	38
41	28	0	15	33	0	8	32
15	0	36	45	30	12	16	37
36	26	12	42	0	30	27	15
37	15	8	6	14	14	12	0
0	32	6	31	0	8	16	20
32	11	34	13	0	39	35	13

Получим сокращенную матрицу:

10	42	32	4	38
36	45	12	16	37
12	42	30	27	15
6	31	8	16	20
34	13	39	35	13

Затем определяем в ней минимальный элемент 1, вычитаем его из всех элементов этой матрицы и суммируем его с элементами, находящимися на пересечениях исключаемых строк и столбцов редуцированной матрицы (выделена в квадрат), объединяем результаты и получаем эквивалентную матрицу:

21	36	4	0	26	5	0	3
0	29	6	38	37	28	0	34
45	32	0	15	37	0	8	32
15	0	32	41	30	8	12	33
36	26	8	38	0	26	23	11
41	19	8	6	18	14	12	0
0	32	2	27	0	4	12	16
32	11	30	9	0	35	31	9

Полученное решение снова недопустимое, т. к. в пятой и восьмой строке содержатся по одному нулю, находящиеся в одном столбце. Снова преобразуем таблицу. Проведем минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице. С этой целью исключаем строки 1, 3 и 6, столбцы 1, 2, 5 и 7.

21	36	4	0	26	5	0	3
0	29	6	38	37	28	0	34
45	32	0	15	37	0	8	32
15	0	32	41	30	8	12	33
36	26	8	38	0	26	23	11
41	19	8	6	18	14	12	0
0	32	2	27	0	4	12	16
32	11	30	9	0	35	31	9

Получим сокращенную матрицу:

6	38	28	34
32	41	8	33
8	38	26	11
2	27	4	16
30	9	35	9

Затем определяем в ней минимальный элемент 2, вычитаем его из всех элементов этой матрицы и суммируем его с элементами, находящимися на пересечениях исключаемых строк и столбцов редуцированной матрицы (выделена в квадрат), объединяем результаты и получаем эквивалентную матрицу:

23	38	4	0	28	5	2	3
0	29	4	36	37	26	0	32
47	34	0	15	39	0	10	32
15	0	30	39	30	6	12	31
36	26	6	36	0	24	23	9
43	21	8	6	20	14	14	0
0	32	0	25	0	2	12	14
32	11	28	7	0	33	31	7

Полученное решение снова недопустимое, т. к. в пятой и восьмой строке по-прежнему содержатся по одному нулю, находящиеся в одном столбце. Снова преобразуем таблицу. Проведем минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице. С этой целью исключаем строки 1, 3 и 6, столбцы 1, 2, 5.

23	38	4	0	28	5	2	3
0	29	4	36	37	26	0	32
47	34	0	15	39	0	10	32
15	0	30	39	30	6	12	31
36	26	6	36	0	24	23	9
43	21	8	6	20	14	14	0
0	32	0	25	0	2	12	14
32	11	28	7	0	33	31	7

Получим сокращенную матрицу:

15	30	39	6	12
36	6	36	24	23
43	8	6	14	14
32	28	7	33	31

Затем определяем в ней минимальный элемент 6, вычитаем его из всех элементов этой матрицы и суммируем его с элементами, находящимися на пересечениях исключаемых строк и столбцов редуцированной матрицы (выделена в квадрат), объединяем результаты и получаем эквивалентную матрицу, в которой все подлежащие назначению единицы разместятся в клетки с нулевой стоимостью:

23	44	4	0	34	5	2	9
0	35	4	36	43	26	0	38
47	40	0	15	45	0	10	38
9	0	24	33	30	0	6	31
30	26	0	30	0	18	17	9
37	21	2	0	20	8	8	0
0	38	0	25	6	2	12	20
26	11	22	1	0	27	25	7

Таким образом, оптимальная матрица назначений:

			1
						1
					1
	1
		1
							1
1
				1

Минимальное значение целевой функции Fmin = 15+16+0+5+17+9+4+1 = 67.

2. Метод потенциалов

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

С (х) =

ai bj	1	1	1	1	1	1	1	1
1	32	47	21	15	37	20	21	18
1	6	35	18	48	43	38	16	44
1	41	28	2	15	33	0	14	32
1	20	5	43	50	35	17	27	42
1	39	29	17	45	3	33	36	18
1	46	24	19	15	23	23	27	9
1	4	36	12	35	4	12	26	24
1	33	12	37	14	1	40	42	14

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

ai bj		1	1	1	1	1	1	1	1
		u1=0	u2=7	u3=10	U4=9	u5= -4	u6=8	u7=10	u8=12
1	v1=6	32 -	47 -	21 -	15 1	37 -	20 -	21 -	18 0
1	v2= 6	6 0	35 -	18 -	48 -	43 -	38 -	16 1	44 -
1	v3= -8	41 -	28 -	2 0	15 -	33 -	0 1	14 -	32 -
1	v4= -2	20 -	5 1	43 -	50 -	35 -	17 -	27 -	42 -
1	v5=7	39 -	29 -	17 1	45 -	3 0	33 -	36 -	18 -
1	v6= -3	46 -	24 -	19 -	15 -	23 -	23 -	27 -	9 1
1	v7 =4	4 1	36 -	12 -	35 -	4 -	12 0	26 -	24 -
1	v8= 5	33 -	12 0	37 -	14 0	1 1	40 -	42 -	14 -

Введем систему потенциалов ui и vj. Положим u1 = 0. Потенциалы vj найдем из условия

Для каждой свободной клетки считаем . Расчет произведем в таблице:

ai bj		1	1	1	1	1	1	1	1
		u1=0	u2=7	u3=10	u4=9	u5= -4	u6=8	u7=10	u8=12
1	v1=6	32 -26	47 -34	21 -5	15 + 1	37 -35	20 -6	21 -5	18 - 0
1	v2= 6	6 0	35 -22	18 -2	48 -33	43 -41	38 -24	16 1	44 -26
1	v3= -8	41 -49	28 -29	2 0	15 -14	33 -45	0 1	14 -16	32 -28
1	v4= -2	20 -22	5 1	43 -35	50 -43	35 -41	17 -11	27 -19	42 -32
1	v5=7	39 -32	29 -15	17 1	45 -29	3 0	33 -18	36 -19	18 1
1	v6= -3	46 -49	24 -20	19 -12	15 -9	23 -30	23 -18	27 -20	9 1
1	v7 =4	4 1	36 -25	12 2	35 -22	4 -4	12 0	26 -12	24 -8
1	v8= 5	33 -28	12 0	37 -22	14 - 0	1 1	40 -27	42 -27	14 + 3

Наибольшим среди положительных значений является = 3, поэтому помечаем клетку (8, 8) знаком «+». Строим цикл.

В новой таблице произведем пересчет потенциалов.

ai bj		1	1	1	1	1	1	1	1
		u1=0	u2=7	u3=10	u4=9	u5= -4	u6=8	u7=10	u8=9
1	v1=6	32 -26	47 -34	21 -5	15 1	37 -35	20 -6	21 -5	18 -3
1	v2= 6	6 0	35 -22	18 -2	48 -33	43 -41	38 -24	16 1	44 -29
1	v3= -8	41 -49	28 -29	2 - 0	15 -14	33 -45	0 + 1	14 -16	32 -31
1	v4= -2	20 -22	5 1	43 -35	50 -43	35 -41	17 -11	27 -19	42 -35
1	v5=7	39 -32	29 -15	17 1	45 -29	3 0	33 -18	36 -19	18 -2
1	v6= 0	46 -46	24 -17	19 -9	15 -6	23 -27	23 -15	27 -17	9 1
1	v7 =4	4 1	36 -25	12 + 2	35 -22	4 -4	12 - 0	26 -12	24 -11
1	v8= 5	33 -28	12 0	37 -22	14 0	1 1	40 -27	42 -27	14 0

Единственным положительным значением является = 2, поэтому помечаем клетку (7, 3) знаком «+». Строим цикл.



В новой таблице произведем пересчет потенциалов.

ai bj		1	1	1	1	1	1	1	1
		u1=0	u2=5	u3=8	u4=7	u5= -6	u6=6	u7=10	u8=7
1	v1=8	32 -24	47 -34	21 -5	15 1	37 -35	20 -6	21 -3	18 -3
1	v2= 6	6 0	35 -24	18 -4	48 -35	43 -43	38 -26	16 1	44 -31
1	v3= -6	41 -47	28 -29	2 0	15 -14	33 -45	0 1	14 -10	32 -33
1	v4= 0	20 -20	5 1	43 -35	50 -43	35 -41	17 -11	27 -17	42 -35
1	v5= 9	39 -30	29 -15	17 1	45 -29	3 0	33 -18	36 -17	18 -2
1	v6= 2	46 -44	24 -17	19 -9	15 -6	23 -27	23 -15	27 -15	9 1
1	v7 =4	4 1	36 -27	12 0	35 -22	4 -6	12 -2	26 -12	24 -13
1	v8= 7	33 -26	12 0	37 -22	14 0	1 1	40 -27	42 -25	14 0

Т. к. оценки всех свободных клеток отрицательны, то получили оптимальный план.

Ответ:

			1
						1
					1
	1
		1
							1
1
				1

Размещено на Allbest.ru