Материал: kozinova_at_osharina_nn_matematika_lineinaia_algebra_analiti

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

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

YT y		y 0 − превышение дохода продавца ресурсов над прибылью
1 2	4	5
1 2

предприятия на каждую единицу продукции.

Ограничения задачи могут быть представлены с помощью дополнительных неизвестных в виде линейных уравнений:

AT Y E YдT CT		3y		2 y		y		4
AT Y E YдT CT			1		2		4
2 3 3 1 2 2 2 1	2 1		12 y1 2 y2 2 y3 y5 6

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

6.4.Симплексный метод решения задачи линейного программирования

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

Первая задача: Вторая задача:

	A X	B	T	Y	C	T
			A	Y	C
m n n 1		m 1	n m m 1		n 1
	X 0		Y	0
n 1			m 1

Особое место среди допустимых планов занимают базисные, которые находят как допустимые базисные решения систем линейных уравнений, представляющих ограничения задачи линейного программирования в канонической форме:

Первая задача: Вторая задача:

A X E X д B	AT Y E Y CT
m n n 1 m m m 1 m 1	д
m n n 1 m m m 1 m 1	n m m 1 n n n 1	n 1

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

поиск допустимого базисного плана,

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

101

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

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

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

X T x		x	x	x	x ? – план
X T x		x	x	x	x ? – план
1 5	1	2	3	4	5
1 5
F C X 4x1 6x2				max – прибыль (функция цели)
1 2	2 1

3x1 12x2
	2x1	2x2

		2x2

X T x1

1 5

7 x3

– ограничения на ресурсы

x4 x5 0 – естественные ограничения

Симплексный метод решения данной задачи представлен с помощью симплекс-таблицы 1. Он состоит только из второго этапа, поскольку на первом шаге легко определяется допустимый базисный план:

X T 0 0		60 22 7
X T 0 0		60 22 7
1 5

Обозначения, применяемые в описании симплексного метода и в таблице: cio – коэффициенты при основных переменных в формуле функции цели экономико-математической модели задачи;

xo – основные переменные рассматриваемого базисного плана, в порядке их следования в уравнениях системы ограничений задачи;

aij , i 1,3, j 1,5 – коэффициенты при переменных x j в системе ограничений

задачи;

bi – правые части системы ограничений задачи;

	bi	– числа, получающиеся в результате деления правых частей системы
	aik
	aik

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

F j − оценочные числа, а именно, коэффициенты (с противоположным знаком) при переменных в формуле функции цели, полученной в результате

102

исключения основных переменных анализируемого базисного плана (для

расчета используется формула Fj cio aij c j ); i

Fb − значение функции цели для анализируемого базисного плана,

рассчитывается по формуле							Fb cio bi			и приводится в оценочной строке, в
								i
столбце правых частей системы ограничений;
X T − базисный план, анализируемый на данном шаге.
																		Таблица 1

	co	c j			4	6	0		0	0			bi	, aik 0
											bi		bi
					x	x	x		x	x	bi
	i	x	o		x	x	x		x	x			aik
		x			1	2	3		4	5
	0	x3			3	12	1		0	0	60	60/3
	0	x4			(2)	2	0		1	0	22	22/2 – min
	0	x5			0	2	0		0	1	7	–
	оценочная	F		j	(-4)	-6	0		0	0	0		T		0	60			22	7
	оценочная

	строка												X I 0
	строка												X I 0
	0	x3			0	(9)	1		-1,5	0	27	27/9 – min
	4	x1			1	1	0		0,5	0	11	11/1
	0	x5			0	2	0		0	1	7	7/2
	оценочная	F		j	0	(-2)	0		2	0	44		T		0		27		0	7
	оценочная

	строка												X II 11
	строка												X II 11
	6	x2			0	1	1/9		-1/6	0	3
	4	x1			1	0	-1/9		2/3	0	8
	0	x5			0	0	-2/9		1/3	1	1
	оценочная	F		j	0	0	2/9		5/3	0	50			T	3			0	0	1
	оценочная

	строка												X III 8
	строка												X III 8

