Типовые математические модели экономических задач линейного программирования

метки: Решение, Значение, Транспортный, Ячейка, Задача, Перевозка, Фактически, Поставщик

x 1	x 2

1. Для производства двух видов продукции I и II с планом x ₁ и x ₂ единиц составить математическую модель, т.е. целевую функцию прибыли F и соответствующую систему ограничений по запасам сырья, предполагая, что требуется изготовить в сумме не менее n единиц обоих видов продукции.

2. Найти оптимальный план X *= (x ₁ , x ₂ ) производства продукции, обеспечивающий максимальную прибыль F _max . Определить остатки каждого вида сырья. Задачу решить симплекс-методом.

3. Построить по полученной системе ограничений многоугольник допустимых решений и найти оптимальный план производства геометрическим методом. Определить максимальную прибыль F _max .

4. Составить математическую модель двойственной задачи (систему ограничений по единичной прибыли и целевую функцию общих издержек на сырье Z ); найти оптимальный набор цен на сырьё Y *= (y ₁ , y ₂ , y ₃ ), обеспечивающий минимум общих затрат на сырье Z _min .

5. Провести анализ первоначальных и дополнительных переменных исходной и двойственной задач, сделать выводы.

6. Решить задачу оптимизации в MS Excel в режиме «поиск решения». Провести исследование полученного решения, используя отчеты по результатам, по устойчивости, по пределам; сделать выводы. Ответы, полученные в результате решений «вручную» и с помощью Excel, должны совпадать.

Решение:

Предположим, что будет использовано х ₁ сырья А для изготовления продукции I, х₂ сырья для изделия II. Тогда общая прибыль составит 6х₁ + 5х₂ .

Так как общее количество сырья А не может превышать 27 единиц, то должно выполняться следующее неравенство:

3х ₁ +2х₂ ? 27.

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

х ₁ + х₂ ? 10;

2х ₁ + 5х₂ ? 35.

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

х ₁ ? 0, х₂ ? 0 (1)

Пусть F — прибыль предприятия, так как по условию необходимо составить план производства двух видов изделий, обеспечивающий максимальную прибыль, следовательно, функция F, при условии, что изготовлено х ₁ единиц изделий I и х₂ единиц изделий II будет максимизироваться:

F = 6х ₁ + 5х₂ > max

Таким образом, мы приходим к следующей математической задаче:

Дана система:

(2)

трех линейных неравенств с двумя неизвестными х _i (i=1,2).

И линейная функция относительно этих же переменных:

F = 6х ₁ + 5х₂ (3)

требуется среди всех неотрицательных решений системы неравенств (2), найти такое, при котором функция (3) примет максимальное значение.

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

Прямые S1 — S3, изображены на рисунке 1.

Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой — нет. Определим искомую полуплоскость через точку О (0; 0).

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

Рис. 1. Многоугольник решений

Как видно из рисунка 1, многоугольником решений является пятиугольник ОАВСD.

Таким образом, среди точек пятиугольника ОАВСD нам нужно найти такие, в которых функция F = 6х ₁ + 5х₂ принимает максимальное значение. Для нахождения этих точек построим нулевую линию уровня (F₀ ) 6х₁ + 5х₂ = 0 и вектор N = (12;10).

Передвигая данную прямую параллельно самой себе в направлении вектора N, видим, что ее последней точкой с многоугольником решений задачи является точка C. Следовательно, в этой точке функция F принимает максимальное значение. Так как C — точка пересечения прямых S1 и S3, то ее координаты удовлетворяют уравнениям этих прямых:

Решив эту систему уравнений мы получили: х ₁ = 7 и х₂ = 3.

Таким образом, максимальное значение функции F _max = 6*7+5*3 = 42 + 15 = 57.

Решение симплекс-методом

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

х ₁ , х₂ ? 0

F = 6х ₁ + 5х₂

Запишем эту задачу в форме основной задачи ЛП:

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

Преобразованную систему ограничений запишем в векторной форме:

Поскольку среди векторов Р ₁ -Р₅ имеются 3 единичных вектора, для данной задачи можно непосредственно записать опорный план.

Таковым является план Х = (0; 0; 0; 27; 10; 35), определяемый системой трехмерных единичных векторов Р ₃ , Р₄ , Р₅ , которые образуют базис трехмерного векторного пространства.

