Челябинск 2004 Задача 1 Предприятие предполагает выпускать два вида продукции А1 и А2 , для производства которых используется сырье трех видов. Производство обеспечено сырьем каждого вида в количествах: b1, b2, b 3 кг. На изготовление единицы изделия А1 требуется затратить сырья каждого вида а1I, а2I, а 3I кг, соответственно, а для единицы изделия А2 - а12, а22, а32 кг. Прибыль от реализации единицы изделия А1 составляет с1 д. ед., для единицы изделия A2 - с2 д. ед. Требуется составить план производства изделий А1 и A2, обеспечивающий максимальную прибыль предприятия от реализации готовой продукции. Необходимо: - решить задачу симплекс-методом; - сформулировать двойственную задачу и найти ее решение; - определить интервалы устойчивости двойственных оценок по отношению к изменению сырья каждого вида в отдельности; - оценить стоимость готовой продукции, если запасы сырья каждого вида на производстве изменились на величину Db1, Db2 и Db3 кг, соответственно, а также найти новый оптимальный план; - решить исходную задачу геометрически. Подпись:
Вид сырья Продукция Ограничения
по сырью Изменения запасов
А1 А2
1-й 2 5 432 113
2-й 3 4 424 37
3-й 5 3 532 -100
Прибыль 34 50

Подпись:
Вид сырья Продукция Ограничения
по сырью Изменения запасов
А1 А2
1-й 2 5 432 113
2-й 3 4 424 37
3-й 5 3 532 -100
Прибыль 34 50

Задание 1 Запишем задачу линейного программирования для данной задачи:

, (1)

. В задаче (1) переменные

- количество единиц продукции вида A и B. Приведем задачу (1) к каноническому виду. Для этого преобразуем все ограничения из неравенств в равенства (путем введения дополнительных переменных) и заменим задачу максимизации на задачу минимизации. Имеем:

, (2)

. Составим 1-ю симплекс-таблицу Контрольная: Транспортная задача

Таблица 1

Свободные переменные Базисные переменные	Свободный член	x1	x2
x3	432	2	5
x4	424	3	4
x5	532	5	3
*Fmin*	0	34	50

Разыскиваем в последней строке наименьший положительный элемент, он равен 34. Первый столбец коэффициентов будет разрешающим. Определим отношение свободных членов к положительным элементам разрешающего столбца. Минимальное симплекс-отношение равно 532/5. Разрешающий элемент находится на пересечении строки базисной переменной x5 и столбца свободной переменной x1. Меняем местами переменные x5 и x1 и переходим к следующей симплекс-таблице, используя правило прямоугольника. Таблица 2

Свободные переменные Базисные переменные	Свободный член	x5	x2
x3	1096/5	-2/5	19/5
x4	524/5	-3/5	11/5
x1	532/5	1/5	3/5
*Fmin*	-18088/5	-34/5	148/5

Разыскиваем в последней строке наименьший положительный элемент, он равен 148/5. Второй столбец коэффициентов будет разрешающим. Определим отношение свободных членов к положительным элементам разрешающего столбца. Минимальное симплекс-отношение равно 524/11. Разрешающий элемент находится на пересечении строки базисной переменной x4 и столбца свободной переменной x2. Меняем местами переменные x4 и x2 и переходим к следующей симплекс-таблице, используя правило прямоугольника. Таблица 3

Свободные переменные Базисные переменные	Свободный член	x5	x4
x3	420/11	7/11	-19/11
x2	524/11	-3/11	5/11
x1	856/11	4/11	-3/11
*Fmin*	-55304/11	14/11	-148/11

Разыскиваем в последней строке наименьший положительный элемент, он равен 14/11. Второй столбец коэффициентов будет разрешающим. Определим отношение свободных членов к положительным элементам разрешающего столбца. Минимальное симплекс-отношение равно 60. Разрешающий элемент находится на пересечении строки базисной переменной x3 и столбца свободной переменной x5. Меняем местами переменные x3 и x5 и переходим к следующей симплекс-таблице, используя правило прямоугольника. Таблица 4

Свободные переменные Базисные переменные	Свободный член	x3	x4
x5	60	11/7	-19/7
x2	64	3/7	-2/7
x1	56	-4/7	5/7
*Fmin*	-5104	-2	-10

В последней строке нет положительных элементов, следовательно, оптимальное решение найдено: Fmax = -Fmin = 5104; X = (56; 64; 0; 0; 60). Задание 2 Теоремы двойственности. Первая (основная) теорема двойственности. Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их целевых линейных функций равны:

или

