Posobie1

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

4. Пусть столбец, который может стать разрешающим, имеет номер j, то есть c j 0. Это означает, как уже говорилось выше, можно уменьшить

значение целевой функции путем увеличения значения xj, оставляя все другие свободные переменные без изменений, то есть равными нулю. В системе (4), на основе которой построена симплекс-таблица 4, имеем:

x1 b10 b1 j x j 0,x2 b20 b2 j x j 0,

.............................

xk bk 0 bkj x j 0.

Ясно, что увеличивая xj, надо следить за тем, чтобы x1, x2,…, xk оставались неотрицательными. Здесь возможны два случая:

а) Все коэффициенты bij < 0, i = 1,…, k. Тогда значение xj можно увеличивать неограниченно, от этого произведения –bijxj будет только расти, и все переменные x1, x2,…, xk будут неограниченно возрастать, то есть требование их неотрицательности не будет нарушено. Целевая функция

при этом				(X) = c0 c j ( x j ),					c j 0, не будет ограничена снизу:
			L
	L( X ) .

б) Среди bij , i = 1,…, k имеются положительные, и таких чисел может быть несколько. Пусть brj > 0 r = 1 или r = 2, или …, или r = k. Ясно, чтобы выполнялось условие xr = br0 – brjxj ≥ 0, надо потребовать выполнения

равносильного неравенства x j bro , то есть переменную xj можно увели-

brj

чивать, но только до величины bro . И такие неравенства должны выпол-

brj

нятся для всех строк j-го столбца, в которых brj > 0. Следовательно, надо для таких строк определить величину

61

K min	br 0	,	1 r k,	b 0.
	brj			rj

Ясно, что xj можно увеличивать, но не более чем до K. Значит, xj надо менять местами с той базисной переменной, в которой строке указанный минимум достигается.

Итак, последовательность действий в пункте 4 такова: просматривается столбец, соответствующий c j 0, выясняется, имеются ли в нем по-

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

5. В разрешающем столбце j находится строка с номером i, для кото-

рой достигается min	br 0	, 1 r k,	b 0.	Строка i — разрешающая
	brj		rj

строка. Перейти к пункту 6.

6. Меняются местами переменные xj и xi. Для этого в последней сим- плекс-таблице надо выполнить жордановы исключения по соответствующему алгоритму. Вернуться к пункту 3.

Продемонстрируем на примерах применение рассмотренного алгоритма симплекс-метода.

Пример 1. Рассмотрим задачу 4 из п. 6 § 2. Имеем общую задачу:

3x1 4x2 322,x2 70,

2x1 180,

0,5x1 2x2 100,x j 0, j 1, 2,

L( X ) 60x1 100x2 max .

1.Путем введения новых неотрицательных переменных приведем ее

кканоническому виду:

62

3x1 4x2 x3

322,

x4

70,

x2

2x1 x5 180,

0,5x 2x

2

x 100,

1

6

x

j

0, j 1,...,6,

L( X ) 60x1 100x2 min .

2. Определим ранг

матрицы

коэффициентов

системы

уравнений.

В нашем случае ясно, что он равен 4, так как коэффициенты при новых

Таблица 9

переменных

образуют

еди-

ничную

подматрицу.

Еще

Свободные

более очевидно, что перемен-

bi0

x1

x2

ные x3,

x4,

x5,

x6

могут одно-

Базисные

временно

быть

выражены

x3

322

3

4

через x1

и x2. Таким образом,

x4

70

0

1

x3, x4, x5, x6

являются базисны-

ми переменными, а x1

и x2 —

свободными. В этом случае

x5

180

2

0

система (4) имеет вид:

x3

322 3x1

4x2 ,

x6

100

0,5

2

70

x2 ,

x4

180 2x1,

L( X )

0

60

100

x5

x

100 0,5x 2x

.

6

1

2

Составим

для

полученной

Таблица 10

системы и целевой функции

Свободные

симплекс-таблицу (таблица 9).

Базисные

bi0

x1

x2

X = (0; 0; 322; 70; 180; 100) —

опорный план, с которого мы

x3

322

3

4

начинаем движение в сторону

–200

–1

–2

уменьшения значения

L( X ) .

x4

70

0

1

–50

