korobov

91

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

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

Геометрический смысл системы линейных неравенств, с тремя переменными

Пусть дана система линейных неравенств:

a x + a x

+ a x

≤ b ;

11

1

12

2

13

3

1

a21x1 + a22 x2 + a23 x3 ≤ b2

;

(2.2.103)

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

a

x + a

m2

x

2

+ a

m3

x

3

≤ b .

m1 1

m

с тремя независимыми переменными х1, х2, х3.

Будем

представлять

переменные х1, х2, х3 как координаты точки Р в

прямоугольной системе

координат в пространстве. Спрашивается, какую область в

пространстве образует совокупность точек Р (х1, х2, х3), координаты которых удовлетворяют всем неравенствам (2.2.103).

Сначала решим этот вопрос для одного неравенства
a1 x1	+ a2 x2	+ a3 x3 ≤ b.	(2.2.104)
Рассмотрим плоскость, определяемую уравнением
a1 x1	+ a2 x2	+ a3 x3 = b.	(2.2.105)

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

Система неравенств (2.2.103) определяет общую часть (пересечение) т полупространств, каждое из которых определяется одним из неравенств системы.

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

Область (полупространство), определяемая одним неравенством (2.2.104), очевидно, является выпуклой. Покажем, что область, определяемая системой неравенств (2.2.103), также является выпуклой. Пусть Р1( x1' , x2' , x3' ) и P2( x1'' , x2'' , x3'' ) — две

произвольные точки области М. Из аналитической геометрии в пространстве известно, что

92

координаты любой точки Р (х1, х2, х3), лежащей на отрезке P1P2, могут быть определены через координаты концов отрезка по формулам:

x = (1− λ)x'		+ λ x	'' ;
1	1	1
x2	= (1− λ)x2'	+ λ x2'' ;		(2.2.106)
x3	= (1− λ)x3' + λ x3'' ,
где параметр λ удовлетворяет условию 0 ≤λ≤1.
Координатные равенства (2.2.106) можно записать в				виде одного векторного
равенства
Х=(1-λ)Х' + λХ",			0≤λ≤ 1,	(2.2.107)

где X', X" , X — радиусы-векторы точек Р1, Р2, Р. Каждому значению параметра λ в интервале (0, 1) соответствует одна и только одна точка отрезка Р1Р2.

При изменении параметра от 0 до 1 точка Р пробегает весь отрезок Р1Р2, от точки Р1 до точки Р2. В дальнейшем радиусы-векторы

X = [x1 , x2 , x3 ], X '= [x1' , x2' , x3' ], X ''= [x1'' , x2'' , x3'' ]

будем рассматривать как точки пространства, координаты которых совпадают с компонентами векторов.

Точка X, определяемая соотношением (2.2.107), называется выпуклой комбинацией точек Х1 и Х2. Систему неравенств (2.2.103) можно записать в следующем векторном виде:

Ai X	1	≤ b , i = 1,2,...,m,									(2.2.108)
			1
где Аi = (ai1, аi2, ai3) — строки матрицы системы неравенств (2.2.103): А=									ij		.
								a
											m×3
Пусть точки Х1 и Х2 принадлежат области М, определяемой системой неравенств
(2.2.108), тогда
AiX1≤bi			i= 1, 2,..., т;								(2.2.109)
AiX2≤bi			i= 1, 2,..., m.								(2.2.110)
Умножая неравенства (2.2.109) и (2.2.110) соответственно на неотрицательные
числа 1 - λ и			λ и затем почленно их складывая, получим
Ai [(1− λ)X				1	+ λX	2	]≤ b .
							i
или, учитывая равенство (2.2.107),
АiХ≤bi.											(2.2.111)