. Если целевая линейная функция одной из задач не ограничена, то условия другой задачи противоречивы. Вторая теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных целевой функции исходной задачи, выраженной через неосновные переменные ее оптимального решения. Двойственная задача линейного программирования для исходной задачи (1) имеет вид

. Согласно теоремам двойственности ее решением будет вектор (2, 10, 0). При этом

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

Переменная	Теневая цена	Полученный расход сырья	Ограничение по сырью	Допустимое увеличение	Допустимое уменьшение
Y1	2	432	432	98	38,1818
Y2	10	424	424	22,1053	78,4
Y3	0	472	532	Не ограничено	60

Таблица 5 Задание 4 Оценим стоимость готовой продукции, если запасы сырья каждого вида на производстве изменились на величину Db1 = 113, Db2 = 27 и Db3 = -100, соответственно, и найдем новый оптимальный план. Новая задача линейного программирования имеет вид:

, (3)

. X = (17,857; 101,857; 0; 0; 37,143). При этом оптимальном плане стоимость готовой продукции равна Fmax = -Fmin = 5700, Т.е. при максимальная стоимость продукции выросла на 5700 – 5104 = 596 ед. Задание 5 Решим исходную задачу (1) геометрически. Построим в системе координат X1OX2 построим три прямых, соответствующих трем ограничениям исходной задачи:

- ограничение (1),

- ограничение (2),

- ограничение (3). Построим область допустимых значений:

x1	0	216
x2	86,4	0

x1	0	141,33
x2	106	0

x1	0	116,4
x2	194	0

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

направления наибольшего возрастания целевой функции Fmax равен (34, 50). Линии уровня перпендикулярны вектору

, одна из них приведена на рисунке. Перемещая линию уровня по направлению

, находим наиболее удаленную от начала координат точку. Из графика видно, что эта точка X является пересечением прямых, соответствующих ограничениям (1) и (2). Ее координаты найдем, решив систему линейных уравнений: Контрольная: Транспортная задача

(4) Решением системы (4) является точка с координатами

Ответ:

ден.ед.

X

U

Задача № 33 На три базы: А1, А2, А3 поступил однородный груз в количествах: а1, а2, а 3, соответственно. Груз требуется перевезти в пять пунктов: b1 в пункт В1, b2 в пункт В2, b3 в пункт В3, b4 в пункт В4, b5 в пункт В5. Спланировать перевозки так, чтобы общая их стоимость была минимальной. Матрица тарифов cij перевозок между пунктами отправления (базами) и пунктами назначения, а также запасы ai и потребности bj задаются ниже для каждого номера задачи в соответствии с таблицами 1, 2. Таблица 1 Подпись: Пункт отправления В1 В2 В3 B4 В5 Запасы, аi (тонн)
А1 с11 c12 c13 c14 c15 а1
А2 c21 c22 c23 c24 c25 a2
А3 c31 c32 c33 c34 c35 a3
Потребности, bj (тонн) b1 b2 b3 b4 b5 Sаi = Sbj

Подпись: Пункт отправления В1 В2 В3 B4 В5 Запасы, аi (тонн)
А1 с11 c12 c13 c14 c15 а1
А2 c21 c22 c23 c24 c25 a2
А3 c31 c32 c33 c34 c35 a3
Потребности, bj (тонн) b1 b2 b3 b4 b5 Sаi = Sbj

Таблица 2

В1

В2

В3

В4

В5

аi

А1	14	8	17	5	3	120
А2	21	10	7	11	6	180
А3	3	5	8	4	9	230
bj	70	120	105	125	110	530

Решение

Имеем транспортную задачу закрытого типа. Математическая модель этой задачи имеет вид:

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

. Определим теперь базисный план (допустимое опорное решение) транспортной задачи закрытого типа. Используем метод наименьшей стоимости. Запишем исходную таблицу. Таблица 3

	B1	B2	B3	B4	B5	Запасы, ai
А1	14	8	17	5	3	120
А2	21	10	7	11	6	180
А3	3	5	8	4	9	230
Потребности, bj	70	120	105	125	110

Ищем в таблице 3 минимальную стоимость – это ячейки (1,5) и (3,1), т.е. 1-я строка и 5-й столбец и 3-я строка и 1-й столбец. Возьмем, для определенности ячейку (1,5). Определяем минимум из запасов в 1-й строке и потребностей в 5-м столбце. Он равен 110. Записываем в скобках в ячейку (1,5) 110 и вычеркиваем 1-й столбец, а запасы 1-й строки уменьшаем на 110 единиц, т.е. 120 - 110 = 10 ед. Таблица 4

	B1	B2	B3	B4	B5	Запасы, ai