–0,25

–0,5

Для него

L( X ) = 0.

Значения

x5

180

2

0

x3, x4, x5, x6 считываются из

0

0

0

столбца

свободных

членов

x6

100

0,5

2

bi0, так как именно эти значе-

50

0,25

0,5

ния получаются, если сво-

L( X )

0

60

100

бодные

переменные

равны

нулю.

–5000

–25

–50

63

3. Видим, что	в последней строке есть положительные элементы
в столбцах при x1	и x2. Значит, любой из этих столбцов в дальнейшем мо-
жет стать разрешающим.

4. Рассмотрим столбец x2. В нем есть положительные коэффициенты

в строках при x3, x4							и x6.
5. Находим, в какой из этих строк достигается								min	br 0	. Видим, что
									brj
322			70		100		50, и достигается в строке при x6. Значит, эта строка
min		,		,
4			1		2

будет разрешающей.

6. Отметим в таблице разрешающую строку, разрешающий столбец,

разрешающий

элемент

Таблица 11

и выполним один шаг жор-

Свободные

дановых исключений, то есть

bi0

x1

x6

переведем

переменную

x2

Базисные

в базисные, а x6

— в сво-

x3

122

2

–2

бодные.

Преобразования

61

0,5

–1

исходной таблицы отраже-

x4

20

–0,25

–0,5

ны в таблице 10, а новая

15,25

0,125

–0,25

симплекс-таблица представ-

лена в верхних треугольни-

x5

180

2

0

–122

–1

2

ках таблицы 11. В дальней-

шем для экономии места в

x2

50

0,25

0,5

случае, если новая таблица

–15,25

–0,125

0,25

снова подвергается преобра-

–5 000

35

–50

L( X )

зованиям, будем

в ней

за-

–17,5

35

–2 135

полнять

нижние

треуголь-

ники,

что

соответствует

следующим

жордановым

исключениям. Так сделано в таблице 11,

судя по

которой

значение

L( X ) от 0 в начале процесса вычислений уменьшилось до –5 000. Это

значение целевой функции на опорном плане X = (0; 50; 122; 20; 180; 0). Значения x3, x4, x5, x2 считываются из столбца свободных членов bi0. Вернемся к пункту 3 алгоритма симплекс-метода.

1.Видим, что в последней строке таблицы 11 (рассматриваем только верхние треугольники) положительный элемент только один — в столбце x1.

2.Этот столбец — разрешающий, так как в нем в строках при x3, x5

иx2 находятся положительные коэффициенты.

64

Таблица 12

3.

Находим,

в

какой

из

этих

строк

достигается

Свободные

br 0

bi0

x3

x6

min

.

Видим,

что

Базисные

brj

x1

61

0,5

–1

122

180

50

,

,

min

61,

x4

35,25

0,125

–0,75

2

2

0,25

и достигается в строке при x3.

x5

58

–1

2

Значит, эта строка будет раз-

решающей.

x2

34,75

–0,125

0,75

4. Отметим в таблице 11

разрешающую строку, разре-

L( X )

–7135

–17,5

–15

шающий столбец, разрешаю-

щий

элемент

и

выполним

один шаг жордановых ис-

ключений, то есть переведем

переменную

x1

в

базисные,

а x3 — в свободные. Преобразования исходной таблицы отражены в ниж-

них треугольниках таблицы 11, а новая симплекс-таблица представлена

в верхних треугольниках таблицы 12. По таблице 12 находим, что значе-

ние L( X ) от –5 000 на предыдущем шаге симплекс-метода уменьшилось

до –7 135. Это — значение целевой функции на опорном плане X = (61; 34,75; 0; 35,25; 58; 0). Значения x1, x4, x5, x2 считываются из столбца свободных членов bi0. Вернемся к пункту 3 алгоритма симплекс-метода.

3. Видим, что в последней строке таблицы 12 положительных элементов нет. Это означает, что найденное опорное решение является оптимальным: X*= (61; 34,75; 0; 35,25; 58; 0). Наименьшее значение

L( X * ) равно –7 135. Интерпретируем полученные результаты:

x1* 61 — оптимальный выпуск задвижек в день составляет 61 штуку;

