МУ ЭММ _часть 1_

21

многоугольники, точки которых не удовлетворяют тем или иным ограничениям.

Точки, удовлетворяющие всем ограничениям – это точки нашего многоугольника. Его границы соответствуют сырьевым ресурсам.

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

Во-первых, область допустимых планов непуста и ограничена. Следовательно, оптимальный план существует.

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

Определение оптимального плана методом перебора вершин

Для нахождения оптимального плана необходимо найти координаты вершин многоугольника OABCD допустимых планов, подставить значение х1 и х2 в целевую функцию и найти максимальное значение целевой функции F.

Координаты вершины О (0; 0). Подставим значение х1 и х2 в целевую функцию и получим F = 15 0 + 10 0 = 0.

Координаты вершины А (0; 3,83). Подставим значение х1 и х2 в целевую функцию и получим F = 15 0 + 10 3,83 = 38,3.

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

связывающей ресурсы Электроэнергия и Оборудование:

3x1 7x2 29,x1 6x2 23.

Решив систему уравнений, получаем координаты вершины (1,18; 3,64). Подставим значение х1 и х2 в целевую функцию и получим

F = 15 1,18 + 10 3,64 = 54,1.

Координаты вершины С определяются из системы уравнений, связывающей ресурсы Электроэнергия и Сырье:

3x1 7x2 29,3x1 x2 18.

Решив систему уравнений, получаем координаты вершины (5,39; 1,83). Подставим значение х1 и х2 в целевую функцию и получим

F = 15 5,39 + 10 1,83 = 99,15.

22

Координаты вершины D (6; 0). Подставим значение х1 и х2 в целевую функцию и получим F = 15 6 + 10 0 = 90.

Максимальное значение целевой функции, равное 99,15, достигается в вершине C с координатами (5,39; 1,83). Т.е. для получения наибольшей стоимости выпущенной продукции, равной 99,15 денежных единиц, предприятие должно выпустить 5,39 единиц продукта А и 1,83 единиц продукта В.

Построение градиента и определение оптимального плана

Обратимся

к

целевой функции. Ее

градиент есть вектор

F

F

15x 10x

2

15x 10x

2

gradZ

;

1

;

1

= (15; 10). Для

x1

x1

x2

x2

решения задачи следует изобразить этот вектор в виде стрелки с началом в точке (0; 0) и концом в точке (15; 10), а также учесть ее направление.

Целевая функция задачи геометрически изображается с помощью прямой уровня, т.е. прямой, на которой F = c1x1 + c2x2 принимает постоянное значение, равное С. Если С произвольная константа, то уравнение прямой уровня имеет вид c1x1 + c2x2 = C. Все линии уровня целевой функции параллельны друг другу и перпендикулярны градиенту.

На рис. 5 пунктиром изображены линии уровня целевой функции (ЛУЦФ), соответствующие различным значениям целевой функции. Точкой минимума функции F будет точка первого касания линии уровня с областью допустимых планов. Точкой максимума точка отрыва линии уровня от допустимого многоугольника.

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

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

Таким образом, точка C является оптимальным планом задачи. Это единственная точка, принадлежащая одновременно области допустимых планов и линии уровня в ее крайнем положении. Следовательно, наша задача обладает единственным оптимальным планом.

Выше были рассчитаны координаты точки С (5,39; 1,83).

Таким образом, оптимальный план предписывает выпустить 5,39 единиц продукции А и 1,83 единиц продукции В.

А оптимум целевой функции Fmax = 15 5,39 + 10 1,83 = 99,15 денежных единиц.

x2

10

9

8

7

6

5

4

A

3

2

1

-2 -1 0 -1

-2

23

3x1 + x2 = 18

B

														x1 + 6x2 = 23
										C
													3x1 + 7x2 = 29
											D
1		2		3		4		5		6		7		8		9 10 x1

ЛУЦФ 15x1 + 10x2 = 15

Рис. 5. Решение задачи методом градиента

2.3. Решение задачи линейного программирования методом симплекс таблиц

Выше для примера была сформулирована экономико-математическая модель задачи:

F = 15x1 + 10x2 max,

3x1 7x2 29,3x1 x2 18,

x1 6x2 23, x1, x2 0.

24

Чтобы привести модель задачи к каноническому виду, необходимо систему ограничений-неравенств привести к системе ограниченийравенств. Для этого к левой части каждого неравенства прибавим добавочные неотрицательные переменные х3, x4, x5. Эти добавочные переменные в условиях данной задачи имеют конкретное экономическое содержание, т.е. объем остатков ресурса каждого вида после выполнения плана выпуска продукции.

Задача линейного программирования в канонической форме имеет вид:

F = 15x1 + 10x2 max,