А1	14	8	17	5	(110)3	120,10
А2	21	10	7	11	6	180
А3	3	5	8	4	9	230
Потребности, bj	70	120	105	125	110,0

Ищем в таблице 4 минимальную стоимость – это ячейка (3,1), т.е. 3-я строка и 1-й столбец. Определяем минимум из запасов в 3-й строке и потребностей в 1-м столбце. Он равен 70. Записываем в скобках в ячейку (3,1) 70 и вычеркиваем 1- й столбец, а запасы 3-й строки уменьшаем на 70 единиц, т.е. 230 - 70 = 160 ед. Таблица 5

	B1	B2	B3	B4	B5	Запасы, ai
А1	14	8	17	5	(110)3	120,10
А2	21	10	7	11	6	180
А3	(70)3	5	8	4	9	230,160
Потребности, bj	70,0	120	105	125	110,0

Ищем в таблице 5 минимальную стоимость – это ячейка (3,4), т.е. 3-я строка и 4-й столбец. Определяем минимум из запасов в 3-й строке и потребностей в 4-м столбце. Он равен 125. Записываем в скобках в ячейку (3,4) 125 и вычеркиваем 4-й столбец, а запасы 3-й строки уменьшаем на 125 единиц, т.е. 160 - 125 = 35 ед. Таблица 6

	B1	B2	B3	B4	B5	Запасы, ai
А1	14	8	17	5	(110)3	120,10
А2	21	10	7	11	6	180
А3	(70)3	5	8	(125)4	9	230,160,35
Потребности, bj	70,0	120	105	125,0	110,0

Ищем в таблице 6 минимальную стоимость – это ячейка (3,2), т.е. 3-я строка и 2-й столбец. Определяем минимум из запасов в 3-й строке и потребностей во 2-м столбце. Он равен 35. Записываем в скобках в ячейку (3,2) 35 и вычеркиваем 3- ю строку, а запасы 2-го столбца уменьшаем на 35 единиц, т.е. 120 - 35 = 85 ед. Таблица 7

	B1	B2	B3	B4	B5	Запасы, ai
А1	14	8	17	5	(110)3	120,10
А2	21	10	7	11	6	180
А3	(70)3	(35)5	8	(125)4	9	230,160,35,0
Потребности, bj	70,0	120,85	105	125,0	110,0

Ищем в таблице 7 минимальную стоимость – это ячейка (2,3), т.е. 2-я строка и 3-й столбец. Определяем минимум из запасов во 2-й строке и потребностей в 3-м столбце. Он равен 105. Записываем в скобках в ячейку (2,3) 105 и вычеркиваем 3-й столбец, а запасы 2-й строки уменьшаем на 105 единиц, т.е. 180 - 105 = 75 ед. Таблица 8

	B1	B2	B3	B4	B5	Запасы, ai
А1	14	8	17	5	(110)3	120,10
А2	21	10	(105)7	11	6	180,75
А3	(70)3	(35)5	8	(125)4	9	230,160,35,0
Потребности, bj	70,0	120,85	105,0	125,0	110,0

Вычеркиваем далее 2-й столбец и записываем в ячейку (1,2) 10, а в ячейку (2,2) 75. В результате все запасы и потребности полностью израсходованы. Таблица 9

	B1	B2	B3	B4	B5	Запасы, ai
А1	14	(10)8	17	5	(110)3	120,10,0
А2	21	(75)10	(105)7	11	6	180,75,0
А3	(70)3	(35)5	8	(125)4	9	230,160,35,0
Потребности, bj	70,0	120,85,0	105,0	125,0	110,0

Таким образом, получен базисный план транспортной задачи закрытого типа: Контрольная: Транспортная задача

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

	B1	B2	B3	B4	B5	Запасы, ai
А1	14	(10)8	17	5	(110)3	120
А2	21	(75)10	(105)7	11	6	180
А3	(70)3	(35)5	8	(125)4	9	230
Потребности, bj	70	120	105	125	110

В методе потенциалов каждой i-й строке и j-му столбцу транспортной таблицы ставятся в соответствие числа (потенциалы) ui и vj. Для каждой базисной переменной xij потенциалы удовлетворяют уравнению: ui + vj = cij. В рассматриваемой задаче имеем 8 неизвестных переменных (потенциалов) и 7 уравнений, соответствующих семи базисным переменным. Чтобы найти значения потенциалов из системы уравнений для базисных переменных присвоим одному из потенциалов произвольное значение, и затем последовательно вычислим значения остальных потенциалов. Возьмем для определенности u1 = 0. Имеем таблицу: Таблица 11

