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

Размещено на 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

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

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

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