Таким образом, точка X, являющаяся выпуклой комбинацией точек X1 и Х2, принадлежащих области М, также принадлежит области М. Отсюда следует, что область, определяемая системой неравенств (2.2.103), является выпуклой. Если все точки области М находятся на конечном расстоянии от начала координат, то область М представляет собой выпуклый многогранник. Область М может быть в некоторых направлениях неограниченной, тогда она называется выпуклой многогранной областью. Возможен случай, когда не существует ни одной точки, координаты которой удовлетворяли бы всем неравенствам (2.2.103) (система противоречива), тогда говорят, что область М пуста.

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

Геометрический смысл системы линейных неравенств с п переменными

Сначала приведем некоторые определения из геометрии n-мерного пространства, n- мерный вектор Х = [х1, х2, . . ., xn] будем понимать как точку в n-мерном пространстве.

93

Расстояние X − Y между двумя точками Х = [х1, х2,...,хn] и Y=[y1, y2,…,yп] определяется следующим образом:

	n				1/ 2
X − 0	= ∑(xj	− y j	)2		.	(2.2.112)
	j=1

Это определение расстояния является обобщением определения расстояния в двух и трехмерном пространствах.

Длиной, или абсолютной величиной Х , вектора Х=(х1, х2, . . .,хп) называется расстояние от начала координат, определяемого нулевым вектором 0=(0, 0, .... 0), до точки X:

			n	2j	1/ 2
X	=	X − 0	= ∑x		.	(2.2.113)
			j=1

Совокупность всех n-мерных векторов Х = [х1, х2,...,хn] вместе с расстоянием, определенным выражением (2.2.112), называется п-мерным евклидовым пространством и обозначается символом Еп .

В обычном трехмерном пространстве прямая может быть задана с помощью векторного уравнения

Х=А + λВ,

(2.2.114)

где А и В — радиусы-векторы, разность которых А — В определяет направление прямой.

Точка X пробегает всю прямую при изменении параметра λ от -∞ до +∞.

По аналогии с этим под «прямой» в n-мерном пространстве понимается совокупность точек Х = [х1, х2,...,хn], удовлетворяющих векторному уравнению вида (2.2.114), где А и В — заданные n-мерные векторы.

Векторное уравнение (2.2.114) можно преобразовать следующим образом:

Х=(А-λА) + (λА + λВ) = (1-λ)А + λ (А+В).	(2.2.115)
Точку А обозначим через Х1, а точку А + В через Х2. Тогда уравнение прямой
(2.2.115) будет иметь следующий вид:
X=(1-λ)Xl + λX2.	(2.2.116)
Если ограничить пределы изменения	параметра неравенствами 0≤λ≤1, то

множество точек (2.2.116) называется отрезком, соединяющим точки Х1 и Х2. Точка X отрезка X1X2, определяемая равенством (2.2.116) при 0≤λ≤1, так же как и в трехмерном случае, называется выпуклой комбинацией точек Х1 и Х2. Точки Х1 и Х2, отвечающие значениям λ = 0 и λ= 1, называются концами отрезка. Точки X, отвечающие значению параметра, удовлетворяющему строгим неравенствам 0≤λ≤1, называются внутренними точками отрезка.

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

a1 x1 + a2 x2 + a3 x3 = b,

является так называемая гиперплоскость в n-мерном пространстве.

Гиперплоскость в n-мерном пространстве определяется как множество Х = [х1, х2,...,хn], координаты которых удовлетворяют уравнению первой степени

a1x2 + a2x2+ ... +anxn = b.	(2.2.117)
Вектор коэффициентов А=(а1, а2,..., ап)	уравнения гиперплоскости (2.2.117)
называется нормалью к гиперплоскости.
Уравнение гиперплоскости (2.2.117) можно записать в виде
АХ=b.	(2.2.118)
Гиперплоскость (2.2.118) разбивает все пространство Еп на два полупространства, и
для одного из них
АХ≤b.	(2.2.119)

94

Неравенство (2.2.119) определяет так называемое замкнутое полупространство, границей которого является гиперплоскость (2.2.118).