Базисные переменные	Уравнения относительно потенциалов	Решение
x12	u1 + v2 = 8	u1 = 0 Þ v2 = 8
x15	u1 + v5 = 3	u1 = 0 Þ v5 = 3
x22	u2 + v2 = 10	v2 = 8 Þ u2 = 2
x23	u2 + v3 = 7	u2 = 2 Þ v3 = 5
x31	u3 + v1 = 3	u3 = -3 Þ v1 = 0
x32	u3 + v2 = 5	v2 = 8 Þ u3 = -3
x34	u3 + v4 = 4	u3 = -3Þ v4 = 7

Далее, используя вычисленные значения потенциалов, для каждой свободной переменной вычислим величины ui + vj - cij. Результаты приведены в таблице 12. Таблица 12

Свободные переменные	Значения ui + vj - cij
x11	u1 + v1 - c11 = 0 + 0 - 14 = -14
x13	u1 + v3 - c13 = 0 + 3 - 17 = -14
x14	u1 + v4 - c14 = 0 + 7 - 5 = 2
x21	u2 + v1 - c21 = 2 + 0 - 21 = -19
x24	u2 + v4 - c24 = 2 + 7 - 11 = -2
x25	u2 + v5 - c25 = 2 + 3 - 6 = -1
x33	u3 + v3 - c33 = -3 + 5 - 8 = -6
x35	u3 + v5 - c35 = -3 + 5 - 9 = -7

Т.к. получили положительное значение ui + vj - cij, то полученное решение не является оптимальным. Введем в базис ту свободную переменную, у которой значение ui + vj - cij является положительным. Это – переменная x14. Строим для нее цикл из четного числа переменных, все вершины которого (кроме самой этой переменной) находятся в занятых клетках. Около свободной клетки цикла ставится знак (+), затем поочередно проставляем знаки (-) и (+):

	(10)(-)		(+)	(110)
	(75)	(105)
(70)	(35)(+)		(125)(-)

У вершин со знаком (-) выбираем минимальный груз, он равен 10. Прибавляем его к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у отрицательных вершин. Получаем новый цикл:

			(10)	(110)
	(75)	(105)
(70)	(45)		(115)

В результате имеем новое опорное решение: Контрольная: Транспортная задача

. Проверим полученное решение на оптимальность. Определим потенциалы строк и столбцов, считаем, для определенности u1 = 0. Имеем таблицу: Таблица 13

Базисные переменные	Уравнения относительно потенциалов	Решение
x14	u1 + v4 = 5	u1 = 0 Þ v4 = 5
x15	u1 + v5 = 3	u1 = 0 Þ v5 = 3
x22	u2 + v2 = 10	u2 = 4 Þ v2 = 6
x23	u2 + v3 = 7	v5 = 3 Þ u2 = 4
x31	u3 + v1 = 3	u3 = -1 Þ v1 = 4
x32	u3 + v2 = 5	v2 = 6 Þ u3 = -1
x34	u3 + v4 = 4	u3 = -1Þ v4 = 5

Далее, используя вычисленные значения потенциалов, для каждой свободной переменной вычислим величины ui + vj - cij. Результаты приведены в таблице 14. Таблица 14

Свободные переменные	Значения ui + vj - cij
x11	u1 + v1 - c11 = 0 + 4 - 14 = -10
x12	u1 + v2 - c12 = 0 + 4 - 8 = -4
x13	u1 + v3 - c13 = 0 + 5 - 17 = -12
x21	u2 + v1 - c21 = 3 + 4 - 21 = -14
x24	u2 + v4 - c24 = 3 + 6 - 11 = -2
x25	u2 + v5 - c25 = 3 + 5 - 6 = 2
x33	u3 + v3 - c33 = -1 + 4 - 8 = -5
x35	u3 + v5 - c35 = -1 + 3 - 9 = -7

Т.к. получили положительное значение ui + vj - cij, то полученное решение не является оптимальным. Введем в базис ту свободную переменную, у которой значение ui + vj - cij является положительным. Это – переменная x24. Строим для нее цикл из четного числа переменных, все вершины которого (кроме самой этой переменной) находятся в занятых клетках. Около свободной клетки цикла ставится знак (+), затем поочередно проставляем знаки (-) и (+):

			(10)	(110)
	(75)(-)	(105)	(+)
(70)	(45)(+)		(115)(-)

У вершин со знаком (-) выбираем минимальный груз, он равен 75. Прибавляем его к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у отрицательных вершин. Получаем новый цикл:

			(10)	(110)
		(105)	(75)
(70)	(120)		(40)

В результате имеем новое опорное решение: Контрольная: Транспортная задача