3x1 7x2 x3 29,3x1 x2 x4 18,

x1 6x2 x5 23, x1, x2 0.

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

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

Положив свободные переменные х1, х2, равными нулю, получим первое базисное решение (0; 0; 29; 18; 23), которое оказалось допустимым. Переходим сразу к этапу поиска оптимального решения задачи.

I шаг. Базисные переменные х3, х4, х5. Составляем первую симплекстаблицу и находим разрешающий элемент.

		Базисные				Свободные								х1			х2			х3			х4			х5
	переменные							члены
		х3									29		3			7				1		0			0
		х4									18			3			1			0			1			0
		х5									23		1			6				0		0			1
		F									0		-15			-10				0		0			0
Базисное решение F = 0												(0; 0; 29; 18; 23).
x		min	29	;	18		;		23		min 9,67;6;23 6 .
1				3
		3							1

25

II шаг. Базисные переменные х3, х1, х5. Составляем новую симплекстаблицу.

Базисные	Свободные	х1		х2		х3	х4	х5
переменные	члены
х3	11	0	6			1	-1	0
x1	6	1	0,33			0	0,33	0
х5	17	0	5,67			0	-0,33	1
F	90	0	-5			0	5	0
Базисное решение F = 90		(6; 0; 11; 0; 17).

Так как строка целевой функции содержит отрицательное значение, находим разрешающий элемент:

	11					6		17		min 1,83;18;3 1,83.
	x2 min			;			;
			6			0,33
								5,67
	III шаг. Базисные переменные х2, х1, х5. Переходим к следующей
таблице.
	Базисные					Свободные				х1	х2	х3	х4	х5
	переменные					члены
	x2							1,83		0	1	0,17	-0,17	0
	x1							5,39		1	0	-0,06	0,39	0
	х5							6,61		0	0	-0,94	0,61	1
	F							99,17		0	0	0,83	4,17	0

Эта таблица является последней, потому что в строке целевой функции все элементы положительные. Тогда оптимальным будет решение (5,39; 1,83; 0; 0; 6,61) при котором Fmax = 99,17.

Т.е. для получения наибольшего дохода, равного 99,17 денежных единиц, предприятие должно выпустить 5,39 единиц продукции вида А и 1,83 единицы продукции В. При этом ресурсы Электроэнергия и Сырье будут использованы полностью, а 6,61 единиц ресурса Оборудования останутся неизрасходованными.

2.4. Двойственный анализ задачи линейного программирования

Выше для примера была сформулирована экономико-математическая модель задачи:

F = 15x1 + 10x2 max,

3x1 7x2 29,3x1 x2 18,

x1 6x2 23, x1, x2 0.

Теперь сформулируем двойственную задачу (см. п. 1.4. Элементы теории двойственности в задачах линейного программирования). Пусть

26

некая организация решила закупить все ресурсы рассматриваемого предприятия. При этом необходимо установить оптимальную цену на приобретаемые ресурсы у1, у2, у3, исходя из следующих объективных условий:

1)покупающая организация старается минимизировать общую стоимость ресурсов;

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

Согласно первому условию общая стоимость сырья выразится

величиной Z = 29у1 + 18у2 + 23у3 min.

Согласно второму требованию вводятся ограничения: на единицу продукции А расходуются три единицы первого ресурса (Электроэнергия) ценой у1, три единицы второго ресурса (Сырье) ценой у2, одна единица третьего ресурса (Оборудование) ценой у3. Стоимость всех ресурсов, расходуемых на производство единицы первого вида продукции, равна 3у1 + 3у2 + у3 и должна составлять не менее 15 единиц, т. е.

3у1 + 3у2 + у3 15.

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

7у1 + у2 + 6у3 10.

По экономическому смыслу цены неотрицательные: y1, y2, y3 0. Получили симметричную пару взаимодвойственных задач.

F = 15x1			+ 10x2 max,			Z = 29у1 + 18у2 + 23у3 min,
3x		7x			29,	3y		3y		y		15,
	1			2			1	y2	2		3
	3x1 x2				18,	7y1			6y3			10,
x		6x	2		23,	y1, y2, y3 0.
	1
	x1, x2		0;

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

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

Fmax = 99,17, тогда Zmin = 99,17.

Установим соответствие между переменными исходной и двойственной задачи:

x1	x2	x3	x4	x5
y4	y5	y1	y2	y3

27

В результате решения данной задачи симплексным методом получено следующее решение (0,83; 4,17; 0; 0; 0), которое записываем из строки F таблицы оптимального решения..

Компоненты у1, у2, у3 оптимального решения двойственной задачи оценивают добавочные переменные х3, х4, х5 прямой задачи.

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

