Решение задачи линейного программирования

4 Решение задачи оптимизации на основе симплекс-метода

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

30x1 + 40x2		+ x3 = 40000;
50x1 +20x2		+ x4 = 32000;
1500x1 +500x2 + x5			= 900000;
x1 + x2 + x6		=1050;	(4.1)
xi	≥ 0, i =1, 6;
xi	−целое	i =1, 2;

E =1500x1 +500x2 → max.

Составим первую симплекс-таблицу:

Таблица 4.1 – 1-ая симплекс-таблица

Базис	x1		x2	x3		x4	x5	x6	Решение
E			−500	0		0	0	0	0
	−1000
x3	50		20	1		0	0	0	32000
x4	30		40	0		1	0	0	40000
x5	1500		500	0		0	1	0	900000
x6	1		1	0		0	0	1	1050

Приведенное в таблице начальное решение ( x1 = 0 , x2 = 0 , x3 = 40000 , x4 = 32000 , x5 = 900000 , x6 =1050 ) является допустимым, но не является оптимальным: признак неоптимальности решения – наличие отрицательных коэффициентов в строке целевой функции E .

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

12

tbicr

Для определения переменной, исключаемой из базиса, найдем симплексные

отношения:
32000/ 50 = 640 ;
40000/ 30 =1333.333 ;	(4.2)
900000/1500 = 600 ;
1050/1 =1050 .

Минимальное симплексное отношение соответствует переменной x5 , значит, эта переменная исключается из базиса. Строка, соответствующая переменной, исключаемой из базиса, называется ведущей.

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

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

пересчитываются по правилу прямоугольника: b'

= (a ×b

2

−a

2

×b ) / a , где

a

– ведущий

2

1

1

1

1

элемент, a2 и b1 – старые значения ведущих строки и столбца, b2 –

старое значение

высчитываемой ячейки, b'

– новое значение высчитываемой ячейки.

2

a1

…

a2

…

…

…

b1

…

b2

Рисунок 4.1

Таблица 4.2 – 2-ая симплекс-таблица

Базис	x1	x2	x3	x4	x5	x6	Решение
E	0	−166.667	0	0	0.667	0	600000
x3	0	3.333	1	0	−0.033	0	2000
x4	0	30	0	1	−0.02	0	22000
x1	1	0.333	0	0	667 ×10−6	0	600
x6	0	0.667	0	0	−667×10−6	1	450

13

tbicr

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

В базис включается переменная x2 .

Для определения переменной, исключаемой из базиса, вычисляются симплексные

отношения:
2000 / 3.333 = 600 ;
22000/ 30 = 733.333 ;	(4.3)
600/ 0.333 =1800 ;
450 / 0.667 = 675.

Минимальное симплексное отношение соответствует переменной x3 , значит, она исключается из базиса.

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

Таблица 4.3 – 3-яя симплекс-таблица

Базис	x1	x2	x3	x4	x5	x6	Решение
E	0	0	50	0	−1	0	700000
x2	0	1	0.3	0	−0.01	0	600
x4	0	0	−9	1	0.28	0	4000
x1	1	0	−0.1	0	0.004	0	400
x6	0	0	−0.2	0	0.006	1	50

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

В базис включается переменная x5 .

Для определения переменной, исключаемой из базиса, вычисляются симплекс

отношения:
4000/ 0.28 =14285.714 ;
400 / 0.004 =100000 ;	(4.4)
50 / 0.006 =8333.333.
14	tbicr

Минимальное симплексное отношение соответствует переменной x6 , значит, она исключается из базиса.

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

Таблица 4.4 – 4-ая симплекс-таблица

Базис	x1	x2	x3	x4	x5	x6	Решение
E	0	0	16.667	0	0	166.667	708333.333
x2	0	1	0.033	0	0	1.667	683.333
x4	0	0	0.333	1	0	−46.667	1666.667
x1	1	0	0.033	0	0	−0.667	366.667
x5	0	0	−33.333	0	1	166.667	8333.333

Получено оптимальное решение (признак его оптимальности - отсутствие отрицательных коэффициентов в строке целевой функции). Основные переменные задачи приняли следующие значения:

x1 = 366.667 ;	(4.5)
x2 = 683.333 .	(4.6)
Это означает, что необходимо выпускать 366.667	автомобилей «Шторм» и

683.333 автомобилей «Торнадо».

Значение целевой функции E = 708333.333 показывает, что прибыль при таком выпуске автомобилей оставит 708333.333 ден. ед.

Остаточная переменная x3 = 0 означает, что количество неиспользуемого времени

квалифицированного труда равно нулю
Остаточная переменная	x4 =1666.667	означает,	что не используется 1666.667
часов неквалифицированного труда.
Остаточная переменная	x5 = 8333.333	означает,	что возможны еще затраты на
выпуск автомобилей в размере 8333.333 ден. ед.
Остаточная переменная	x6 = 0 означает, что на заводе выпускается максимально
возможное количество автомобилей.
	15		tbicr

Данное решение не является целочисленным, поэтому в пункте 6. «Определение оптимального целочисленного решения» решим задачу методом ветвей и границ.

16

tbicr

5Анализ базовой модели на чувствительность

5.1Статус и ценность ресурсов

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

Статус и ценность ресурсов определяется в нашем случае из остаточных переменных.

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

Ценность ресурсов представляет собой коэффициенты Е-строки при остаточных переменных, соответствующих остаткам ресурсов, в симплекс-таблице с оптимальным решением.

Ценность квалифицированного труда равна 16.667 ден. ед. При увеличении квалифицированной работы на один час предприятие повышает прибыль на 16.667 ден. ед., при увеличение на одного рабочего – на 16.667×40 = 666.667 ден. ед.

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

Ценность неквалифицированного труда равна нулю.

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

Ценность ресурса «затраты на выпуск автомобилей» равна нулю.

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

Ценность ресурса «вывоз автомобилей» равна 166.667 ден. ед. При увеличении вывоза на один автомобиль прибыль предприятия повысится на 166.667 ден. ед.

Из значений ценности ресурсов можно сделать выводы:
17	tbicr

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

Из полученных результатов видно, что на предприятии небольшие остатки не дефицитных ресурсов.

Загруженность неквалифицированных рабочих составляет:

	32000 −1666.667	×100% = 94.8% .	(5.1)
	32000

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

	900000 −8333.333	×100% = 99.1% .	(5.2)
	900000

То есть на автозаводе хороший баланс ресурсов.

5.2Анализ на чувствительность к изменению количества часов квалифицированного труда

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

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

Новое оптимальное решение определяется следующим образом:

x1	= 366.667 +0.033d ;
x2	= 683.333 −0.033d ;
x4	=1666.667 +0.333d ;	(5.2.1)

18

tbicr

x5 = 8333.333 −33.333d ;

E = 708333.333 +16.667d .

Пусть, например, доступное количество часов квалифицированного труда будет составлять не 32000, а 36000 часов, что может быть связано с увеличением числа квалифицированных рабочих на 100 человек. При этом d = 4000 . Тогда найдем новое оптимальное решение:

x1	= 366.667 +0.033×4000 = 500 ;
x2	= 683.333 −0.033×4000 = 550 ;
x4	=1666.667 +0.333×4000 = 3000;	(5.2.2)
x5	= 8333.333 −33.333×4000 = −125000 ;

E = 708333.333 +16.667×250 = 775000.

Одна из переменных приняла отрицательное значение, что недопустимо по физическому смыслу. Это значит, что для поиска оптимального решения в новых условиях требуется решить задачу заново, изменив ограничение на доступное количество квалифицированного труда.

Пусть доступное количество часов квалифицированного труда будет составлять не 32000, а 30000 часов. При этом d = −2000. Тогда найдем новое оптимальное решение:

x1	= 366.667 +0.033×(−2000) = 300 ;
x2	= 683.333 −0.033×(−2000) = 750 ;
x4	=1666.667 +0.333×(−2000) =1000 ;	(5.2.3)
x5	=8333.333 −33.333×(−2000) = 75000 ;

E = 708333.333 +16.667×250 = 675000.