x2* 34,75 — оптимальный выпуск тисков в день составляет 34,75 штук;

x3* 0 — сталь-45 при таком выпуске расходуется полностью; x4* 35,25 — остаток чугуна (кг) на складе за 1 день;

x5* 58 — остаток бронзы (кг) на складе за 1 день;

x6* 0 — сталь-3 при таком выпуске расходуется полностью;

max L(X ) min L(X ) 7 135 — наибольшая выручка (руб.) за день за выпущенную продукцию.

65

Получили то же решение, что и в § 2.

Если выпускать 34,75 тисков в день нельзя, то этот результат можно интерпретировать так: оптимальным является выпуск 34,75 · 4 = 139 штук тисков за 4 дня. Остальные цифры также должны быть соответственно пересчитаны. Можно поступить и по-другому: оптимальным считать выпуск 34 тисков в день. Но в этом случае необходимо пересчитать выручку, остаток стали-45, чугуна и стали-3.

Заметим, что выбирая разрешающий столбец в таблице 1 (пункт 4), можно было бы остановиться и на столбце переменной x1: в последней строке этого столбца и в других строках есть положительные элементы. В этом случае решение пошло бы по другому пути. Убедитесь в этом самостоятельно. Порядок жордановых исключений в этом случае таков: x1 меняем с x5, x2 меняем с x3, x5 меняем с x6. Значения целевой функции при этом будут уменьшаться так: 0, –5 400, –6 700, –7 135.

Пример 2. Рассмотрим конкретную экономическую ситуацию. На АООТ «Балтекс» для выпуска глянцевой ткани, ткани «Турист» и курточной ткани используются ткацкие станки двух типов: станки гидравлические и станки ткацкие бесчелночные (коротко: СГ и СТБ) с различной производительностью. Для изготовления указанных видов ткани используются нити и красители. Ресурсы времени работы станков, нитей и красителей ограничены. В таблице 13 указаны ежемесячные ресурсы времени работы станков в тысячах станко-часов, нитей и красителей в килограммах, производительность станков в метрах на час, нормы расхода нитей и красителей в килограммах на тысячу метров каждого вида ткани и цена 1 м ткани. Требуется организовать выпуск продукции так, чтобы ежемесячная выручка предприятия была максимальной.

						Таблица 13
Виды			Виды ткани			Ежемесячный
ресурсов	Глянцевая		«Турист»		Курточная	объем ресурсов
	Производительность станков
СГ	0 м/ч		45,5 м/ч		29 м/ч	4,6 тыс. ст.-ч
СТБ	23,5 м/ч		0 м/ч		0 м/ч	4,5 тыс. ст.-ч
			Нормы расхода
Нити	417,7 кг/тыс. м		221,9 кг/тыс. м	112,24 кг/тыс. м		2 485,7 кг
Красители	1 192,5 кг/тыс. м		675,0 кг/тыс. м		270,0 кг/тыс. м	9 738,5 кг
		Цена за 1 м ткани
	54,3 руб.		50,2 руб.		27,0 руб.

Составим математическую модель задачи. Пусть x1, x2 и x3 — количество в тыс. м глянцевой ткани, ткани «Турист» и курточной ткани соответственно, выпускаемой ежемесячно. На выпуск x1 тыс. м глянцевой ткани на

66

СТБ с производительностью 23,5 м/ч будет потрачено	x1	тыс. ст.-ч, на
	23,5

выпуск x2 тыс. м ткани «Турист» на СГ с производительностью 45,5 м/ч —

	x2	тыс. ст.-ч, на выпуск x3 тыс. м курточной ткани на СГ с производи-
45,5
тельностью 29 м/ч —							x3				тыс. ст.-ч. Другие соотношения достаточно
					29
очевидны. Получим:
		x2							x3		4,6,
			45,5					29
				x1
									4,5,
			23,5
												112,24x3 2 485,7,
		417,7x1 221,9x2
		1192,5x1 675x2 270x3 9 738,5,
		x 0,							x	2	0, x	0,
			1								3

L( X ) 54,3x1 50,2x2 27,0x3 max .

Перейдем к КЗЛП, оставив для корректного выполнения алгоритма в дробях 4 знака после запятой:

0,0220x2 0,0345x3 x4 4,6,0,0426x1 x5 4,5,