Множество точек в n-мерном пространстве называется выпуклым, если оно содержит любую выпуклую комбинацию X= (1 -λ) Х1 + λХ2, 0≤λ≤1 любой пары точек Х1 и Х2 из этого множества. Таким образом, выпуклое множество содержит отрезок, соединяющий любые две точки из этого множества.

Замкнутое n-мерное полупространство, также как и обычное трехмерное полупространство, является выпуклым. Действительно, пусть Х1 и Х2 — две произвольные точки полупространства, определяемого неравенством (2.2.119), тогда

AX1≤b, AX2≤b.

Умножим первое неравенство на неотрицательное число 1 -λ и второе на λ (0≤λ≤1) и затем полученные неравенства почленно сложим, в результате получим

A[(1− λ)X1 + λ X 2 ]≤ b.

Это означает, что выпуклая комбинация Х=(1 -λ)Х1 +λХ2, 0≤λ≤ 1 принадлежит тому же полупространству. Это и доказывает его выпуклость.

Пусть дана система m линейных неравенств с п неизвестными:

a x + a x

+ ...+ a

x

≤ b ;

11 1 12

2

1n

n

1

a21x1 + a22 x2 + ...+ a2n xn ≤ b2

;

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

a

x + a

m2

x

2

+ ...+ a

mn

x

n

≤ b

,

m1 1

m

которую можно записать кратко в виде

AiX≤bi,

i=l, 2,..., т,

где Аi = (аi1, ai2, . ..,ain) — строки матрицы системы A =

a

ij

;

m×n

(2.2.120)

(2.2.121) Х=[х1, х2, . . ., хn] —

переменный вектор.

Каждое из этих неравенств (2.2.121) определяет некоторое замкнутое полупространство пространства En, а все неравенства совместно — некоторую область в n-мерном пространстве. Точно так же, как в предыдущем параграфе, для трехмерного пространства можно доказать, что эта область является выпуклой. Она, по аналогии с трехмерным пространством, называется выпуклым многогранником, если для всех ее точек выполняется неравенство Х <С, где С — положительное число.

Если не существует положительного числа С, при котором бы выполнялось неравенство Х <С, для всех точек области, то область называется выпуклой многогранной областью. Если система (2.2.120) несовместна, то говорят, что определяемая ею область пуста.

Геометрический смысл опорных решений

По аналогии с определением вершины выпуклого многогранника (многогранной области) в трехмерном пространстве определяется понятие вершины в n-мерном пространстве. Вершину выпуклого многогранника (многогранной области) в n-мерном пространстве можно охарактеризовать как точку многогранника, которая не является внутренней точкой никакого отрезка, целиком принадлежащего данному многограннику. Примем следующее определение вершины: точка X, принадлежащая выпуклому многограннику (многогранной области), называется его вершиной, если в этой области не существует двух различных точек Х1 и Х2, для которых точка X являлась бы выпуклой комбинацией Х=(1-λ)Х1+λХ2 при 0<λ<1.

Область, определяемая системой линейных уравнений

x1 ≥ 0, x2 ≥ 0,..., xn ≥ 0, (2.2.123)

определяет выпуклую многогранную область или выпуклый многогранник. Действительно, каждое i-е уравнение в системе (2.2.122) можно заменить равносильной системой, состоящей из двух неравенств:

95

	a x + a x			+ ... + a	x		= b ;
	11 1	12	2	1n		n	1
	a21x1 + a22 x2 + ...+ a2n xn = b2							;	(2.2.122)
	...............................................

am1 x1 + am2 x2 + ...+ amn xn = bm

иусловиями неотрицательности переменных

ai1x1 + ai2 x2 + ...+ ain xn ≥ bi ;

ai1x1 + ai2 x2 + ...+ ain xn ≤ bi .

Таким образом, система т уравнений (2.2.122) и система неравенств (2.2.123) равносильны системе 2т + п линейных неравенств и, следовательно, определяют выпуклую многогранную область или выпуклый многогранник.

Докажем следующую теорему.

Теорема (о соответствии вершин опорным решениям). Опорное решение X