Таким образом, в новых условиях завод должен будет производить 300 автомобилей «Шторм» и 750 автомобилей «Торнадо». При этом количество часов неиспользуемого неквалифицированного труда уменьшится на 666.667 часов, неиспользуемые средства на выпуск автомобилей увеличится на 66666.667 ден. ед. Остальные значения переменных останутся неизменными. Будет получена прибыль в

19

tbicr

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

квалифицированного труда приведет к уменьшению прибыли.
	Найдем значения	d , при которых состав переменных в оптимально базисе не
изменится
x1	= 366.667 +0.033d ≥ 0 ;		d ≥ −366.667 / 0.033;	d ≥ −11000;
x2	= 683.333 −0.033d ≥ 0 ;		d ≤ 683.333/ 0.033 ;	d ≤ 20500 ;	(5.2.4)
x4	=1666.667 +0.333d ≥ 0 ;		d ≥ −166.667 / 0.333;	d ≥ −5000;
x5	= 8333.333 −33.333d ≥ 0 ;		d ≤8333.333/ 33.333;	d ≤ 250 .
	При d [−5000,	250]	количество часов квалифицированного		труда будет

изменяться от 27000 до 32250 часов. При этом состав переменных в оптимально базисе не изменится. Прибыль предприятия будет изменяться в пределах от

708333.333 +16.667 ×(−5000) = 625000 ден. ед. до 708333.333 +16.667 ×250 = 712500 ден.

ед. То есть при уменьшении часов квалифицированного труда прибыль предприятия уменьшается, при увеличении – увеличивается.

5.3 Анализ на чувствительность к изменению стоимости автомобиля «Шторм»

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

Пусть прибыль от продажи одного автомобиля «Шторм» изменилась на d ден. ед., то есть составляет 1000 +d ден. ед. Для анализа влияния этого изменения на оптимальное решение используются коэффициенты симплекс-таблицы, соответствующей оптимальному решению, из строки x1 , так как для этой переменной изменился коэффициент целевой функции. Новые значения E-строки определяются следующим образом:

F3	=16.667 +0.033d ;
F6	=166.667 −0.667d ;	(5.3.1)
E = 708333.333 +366.667d .

20

tbicr

Пусть, например, прибыль от продажи одного автомобиля «Шторм» снизится до 950 ден. ед., что может быть связано со снижением цены на него из-за низкой рентабельности. При этом d = −50 . Тогда найдем новое оптимальное решение:

F3	=16.667 +0.033×(−50) =15 ;
F6	=166.667 −0.667 ×(−50) = 200 ;	(5.3.2)
E = 708333.333 +366.667 ×(−50) = 690000 .

Коэффициенты E-строки остались неотрицательными. Это означает, что оптимальное решение не изменилось. Таким образом, в новых условиях изменится ценность ресурсов квалифицированного труда и вывоза автомобилей, а прибыль будет составлять 690000 , то есть снижение прибыли от выпуска автомобилей, как и следовало ожидать, приведет к снижению прибыли.

Найдем значения d , при которых остается оптимальным решение, найденное для исходной постановки задачи. Условием оптимальности решения является неотрицательность всех коэффициентов E-строки:

F3	=16.667 +0.033d ≥ 0 ;	d ≥ −16.667 / 0.033;	d ≥ −500 ;	(5.3.3)
F6	=166.667 −0.667d ≥ 0 ;	d ≤166.667 / 0.667 ;	d ≤ 250 .
	При d [−500, 250]	прибыль от продажи одного автомобиля «Шторм» будет

изменяться от 1000 ден. ед. до 1750 ден. ед. При этом решение, найденное для исходной постановки задачи, будет оптимально. Если прибыли выйдет за эти пределы, то для получения оптимального решения потребуется решить задачу заново (новое оптимальное решение будет отличаться от прежнего не только значениями, но и составом переменных в оптимальном базисе). Прибыль предприятия будет изменяться в пределах от

708333.333 +366.667 ×(−500) = 525000 ден. ед. до 708333.333 +366.667 ×250 =800000

ден. ед.

21

tbicr