417,7x1 221,9x2 112,24x3 x6 2 485,7,1192,5x1 675x2 270x3 x7 9 738,5,

x 0, i 1,..., 7,

i

L( X ) 54,3x1 50,2x2 27,0x3 min .

Ясно, что базис в системе линейных уравнений образуют новые переменные x4, x5, x6, x7. Не проводя подробные рассуждения, как в предыдущем примере, укажем только симлекс-таблицы (таблицы 14—16), отражающие решение. Все величины будем сохранять с 4 знаками после запятой. Здесь в таблице 14, в отличие от предыдущего примера, совмещены исходная и преобразованная по алгоритму жордановых исключений таблица.

67

				Таблица 14
	bi0	x1	x2	x3
	4,6	0	0,0220	0,0345
x4	–0,2486	–0,0418	–0,0001	–0,0112
	4,5	0,0426	0	0
x5	0	0	0	0
	2485,7	417,7	221,9	112,24
x6	11,2019	1,8824	0,0045	0,5058
	9738,5	1192,5	675	270
x7	–7561,2508	–1270,6016	–3,0419	–341,4229
	0	54,3	50,2	27,0
L	–562,2653	–94,4837	–0,2262	–25,3887
				Таблица 15
	bi0	x1	x6	x3
	4,3514	–0,0418	–0,0001	0,0233
x4	–0,5164	–0,0868	–0,0002	–0,0461
	4,5	0,0426	0	0
x5	0	0	0	0
	11,2019	1,8824	0,0045	0,5058
x2	22,1469	3,7216	0,0089	1,9771
	2177,2492	–78,1016	–3,0419	–71,4229
x7	1581,7957	265,8096	0,6354	141,2078
	–562,2653	–40,1837	–0,2262	1,6113
L	–35,6848	–5,9966	–0,0143	–3,1856
				Таблица 16
	bi0	x1	x6	x2
	3,8350	–0,1286	–0,0003	–0,0461
x4
	4,5	0,0426	0	0
x5
	22,1469	3,7216	0,0089	1,9771
x3
	3759,0449	187,7080	–2,4065	141,2078
x7
L	–597,9501	–46,1803	–0,2405	–3,1856
		68

Дадим интерпретацию полученным результатам:

x1* 0 — для получения наибольшей выручки глянцевую ткань выпускать не надо;

x2* 0 — для получения наибольшей выручки ткань «Турист» выпускать не надо;

x3* 22,1469 — для получения наибольшей выручки курточную ткань надо выпускать в объеме 22,1469 тыс. м ежемесячно;

x4* 3,8350 — остаток в тыс. станко-часов рабочего времени СГ;

x5* 4,5 — СТГ не использовались (глянцевая ткань не выпускалась); x6* 0 — нити израсходованы полностью;

x7* 3759,0449 — остаток в кг красителей;

max L(X ) min L(X ) 597,9501 — наибольшая ежемесячная выручка в тыс. руб. за выпущенную продукцию.

4. Реализация алгоритма симплекс-метода на языке паскаль

Эта часть параграфа, посвященного симплекс-методу, будет полезна тем, кто хочет реализовать его на каком-либо языке программирования. Такая реализация существенно отличается от алгоритма, предложенного выше. Дело в том, что выбор базисных переменных — трудоемкая процедура, требующая в связи с возникающей вычислительной погрешностью весьма тонкого анализа получающихся результатов. Гораздо проще ввести искусственный базис — новые по отношению к КЗЛП переменные, количество которых равно количеству строк и которые заведомо образуют базис. Для простоты рассуждений будем полагать, что в КЗЛП, полученной из ОЗЛП, количество уравнений равно m, а количество пременных (старых и новых вместе) — n. Потребуем, чтобы правые части уравнений системы (1) в КЗЛП были неотрицательными: bi ≥ 0, i = 1, 2,…, m. Если в каком-либо уравнении это не так, то умножим обе части его на (–1). Ясно, что такое преобразование никоим образом не изменит решение. Добавим к левой части каждого уравнения системы в КЗЛП еще одну неотрицательную переменную: xn+1, xn+2,…, xn+m. Будем называть их искусственными. Система (1) примет вид:

69