Составим симплексную таблицу для I итерации (таб.1), подсчитав значения F ₀ , z_i — c_i и проверяем исходный план на оптимальность.

F ₀ = (c, P₀ ); z₁ = (c, P₁ ) = 0; z₂ = (c, P₂ ) = 0; z₃ = (c, P₃ ) = 0;

z ₄ = (c, P₄ ) = 0; z₅ = (c, P₅ ) = 0;

z ₁ — c₁ = 0 — 6= — 6; z₂ — c₂ = 0 — 5 = — 5. Для векторов базиса z_i — c_i = 0.

Таблица 1

i	Базис	Ц б	Р 0	6	5	0	0	0
				Р 1	Р 2	Р 3	Р 4	Р 5
1	Р 3	0	27	3	2	1	0	0
2	Р 4	0	10	1	1	0	1	0
3	Р 5	0	35	2	5	0	0	1
4			0	-6	-5	0	0	0

Таким образом, по 4 строке таблицы 1 видно, что план не оптимален, т.к. значения z _i — c_i — отрицательны.

Далее определяем вектор, подлежащий исключению из базиса. Для этого находим Q _{0 min} (b_i /a_{i 1} ) для a_{i 1} >0 и Q_{0 min} (b_i /a_{i 2} ) для a_{i 2} >0.

Таким образом, Q _{0 min} (b_i /a_{i 1} ) = min (27/3; 10/1; 35/2) = 27/3, а Q_{0 min} (b_i /a_{i 2} ) = min (27/2; 10/1; 35/5) = 35/5. Min (27/3; 35/5) = 35/5.

Таким образом, мы нашли разрешающий элемент, находящийся на пересечении 2-ой строки и столбца вектора Р ₂ .

Следовательно, вектор Р ₄ подлежит исключению из базиса.

Столбец вектора Р ₂ и вторая строка являются направляющими.

Далее, составляем таблицу для итерации II (таб.2).

Сначала заполняем строку вектора вновь введенного в базис. Элементы этой строки таб.3 получаются из соответствующих элементов таб.2 делением на разрешающий элемент.

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

Для определения остальных элементов таб. 2 применяем правило прямоугольника.

Данный цикл продолжается до тех пор, пока все значения z _i — c_i — не станут положительными.

Таким образом, в таб. 2 мы запишем все итерации вычислительного процесса.

Таблица 2

i	Базис	Ц б	Р 0	6	5	0	0	0
				Р 1	Р 2	Р 3	Р 4	Р 5
1	Р 3	0	13	2,2	0	1	0	-0,4
2	Р 4	0	3	0,6	0	0	1	-0,2
3	Р 2	5	7	0,4	1	0	0	0,2
4			35	-4	0	0	0	1
1	Р 3	0	2	0	0	1	-3,6	0,3
2	Р 1	6	5	1	0	0	1,6	-0,3
3	Р 2	5	5	0	1	0	-0,6	0,3
4			55	0	0	0	6,6	-0,3
1	Р 5	0	6,6	0	0	3,3	-12	1
2	Р 1	6	7	1	0	1	-2	0
3	Р 2	5	3	0	1	-1	3	0
4			57	0	0	1	3	0

Итак, среди значений z _i — c_i нет отрицательных, следовательно, опорный план оптимален и F_max = 57.

Двойственная задача

Прямая задача имеет вид:

х ₁ , х₂ ? 0

F = 6х ₁ + 5х₂

Хопт. = (7;3).

Max F = 57.

Составим двойственную модель и с помощью теорем двойственности найдем оптимальное решение двойственной модели:

Двойственная модель:

Z = 27y ₁ + 101y₂ + 35y₃ > min

Так как мы уже нашли решение исходной задачи (таб.2), следовательно, мы нашли и решение двойственной задачи: y ₁ = 1; y₂ = 3; y₃ = 0. (итерация III в симплекс-таблице 2).

Таким образом оптимальное решение двойственной задачи = y _опт (1; 3; 0).

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

Z = 27*1+10*3+35*0 = 27+30+0 = 57, итак, Z = F = 57.

Отчет по результатам:

Microsoft Excel 12.0 Отчет по результатам
Рабочий лист: [Рудометов ЭММ — решение. xlsx] Задача ЛП
Отчет создан: 01.10.2012 12: 12: 54
Целевая ячейка (Максимум)
	Ячейка	Имя	Исходное значение	Результат
	$D$10	оптимальные значения целевая функция	57	57