системы уравнений
x1A1 + x2A2 + ... +хпАп = В	(2.2.124)

является одной из вершин области, определяемой системой (2.2.124) и условиями

неотрицательности неизвестных хj≥0, j = 1,			2, . . ., п, и, наоборот, каждая вершина
указанной области есть некоторое опорное решение системы (2.2.124).
Д о к а з а т е л ь с т в о. Предполагаем,			что	ранг	системы (2.2.124) равен числу
m уравнений системы.	Пусть	точка Х0 =	[x0	, x0 ,..., x0 ,0,0,...,0] некоторое опорное
			1	2	k

решение, связанное с независимой группой векторов условий А1, A2, ..., Ak. Тогда имеем тождество

x0 A + x

0

A + ...+ x

0

A

= B.

(2.2.125)

1

1

2

2

k

k

Допустим противное, что точка Х0 не является вершиной выпуклой области М,

определяемой системой

(2.2.124) и условиями неотрицательности неизвестных.

Тогда

существуют

различные

точки

Х1 =

[x'

, x'

,..., x' ] и Х2 =

[x'' , x

'' ,..., x

'' ],

1

2

n

1

2

n

принадлежащие области М, такие, что

X 0 = (1− λ)X1 + λ X 2 ,

0 < λ < 1,

или в координатах:

x0

= (1− λ)x' + λ x

'' ,

j = 1,2,...,n,

0 < λ < 1.

j

j

j

При j>k,

x0 = 0, но тогда и x'

= x''

= 0

при j>k, поскольку λ>0 и 1-λ>0.

j

j

j

Условия принадлежности точек X1 и Х2 области М принимают теперь вид: x1' A1 + x2' A2 + ...+ xk' Ak = B;

x1'' A1 + x2'' A2 + ...+ xk'' Ak = B.

Вычитая почленно из второго равенства первое, получим

(x1'' − x1' )A1 + (x2'' − x2' )A2 + ...+ (xk'' − xk' )Ak = 0.

Здесь по крайней мере один коэффициент x'j' − x'j отличен от нуля, так как точки Х1

и Х2 различны. Отсюда следует, что векторы A1, А2, . . .,Ak линейно зависимы вопреки условию. Полученное противоречие показывает, что опорное решение системы (2.2.124) является вершиной области М.

96

Докажем теперь обратное утверждение теоремы. Пусть точка Х0 = [x10 , x20 ,..., xn0 ]

является вершиной области М. Допустим противное, что точка Х0 не является одним из опорных решений системы (2.2.124). Тогда, изменяя, если это нужно, нумерацию

неизвестных,

можно

считать,

что

первые

k ≤ m положительных координат

[x0

, x0 ,..., x0 ]точки Х0

будут связаны с линейно зависимым набором векторов А1, А2,…, Ak,

1

2

k

и поэтому существуют числа λ1,λ2,…,λk, не все равные нулю, такие, что

λ1 A1 + λ2 A2 + ... + λk Ak = 0.

(2.2.126)

Так как точка Х0 принадлежит области М, то имеем тождество (2.2.125).

Умножая равенство (2.2.126) на произвольное число t и складывая его почленно с

равенством (2.2.125), получим

(x

0

+ tλ )A + (x

0

+ tλ

2

)A

+ ...+ (x0

+ tλ

k

)A = B.

1

1

1

2

2

k

k

Так как числа x0 , x0 ,..., x

0 положительны, то и числа

1

2

k

x0

+ tλ ,

x0 + tλ

2

,..., x0

+ tλ

k

1

1

2

k

при достаточно малом t положительны.

Взяв два таких значения t, отличающихся

друг от друга знаками, t= ε и t= -ε,

получим две точки:

X

1

= [x0

+ ελ ,

x

0

+ ελ

2

,..., x

0

+ ελ

k

,0,0,...,0];

1

1

2

k

X

2

= [x0

− ελ ,

x0

− ελ

2

,..., x0

− ελ

k

,0,0,...,0],

1

1

2

k

принадлежащие области М, для которых точка Х0

является выпуклой комбинацией:

Х0=(1-λ)Х1 + λХ2

при λ = 1/2,

т. е. не является вершиной области М.

Полученное противоречие показывает, что любая вершина области М должна являться одним из опорных решений системы (2.2.124). Теорема полностью доказана.

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

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

z=сx1 + c2x2 + c3x3	(2.2.127)
при условиях:

a

x

+ a

x

+ ...+ a x

≤ b ;

11

1

12

2

13

3

1

a21x1 + a22 x2

+ ...+ a23 x3

≤ b2 ;

(2.2.128)

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

a

x

+ a

m

2

x

2

+ ...+ a

m3

x

3

≤ b

m

,

m1 1

x1

≥ 0, x2

≥ 0,

x3 ≥ 0.

(2.2.129)

Система

неравенств

(2.2.128)—(2.2.129) определяет

в прямоугольной системе

координат 0 х1, х2, х3 некоторый выпуклый многогранник М (рассматривается случай ограниченной области). Неравенства (2.2.129) показывают, что эта область М расположена в первом октанте.

Рассмотрим далее целевую функцию (2.2.127). При каждом фиксированном значении параметра z = a уравнение (2.2.127) определяет в пространстве некоторую плоскость, которая называется плоскостью уровня целевой функции (2.2.127). Совокупность всех плоскостей уровня образует семейство параллельных плоскостей,

97

перпендикулярных к нормальному вектору С=(с1, с2, c3), который указывает направление наиболее интенсивного возрастания целевой функции. В направлении вектора С=(с1, с2, c3) целевая функция (2.2.127) возрастает равномерно. Будем называть плоскость уровня целевой функции допустимой, если она имеет хотя бы одну общую точку с выпуклым многогранником М, определяемым условиями задачи. Выпуклым многогранником М определяется область определения целевой функции. Допустимую плоскость уровня, отвечающую наибольшему значению целевой функции z = zмаx, будем называть опорной плоскостью уровня. Ясно, что вследствие монотонного возрастания целевой функции в направлении нормального вектора С выпуклый многогранник будет всегда расположен по одну сторону от опорной плоскости, а именно — в сторону, противоположную направлению вектора С. Поэтому опорная плоскость может проходить либо через одну из вершин, либо через ребро или грань выпуклого многогранника. В первом случае мы имеем единственное оптимальное решение (вершину), которое является опорным, во втором случае мы имеем бесчисленное множество оптимальных решений (каждая точка ребра или грани — оптимальное решение), среди которых имеется не менее чем два опорных решения (вершины, являющиеся концами ребра, или угловыми точками грани).

Если задача линейного программирования (2.2.127)—(2.2.128) не имеет решения, то это геометрически означает, что область, определяемая условиями задачи (2.2.127) — (2.2.128), либо пуста (система противоречива), либо представляет выпуклую многогранную область, не ограниченную в направлении нормального вектора С=(с1, с2, с3).

Геометрический смысл задачи минимизации аналогичен геометрической интерпретации задачи максимизации, с той лишь разницей, что выпуклый многогранник М располагается по одну сторону от опорной плоскости, вместе с нормальным вектором

С=(с1, с2, с3).

Рассмотрим теперь задачу линейного программирования с п>3 переменными х1, х2,...,хп. Формулировка задачи остается прежней. Требуется найти неотрицательный вектор X = [x1, x2,…, хn], максимизирующий целевую функцию

z = CX	(2.2.130)
при условиях:
AiX = bi, i=1, 2,..., m,	(2.2.131)
где n-мерные векторы С, Аi и числа bi	являются заданными постоянными.

Вэтом случае все построения теряют реальную наглядность, так как они представляются абстрактно в n-мерном пространстве. Однако, по аналогии с трехмерным пространством, геометрическая интерпретация задачи (2.2.130)—(2.2.131) остается той же самой, что и в трехмерном случае. Единственное различие будет состоять в том, что слово «плоскость» заменяется на «гиперплоскость».

В(2.2.3) была доказана важная теорема об опорных решениях: если каноническая

задача линейного программирования имеет оптимальное решение, то существует по

крайней мере одно оптимальное опорное решение.

Учитывая геометрический смысл опорного решения как некоторой вершины выпуклого многогранника М, мы можем утверждение этой теоремы осмыслить следующим образом: если существуют точки области М, в которых целевая функция (2.2.130) достигает своего наибольшего значения z = zмаx, то это zмаx достигается по

крайней мере в одной из вершин области М.

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

98

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

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

99

Глава 3. СИМПЛЕКСНЫЙ МЕТОД

Симплексный метод разработал американский ученый Дж.Б.Данциг в 1947 г. и впервые опубликовал его в журнале «Эконометрика» во второй половине 1949 г., т.е. ровно через 10 лет после выхода в свет первой работы в области линейного программирования советского ученого Л. В. Канторовича, в которой был изложен метод

разрешающих множителей.

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

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

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

улучшения плана.

3.1.Основной алгоритм симплексного метода

Кнастоящему времени разработано и усовершенствовано несколько алгоритмов симплексного метода. Сначала здесь нами рассматривается решение задачи с помощью основного алгоритма симплексного метода.

Рассмотрим применение основного алгоритма симплексного метода на примере задачи, которая нами была изложена и математически сформулирована в 1.2.

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

F=3x1+4x2+6x3+0 x4+0 x5+0 x6+0 x7, при					ограничениях, представляющихся					в	виде
системы линейных уравнений:
2x1 + 3x2			+ 5x3 + x4				= 1500,
x1 + 4x2			+ 2x3		+ x5		= 1000,
									и при условии xj≥0	j=1,2,…,7.
3x1 + 2x2			+ 3x3		+ x6		= 1800,
4x	+ 2x	2	+ 5x	3	+ x	7	= 2200
1

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

Итак:

F = 3x1 + 4x2 + 6x3 + 0x4 + 0x5 + 0x6 + 0x7																		= max					(3.1)
1500	= 2x	+ 3x			+ 5x			+1x			+ 0x		+ 0x			+ 0x					,
	1		2			3			4			5			6				7
1000	= 1x1 + 4x2				+ 2x3 + 0x4						+1x5 + 0x6					+ 0x7					,		(3.2)
1800	= 3x1 + 2x2				+ 3x3 + 0x4						+ 0x5 +1x6					+ 0x7 ,
2200 = 4x		+ 2x		2	+ 5x		3	+ 0x		4	+ 0x		5	+ 0x		6	+1x			7		.
	1

Уравнения вида (3.2) принято называть симплексными n.

100

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

			Показатели критерия
			оптимальности
			(коэффициенты сj
			целевой функции)
С0	Р0	В	Шапка матрицы (наи-		∑	β	α
			мен. неизвестных)
Коэфф.	Наи-	Ито-			Конт-		Коэф-
целевой	мен	гов.	Основание матрицы		роль-		фици-
функции	ова-	стол			ный	Вi	енты
			(коэффициенты αij
(сj) при	ние	бец			стол-		пере-
			ограничительных
базис-	ба-	(знач.			бец	αik	счета
			условий задачи)
ных	зис-	базис-			(суммы		эле-
неизв.	ных	ных			элемен-		мен-
	не-	неиз-			тов по		тов
	изв.	вест.			строкам		строк
	хi	Вi)			Bi +		матри
		Знач.	Оценочная строка		n		цы
		целев.	(двойственные оценки		∑αij )
		функ-	j)		j=1
		ции

Рис.3.1.

Каждая симплексная таблица соответствует определенному этапу решения задачи

– в ней отражается определенный вариант программы (план).

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

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

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

Итак, рассмотрим таблицу по строкам.

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

Затем заполняют верхнюю строку таблицы. В нее заносятся коэффициенты сj при неизвестных из целевой функции F (3.1)*.

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