На каждом шаге второго этапа симплексного метода для анализа допустимого базисного плана используется критерий оптимальности:

отсутствие отрицательных оценочных чисел при максимизации функции цели;

отсутствие положительных оценочных чисел при минимизации функции цели.

103

Переход к новому допустимому базисному плану на втором этапе симплексного метода.

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

соответствующего	числа в оценочной строке Fk . Перевод	переменной	xk
может привести	к увеличению значения функции цели,	если Fk 0	и

уменьшению, если Fk 0 .

Выбирается основная переменная для перевода в неосновные так, чтобы

новый базисный план был допустимым. Искомая основная переменная указана
во втором столбце xo				и находится в строке таблицы, которой соответствует
минимальным число:
	bi			0
	bi	, i 1, m, a
		, i 1, m, a
			ik
aik

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

Решение предлагаемой задачи F max получено в результате

выполнения трех шагов симплексного метода.

На первом шаге симплексного метода в качестве основных переменных

выбираем дополнительные, а именно, остатки ресурсов	X T	x	x	x . При
	д	3	4	5
	1 3

анализе соответствующего допустимого базисного плана в оценочной строке
появляются отрицательные числа F1 4, F2 6 ,					следовательно, этот план
X T 0 0		22	7 не является оптимальным.
	60
I
На втором шаге симплексного метода определим новую группу основных
переменных.	Переведем неосновную			переменную	x1 в группу основных
переменных,	т.к.	это может F1 4		привести к увеличению функции цели.
Основную переменную			x4 , находящуюся во втором уравнении, переведем в

неосновные, т.к. во второй строке таблицы находится минимальное число:

min

, i 1, m, a

a21

ai1

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

уравнение (второе), причем с коэффициентом				− единица. В	результате,
получим базисный план	X T	11 0		7 с большим	значением
получим базисный план	X T	11 0	27 0	7 с большим	значением
	II
		104

функции цели F Fb 44 . Этот план не может быть назван оптимальным, поскольку в оценочной строке есть отрицательное число F2 2 .

На третьем шаге симплексного метода выполним аналогичные действия:

выберем новую группу основных переменных x2 , x1, x5 ;

выполним преобразования системы ограничений;

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

Третий анализируемый базисный план	X T	8 3	0 0 1 является

	III
оптимальным F Fb 50 , так как оценочная строка этого базисного плана

уже не содержит отрицательных оценочных чисел.

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

	8			оптимальный план выпуска продукции,
X o		(ед.) –		оптимальный план выпуска продукции,

	3
	0

X дo	0		(ед.) –	остатки ресурсов,
	1
	1

F o max F 50 (д. е.) – максимальная прибыль.

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

Пример 3. Используя результаты, полученные в примере 2, и теоремы двойственности найдем решение двойственной задачи, а именно, оптимальные цены ресурсов.

Y T y		y	y		y	y ?		− план

1 5	1	2	3	4		5

Z 60 y1 22 y2 7 y3 min − функция цели
3y1 2 y2					y4	4	− ограничения
	2 y2 2 y3				y5 6
12 y1
YT y		y	y		y	y 0		– естественные ограничения

1 5	1	2	3		4	5

Согласно теореме 1 взаимно-двойственные задачи линейного программирования, одновременно имеют решения, причем:

max F min Z 50 .

Согласно теореме 2:

105

Источник: https://studfile.net/preview/15912971/

Смотрите также:

2418
3033
3499
A решение проблемы
Vse_testy_PVB
Анализ бизнес-планирования
Аттестация: понятие, назначение, порядок проведения
Влияние факторов среды на гаметогенез нерки р. Озерная (Западная Камчатка)
Всемирная история. от Нового времени до конца XX века. Гурина Е.М
Древнегреческий театр