Изменяемые ячейки
	Ячейка	Имя	Исходное значение	Результат
	$B$10	оптимальные значения х1*	7	7
	$C$10	оптимальные значения х2*	3	3
Ограничения
	Ячейка	Имя	Значение	Формула	Статус	Разница
	$D$5	коэф в 1 ограничении левая часть	27	$D$5<=$F$5	связанное	0
	$D$6	коэф во 2 ограничении левая часть	10	$D$6<=$F$6	связанное	0
	$D$7	коэф в 3 ограничении левая часть	29	$D$7<=$F$7	не связан.	6
	$B$10	оптимальные значения х1*	7	$B$10>=0	не связан.	7
	$C$10	оптимальные значения х2*	3	$C$10>=0	не связан.	3

Отчет по пределам

Microsoft Excel 12.0 Отчет по пределам
Рабочий лист: [Рудометов ЭММ — решение. xlsx] Отчет по пределам 1
Отчет создан: 01.10.2012 12: 13: 25
		Целевое
	Ячейка	Имя	Значение
	$D$10	оптимальные значения целевая функция	57
		Изменяемое			Нижний	Целевой		Верхний	Целевой
	Ячейка	Имя	Значение		предел	результат		предел	результат
	$B$10	оптимальные значения х1*	7		0	15		7	57
	$C$10	оптимальные значения х2*	3		0	42		3	57

Отчет по устойчивости:

Microsoft Excel 12.0 Отчет по устойчивости
Рабочий лист: [Рудометов ЭММ — решение. xlsx] Задача ЛП
Отчет создан: 01.10.2012 12: 13: 13
Изменяемые ячейки
			Результ.	Нормир.
	Ячейка	Имя	значение	градиент
	$B$10	оптимальные значения х1*	7	0
	$C$10	оптимальные значения х2*	3	0
Ограничения
			Результ.	Лагранжа
	Ячейка	Имя	значение	Множитель
	$D$5	коэф в 1 ограничении левая часть	27	1
	$D$6	коэф во 2 ограничении левая часть	10	3
	$D$7	коэф в 3 ограничении левая часть	29	0

Потребности Запасы	В 1	В 2	В 3
	b 1 =190	b 2 =120	b 3 =400
А 1	а 1 = 100	4	2	4
А 2	а 2 = 200	3	5	3
А 3	а 3 = 90	1	5	6

1. Сравнивая суммарный запас и суммарную потребность в грузе, установить, является ли модель транспортной задачи открытой или закрытой. Если модель открытая, то ее необходимо закрыть, добавив фиктивный склад А ₄ с запасом а ₄ =b —а в случае а <b или фиктивного потребителя В ₄ с потребностью b ₄ =a —b в случае а >b и положив соответствующие им тарифы перевозок нулевыми.

2. Составить первоначальный план перевозок методом северо-западного угла и методом наименьшей стоимости.

3. Методом потенциалов проверить первоначальный план перевозок на оптимальность в смысле суммарной стоимости перевозок, и если это не так, то составить оптимальный план

обеспечивающий минимальную стоимость перевозок . Найти эту стоимость.

поиск решения»

Решение:

Потребность = 190+120+400 = 710

Возможности = 100+200+90 = 390

Таким образом, данная транспортная задача (ТЗ) — открытая.

Следовательно для решения такой задачи необходимо ввести фиктивного поставщика — А4, имеющего запасы груза равные 320 единиц, тем самым мы сбалансировали спрос и предложение (таблица 4).

Таблица 4

Поставщик	Потребитель	Запасы груза
	В1	В2	В3
А1	4	2	4	100
А2	3	5	3	200
А3	1	5	6	90
А4	0	0	0	320
Потребность	190	120	400	710

Составим первоначальный план по методу северо-западного угла (таблица 5).

Таблица 5

Поставщик	Потребитель	Запасы груза
	В1	В2	В3
А1	100 4	2	4	100
А2	90 3	110 5	3	200
А3	1	10 5	80 6	90
А4	0	0	320 0	320
Потребность	190	120	400	710

n+m — 1 =4+3-1 = 6 — соответствует числу заполненных клеток