. Проверим полученное решение на оптимальность. Определим потенциалы строк и столбцов, считаем, для определенности u1 = 0. Имеем таблицу: Таблица 15

Базисные переменные	Уравнения относительно потенциалов	Решение
x14	u1 + v4 = 5	u1 = 0 Þ v4 = 5
x15	u1 + v5 = 3	u1 = 0 Þ v5 = 3
x23	u2 + v3 = 7	u2 = 6 Þ v3 = 1
x24	u2 + v4 = 11	v4 = 5 Þ u2 = 6
x31	u3 + v1 = 3	u3 = -1 Þ v1 = 4
x32	u3 + v2 = 5	u3 = -1 Þ v2 = 6
x34	u3 + v4 = 4	v4 = 5 Þ u3 = -1

Далее, используя вычисленные значения потенциалов, для каждой свободной переменной вычислим величины ui + vj - cij. Результаты приведены в таблице 14. Таблица 16

Свободные переменные	Значения ui + vj - cij
x11	u1 + v1 - c11 = 0 + 4 - 14 = -10
x12	u1 + v2 - c12 = 0 + 6 - 8 = -2
x13	u1 + v3 - c13 = 0 + 1 - 17 = -16
x21	u2 + v1 - c21 = 6 + 4 - 21 = -11
x22	u2 + v2 - c22 = 6 + 6 - 10 = 2
x25	u2 + v5 - c25 = 6 + 3 - 6 = 3
x33	u3 + v3 - c33 = -1 + 1 - 8 = -8
x35	u3 + v5 - c35 = -1 + 3 - 9 = -7

Т.к. получили несколько положительных значений ui + v j - cij, то полученное решение не является оптимальным. Введем в базис ту свободную переменную, у которой значение u i + vj - cij является максимальным. Это – переменная x25. Строим для нее цикл из четного числа переменных, все вершины которого (кроме самой этой переменной) находятся в занятых клетках. Около свободной клетки цикла ставится знак (+), затем поочередно проставляем знаки (-) и (+):

			(10)(+)	(110)(-)
		(105)	(75)(-)	(+)
(70)	(120)		(40)

			(85)	(35)
		(105)		(75)
(70)	(120)		(40)

В результате имеем новое опорное решение: Контрольная: Транспортная задача

. Проверим полученное решение на оптимальность. Определим потенциалы строк и столбцов, считаем, для определенности u1 = 0. Имеем таблицу: Таблица 17

Базисные переменные	Уравнения относительно потенциалов	Решение
x14	u1 + v4 = 5	u1 = 0 Þ v4 = 5
x15	u1 + v5 = 3	u1 = 0 Þ v5 = 3
x23	u2 + v3 = 7	u2 = 3 Þ v3 = 4
x25	u2 + v5 = 6	v5 = 3 Þ u2 = 3
x31	u3 + v1 = 3	u3 = -1 Þ v1 = 4
x32	u3 + v2 = 5	u3 = -1 Þ v2 = 6
x34	u3 + v4 = 4	v4 = 5 Þ u3 = -1

Далее, используя вычисленные значения потенциалов, для каждой свободной переменной вычислим величины ui + vj - cij. Результаты приведены в таблице 14. Таблица 18

Свободные переменные	Значения ui + vj - cij
x11	u1 + v1 - c11 = 0 + 4 - 14 = -10
x12	u1 + v2 - c12 = 0 + 6 - 8 = -2
x13	u1 + v3 - c13 = 0 + 4 - 17 = -13
x21	u2 + v1 - c21 = 3 + 4 - 21 = -14
x22	u2 + v2 - c22 = 3 + 6 - 10 = -1
x24	u2 + v4 - c24 = 3 + 5 - 11 = -3
x33	u3 + v3 - c33 = -1 + 4 - 8 = -5
x35	u3 + v5 - c35 = -1 + 3 - 9 = -7

Т.к. все среди значений ui + vj - cij нет положительных, то полученное решение Контрольная: Транспортная задача

является оптимальным. Минимальные транспортные издержки при этом составят:

Список литературы 1. Дыхнов А.Е., Дягелец И.Д., Тумашев В.И. Математические методы исследования экономики. Часть I. Оптимальное программирование. – Челябинск, УрСЭИ АТиСО, 1999. 2. Ларионов А.И., Юрченко Т.И., Новоселов А.Л. Экономико-математические методы в планировании. – М.: Высшая школа, 1991. 3. Исследование операций в экономике/ Под ред. Н.Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997. 4. Косоруков О.А., Мищенко А.В. Исследование операций. – М.: Экзамен, 2003. 5. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем. М.: Финансы и статистика, 2001.