Экономический смысл этого обстоятельства состоит в том, что ресурса Оборудования в задаче имеется с излишком и этим ресурсом не особенно дорожат, поэтому устанавливают для него нулевую оценку. А ресурсы Электроэнергия и Сырье являются дефицитным (целиком расходуются), поэтому эти виды оценивают некоторыми положительными оценками (у1 = 0,83, у2 = 4,17).

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

Ценность того или иного вида ресурса будет определяться величиной роста максимального дохода при увеличении, например запаса

Электроэнергии или Сырья.

Согласно выводу из теоремы об оценках Fmax = yi bi.

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

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

Fmax = y3 b3 = 0 1 = 0,

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

Увеличим на 1 единицу запас Электроэнергии. Тогда

Fmax = y1 b1 = 0,83 1 = 0,83.

28

Увеличив на одну единицу запас ресурса Сырье, получим

Fmax = y2 b2 = 4,17 1 = 4,17.

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

			Таблица 2
	Объективно	Затраты ресурсов на единицу
Ресурс	обусловленные	продукции
	оценки ресурсов	Продукт С	Продукт D
Электроэнергия	0,83	6	4
Сырье	4,17	3	2
Оборудование	0	3	4
Цена единицу продукции		15	14

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

m

включен лишь тот вариант, для которого величина aij yi ,

i 1

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

m

j aij yi cj , i 1

при этом если, j 0, то вариант выгоден; если. j > 0, то невыгоден. Для продукта С:

С = 0,83 ∙ 6 + 4,17 ∙ 3 + 0 ∙ 3 – 15 = 17,49 – 15 = 2,49

Поскольку С = 2,49 > 0, то делаем вывод, что продукт С невыгодно включать в план, так как затраты на его изготовление не покрываются получаемой прибылью.

Аналогично оценим прибыль продукта D:

D = 0,83 ∙ 4 + 4.17 ∙ 2 + 0 ∙ 4 – 14 = 11,66 – 14 = 2,34.

Поскольку D = 2,34 > 0, то делаем вывод, что продукт D невыгодно включать в план, так как затраты на его изготовление покрываются получаемой прибылью.

29

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

вMicrosoft Excel

Для решения рассматриваемой задачи с помощью программы MS Excel необходимо выполнить следующие действия.

1. Осуществляем ввод данных в таблицу Excel согласно схеме, представленной на рис. 6.

Рис. 6. Заполнение схемы для решения задачи

Для переменных задачи x1 и x2 отведены ячейки B3 и C3. Эти ячейки называются рабочими или изменяемыми ячейками. В изменяемые ячейки значения не заносятся, в результате решения задачи в этих ячейках будет отражено оптимальное значение переменной.

В ячейку D4 необходимо ввести формулу для вычисления целевой функции задачи (дохода) F = 15x1 + 10x2. Формула в алфавите языка

Excel имеет вид: =B4*B3+C4*C3.

Израсходованное количество ресурса Электроэнергия составляет 3x1 + 7x2. В ячейку D7 (расход электроэнергии) вводится формула

=B7*$B$3+C7*$C$3.

Аналогично вводятся формулы расхода остальных ресурсов, а именно Сырья и Оборудования. В ячейку D8 (расход сырья) вводится формула =B8*$B$3+C8*$C$3. В ячейку D9 (расход оборудования) вводится

формула =B9*$B$3+C9*$C$3.

В результате страница примет вид:

Рис. 7. Вид страницы с добавленными формулами

30

2. В меню Сервис выбираем процедуру Поиск решения. В появившемся окне (рис. 8) нужно установить адрес целевой ячейки D4, значение целевой ячейки, равное максимальному значению, адреса изменяемых ячеек B3:C3.

Рис. 8. Окно средства Поиск решения

3. Чтобы ввести ограничения задачи, нажать кнопку Добавить. В появившемся диалоговом окне слева ввести адрес D7 (израсходованное количество Электроэнергии), затем выбрать знак ≤ и в правой части количество этого ресурса, равное 29 (или адрес ячейки E7). После ввода нажать кнопку Добавить и аналогично ввести второе и третье ограничения, а также условие положительности изменяемых ячеек.

Рис. 9. Добавление ограничения

4.После ввода ограничений получим следующий вид окна Поиск

решения (рис. 10).

5.Затем в окне Поиск решения необходимо нажать кнопку Параметры и

впоявившемся окне (рис. 11) установить флажок в пункте Линейная модель. В этом случае при решении задачи будет использоваться симплекс-метод. Остальные значения можно оставить без изменения. После нажать кнопку ОК.

6.Для решения задачи в окне Поиск решения нажать кнопку Выполнить. Если решение найдено, появляется окно (рис. 12).