Общие транспортные издержки равны:

Z ₁ = 100*4+90*3+110*5+10*5+80*6+320*0 = 400+270+550+50+480+0 = 1750

Проверим составленный план на оптимальность методом потенциалов.

Рассчитаем потенциалы, исходя из того, что потенциал строки А1 = 0 (таблица 6).

Таблица 6

Поставщик	Потребитель	Запасы груза
	В1	В2	В3
А1	100 4	2	4	100	U1=0
А2	90 3	110 5	3	200	U2=
А3	1	10 5	80 6	90	U3=
А4	0	0	320 0	320	U4=
Потребность	190	120	400	710
	V1=	V2=	V3=

Далее, рассчитаем теневые цены (таблица 7 — теневые цены выделены серым цветом).

Таблица 7

Поставщик	Потребитель	Запасы груза
	В1	В2	В3
А1	100 4	-4 2 +	-3 4	100	U1=0
А2	90 3 +	110 5	-3 3	200	U2=-1
А3	-2 1	10 5	80 6	90	U3=-1
А4	3 0	1 0	320 0	320	U4=-7
Потребность	190	120	400	710
	V1=4	V2=6	V3=7

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

Объем перевозимого груза численно равен минимальному значению из тех объемов груза, которые указаны в клетках со знаком минус. Таким образом, min (100; 110) = 100.

Итак, составляем новый план (таблица 8).

Данный цикл длится до тех пор, пока все теневые цены не станут положительными.

Таблица 8

Поставщик	Потребитель	Запасы груза
	В1	В2	В3
А1	4 4	100 2	1 4	100	U1=0
А2	190 3	10 5	-3 3 +	200	U2=3
А3	-2 1	10 5 +	80 6	90	U3=3
А4	3 0	1 0	320 0	320	U4=-3
Потребность	190	120	400	710
	V1=0	V2=2	V3=3

n+m — 1 =4+3-1 = 6 — соответствует числу заполненных клеток

Общие транспортные издержки равны:

Z ₂ = 190*3+100*2+10*5+10*5+80*6+320*0 = 570+200+50+50+480+0 = 1350

Таблица 9

Поставщик	Потребитель	Запасы груза
	В1	В2	В3
А1	1 4	100 2	1 4	100	U1=0
А2	190 3	3 5	10 3 +	200	U2=0
А3	-5 1 +	20 5	70 6	90	U3=3
А4	0 0	1 0	320 0	320	U4=-3
Потребность	190	120	400	710
	V1=3	V2=2	V3=3

n+m — 1 =4+3-1 = 6 — соответствует числу заполненных клеток

Общие транспортные издержки равны:

Z ₃ = 190*3+100*2+20*5+10*3+70*6+320*0 = 570+200+100+30+420+0 = 1320

Таблица 10

Поставщик	Потребитель	Запасы груза
	В1	В2	В3
А1	6 4	100 2	6 4	100	U1=0
А2	120 3	-2 5	80 3 +	200	U2=5
А3	70 1 +	20 5	5 6	90	U3=3
А4	0 0	-4 0 +	320 0	320	U4=2
Потребность	190	120	400	710
	V1=-2	V2=2	V3=-2

n+m — 1 =4+3-1 = 6 — соответствует числу заполненных клеток

Общие транспортные издержки равны:

Z ₄ = 120*3+70*1+100*2+20*5+80*3+320*0 = 360+70+200+100+240+0 = 970

Таблица 11

Поставщик	Потребитель	Запасы груза
	В1	В2	В3
А1	6 4	100 2	6 4	100	U1=0
А2	100 3	2 5	100 3	200	U2=1
А3	90 1	4 5	5 6	90	U3=-1
А4	0 0	20 0	300 0	320	U4=-2
Потребность	190	120	400	710
	V1=2	V2=2	V3=2

n+m — 1 =4+3-1 = 6 — соответствует числу заполненных клеток

Общие транспортные издержки равны:

Z ₅ = 100*3+90*1+100*2+20*0+100*3+300*0 = 300+90+200+0+300+0 = 890

В таблице 11 все теневые цены — положительные, следовательно, план оптимален.

Решение задачи в MS Excel.

Исходными данными для решения транспортной задачи являются:

• матрица транспортных расходов;
• предложение поставщиков;
• спрос потребителей.

Рабочий лист excel с введенными исходными данными для решения транспортной задачи показан на рисунке 2.

Рис. 2 — Рабочий лист EXCEL с введенными исходными данными для решения транспортной задачи

Рабочий лист EXCEL с размеченными блоками ячеек показан на рисунке 3.

Рис. 3 — Рабочий лист EXCEL с размеченными блоками ячеек

Формирование элементов математической модели.

Элементами математической модели транспортной задачи являются следующие суммы:

• фактически реализовано;
• фактически получено.

Для нашей задачи m=4, n=3.

Рассмотрим процесс формирования этих сумм на рабочем листе EXCEL.

Вначале сформируем, в блоке «Фактически реализовано»

1. Заполняем ячейки блока «Матрица перевозок» числом 0,01.

2. Селектируем первую ячейку блока «Фактически реализовано»;

3. Наводим курсор на кнопку автосуммирование и щелкаем левой клавишей мыши;

4. Нажимаем клавишу Delete;

5. Селектируем первую строку блока «Матрица перевозок»;

6. Нажимаем клавишу Enter;

7. Копируем формулу из первой ячейки блока «Фактически реализовано» на все остальные ячейки этого блока.

Сформируем теперь — в блоке «Фактически получено».

Для этого выполните следующие действия:

1. Селектируем первую ячейку блока «Фактически получено»;

2. Наводим курсор на кнопку автосуммирование и щелкаем левой клавишей мыши;

3. Нажимаем клавишу Delete;

4. Селектируем первый столбец блока «Матрица перевозок»;

5. Нажимаем клавишу Enter;

6. Копируем формулу из первой ячейки блока «Фактически получено» на остальные ячейки этого блока.

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

Для ввода этих формул выполняем следующие действия:

1. Селектируем первую ячейку блока «Транспортные расходы»;

2. Наводим курсор на кнопку автосуммирование и щелкаем левой клавишей мыши;

3. Нажимаем клавишу Delete;

4. Селектируем первый столбец блока «Матрица Транспортных расходов»;

5. Нажимаем клавишу *;

6. Селектируем первый столбец блока «Матрица перевозок»;

7. Активируем строку формул, наведя на нее курсор и щелкнув затем левой клавишей мыши;

8. Нажимаем одновременно три клавиши: «CTRL» + «SHIFT» + «ENTER»;

9. Копируем формулу в остальные ячейки блока «Транспортные расходы»;

• Сформируем теперь целевую функцию транспортной задачи, в ячейку «Итого расходы». Для этого:
• Селектируем ячейку «Итого расходы»;

1. Наводим курсор на кнопку автосуммирование и щелкаем левой клавишей мыши;

2. Нажимаем клавишу Delete;

3. Селектируем блок ячеек «Транспортные расходы»;

4. Нажимаем клавишу Enter;

• После формирования элементов математической модели и целевой функции транспортной задачи рабочий лист EXСEL примет вид, показанный на рисунке 4.

Рис. 4 — Формирования элементов математической модели и целевой функции транспортной задачи

Далее, приступаем к решению задачи с помощью программы «Поиск решения».

Параметры программы «Поиск решения» представлены на рисунке 5.

Рис. 5 — Параметры программы «Поиск решения»

Результаты решения представлены на рисунке 6.

Рис. 6 — Результаты решения транспортной задачи

1. Венцель Е.С. Исследование операций. Задачи, принципы, методология [Текст]: учеб. пособие для вузов / Е.С. Венцель. — 3-е изд., стереотип. — М.: Дрофа, 2004.

2. Конюховский П.В. Математические методы исследования операций в экономике [Текст]: учеб. пособие / П.В. Конюховский. — СПб.: Питер, 2000.

3. Стариков А.В. Экономико-математическое и компьютерное моделирование [Текст]: учеб. пособие / А.В. Стариков, И.С. Кущева; Фед. агентство по образованию, ГОУ ВПО «ВГЛТА». — Воронеж, 2008.

4. Хазанова Л.Э. Математические методы в экономике [Текст]: учеб. пособие / Л.Э. Хазанова. — 2-е изд., испр. и перераб. — М.: Изд-во БЕК, 2002.

5. Excel для экономистов и менеджеров [Текст] / А.Г. Дубина [и др.]. — СПб.: Питер, 2004.