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

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

 

z (X) = z (x ₁; x ₂; x ₃; … x_n) = c ₁ x ₁ + c ₂ x ₂ + … + c_nx_n, (3.1)

 

определенной на некотором выпуклом подмножестве n -мерного пространства. Данное подмножество (многогранник) задается некоторой системой линейных неравенств и уравнений:

 

a ₁₁ x ₁ + a ₁₂ x ₂ + a ₁₃ x ₃ + … + a _{1 n}x_n £ b ₁,

…………………………………………

a_{k 1} x ₁ + a_{k 2} x ₂ + a_{k 3} x ₃ + … + a_knx_n £ b_k,

a_{k+ 1;1} x ₁ + a_{k+ 1;2} x ₂ + … + a_{k+ 1; n} x_n = b_{k+ 1}, (3.2)

………………………………………….

a_{m 1} x ₁ + a_{m 2} x ₂ + a_{m 3} x ₃ + … + a_mnx_n = b_m,

x ₁; x ₂; x ₃; … x_s ³ 0.

 

Равенства и неравенства, входящие в систему (3.2), называются ограничениями. Если все ограничения системы (3.2) являются равенствами и все переменные x_i ограничены на знак (" i x_i ³ 0), то задача называется канонической, а если все ограничения являются неравенствами и при этом все переменные ограничены на знак, то задача называется стандартной.

Функция z (X) = z (x ₁; x ₂; x ₃; … x_n) называется функцией цели. Любое решение системы ограничений, включая ограничения на знак, называется планом задачи. План, на котором функция цели достигает своего максимума (минимума), называется оптимальным. Задача линейного программирования может иметь единственное решение (единственный оптимальный план), бесчисленное множество решений или вообще не иметь решений. Причем задача может не иметь решений по двум причинам: из-за отсутствия планов (несовместности системы ограничений) или из-за неограниченности функции цели на множестве планов.

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

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

Точнее, симплекс-метод состоит в следующем:

1. Он позволяет найти первоначальный опорный план (возможно далеко не оптимальный) или доказать, что задача не имеет решения из-за отсутствия планов.

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

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

Понятно, что геометрически можно решать только простейшие задачи. А сведение общей задачи к канонической приводит к неоправданному увеличению числа переменных. Пусть, например, функция цели зависит от n переменных, система ограничений содержит k неравенств и m – k уравнений, причем только s переменных ограничены на знак. Тогда при сведении задачи к канонической мы должны ввести следующие добавочные переменные:

1) k переменных вводятся для превращения неравенств в уравнения;

2) n – s переменных вводится для того, чтобы ограничить на знак все переменные (если переменная x_i неограниченна на знак, то ее заменяют на разность дух переменных, ограниченных на знак: x_i = x_i ¢ – x_i ², x_i ¢ ³ 0, x_i ² ³ 0).

Кроме того, для «запуска» симплекс-метода необходим первоначальный оперный план, для чего приходится вводить «искусственные» переменные порой во все ограничения задачи. Это еще m переменных. Итого, каноническая задача может содержать n + k + n – s + m = 2 n + k + m – s переменных, для каждой из которых отводится отдельный столбец симплекс-таблицы. А затем с помощью специального алгоритма, основанного на методе Гаусса-Жордана, таблица несколько раз пересчитывается, вплоть до получения окончательного ответа.

Причем количество шагов, необходимых для получения ответа, напрямую зависит от числа переменных, участвующих в задаче. Геометрически это означает то, что в поисках оптимального плана нам приходится «путешествовать» по ребрам многогранника, находящегося в пространстве размерности 2 n + k + m – s. Данное число может более, чем втрое, превышать n (размерность задачи). Поэтому решать задачу таким методом вручную крайне затруднительно. При использовании ЭВМ, в случае большого количества переменных, мы так же можем столкнуться со многими неприятностями.

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

Пусть, по-прежнему, функция цели зависит от n переменных, система ограничений содержит k неравенств и r = m – k уравнений, и только s переменных ограничены на знак. Последовательно выражая в каждом из уравнений одну из переменных и подставляя их во все остальные ограничения и в функцию цели, мы получаем задачу с n – r переменными (симплекс-таблица уменьшается на r столбцов). Кроме того, отсутствие ограничений на знак некоторых переменных так же приводит к уменьшению симплекс-таблицы (на n – s строк). Подробнее об этом рассказывается в §3 настоящей главы.

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

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

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

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

 

Описание метода Штифеля

 

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

 

z (X) = c ₁ x ₁ + c ₂ x ₂ +…+ c_jx_j +…+ c_nx_n ® max (3.3)

 

a ₁₁ x ₁ + a ₁₂ x ₂ +…+ a _{1 j}x_j +…+ a _{1 n}x_n £ b ₁

……………………………………………

a_{i 1} x ₁ + a_{i 2} x ₂ +…+ a_ijx_j +…+ a_inx_n £ b_i (3.4)

……………………………………………

a_{m 1} x ₁ + a_{m 2} x ₂ +…+ a_mjx_j +…+ a_mnx_n £ b_m

x ₁; x ₂; … x_j; … x_n ³ 0

 

Введем в систему (3.4) m дополнительных, ограниченных на знак переменных. Для этого перенесем все слагаемые из левых частей неравенств (3.4) в правые:

 

y ₁ = b ₁+ a ₁₁(– x ₁) + a ₁₂(– x ₂) +…+ a _{1 j} (– x_j) +…+ a _{1 n} (– x_n),

……………………………………………………………….

y_i = b_i + a_{i 1}(– x ₁) + a_{i 2}(– x ₂) +…+ a_ij (– x_j) +…+ a_in (– x_n), (3.5)

……………………………………………………………….

y_m = b_m + a_{m 1}(– x ₁) + a_{m 2}(– x ₂) +…+ a_mj (– x_j) +…+ a_mn (– x_n),

x ₁; x ₂; … x_n; y ₁; y ₂; … y_m ³ 0.

 

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

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

	– x 1	– x 2	…	– xj	…	– xn
y 1	a 11	a 12	…	a 1 j	…	a 1 n	b 1
…	……………………………………………	…
yi	ai 1	ai 2	…	aij	…	ain	bi
…	……………………………………………	…
ym	am 1	am 2	…	amj	…	amn	bm
z	– c 1	– c 2	…	– cj	…	– cn

Табл. 3.1.

 

Верхние строки таблицы соответствуют системе ограничений задачи, а нижнюю строку мы зарезервируем за функцией цели. Именно эта строка таблицы и будет играть ключевую роль в решении задачи. В дальнейшем элементы последней строки жордановой таблицы мы будем называть оценками соответствующих свободных переменных. В исходной таблице 3.1 числа -c ₁, -c ₂,…, -c_j,…, -c_n являются оценками свободных переменных x ₁, x ₂,…, x_j,…, x_n, соответственно.

Свободными переменными мы в дальнейшем будем называть переменные, расположенные в верхней заглавной строке жордановой таблицы. На первом этапе решения задачи это переменные x ₁,…, x_n. Придавая свободным переменным различные значения, мы каждый раз будем получать различные значения зависимых (базисных) переменных (на первом этапе, это переменные y ₁,…, y_m). В частности, придавая свободным переменным нулевые значения, мы получаем так называемые базисные решения системы (3.5). Исходным базисным решением является вектор
(0,…, 0,…, 0, b ₁,…, b_i,…, b_m).

Причем лишь те решения (x ₁,…, x_n, y ₁,…, y_m) системы ограничений являются планами исходной задачи (3.3) – (3.5), все компоненты которых ограничены на знак (x_j ³ 0, y_i ³ 0, j = 1, 2,…, n, i = 1, 2,…, m). Базисные решения системы ограничений (3.5), являющиеся планами (т.е. ограниченные на знак), называются опорными планами задачи (3.3) – (3.5). В дальнейшем мы увидим, что оптимальный план задачи, если он существует, находится среди опорных планов.

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

Среди правых частей b ₁,…, b_i,…, b_m системы ограничений (3.5) могут оказаться отрицательные числа. Поэтому исходное базисное решение (0,…, 0,…, 0, b ₁,…, b_i,…, b_m) системы ограничений (3.5), найденное из таблицы 3.1, как правило, не является планом задачи. Данное обстоятельство приводит нас к необходимости решать задачу в два этапа. На первом этапе мы выходим в область планов исходной задачи (3.3) – (3.5) или доказываем, что задача не имеет решения из-за отсутствия планов. На втором этапе мы находим оптимальный план или доказываем неразрешимость задачи из-за неограниченности функции цели.

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

Зафиксируем j -й столбец жордановой таблицы (3.1). Для тех элементов a_ij данного столбца, знак которых совпадает со знаком свободного члена b_i, расположенного в той же строке, что и a_ij, определим отношение:

.

Числа называются симплексными отношениями. Из определения следует, что все симплексные отношения строго больше нуля.

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

 

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

Доказательство. Предположим, что минимальное симплексное отношение в выбранном j -ом столбце соответствует r -ой строке. То есть

 

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

Выясним теперь, как изменяется свободный член в произвольной i –ой строке (i ¹ r). Для этого вспомним, что после одного шага модифицированных жордановых исключений свободный член, так же как и любой другой элемент жордановой таблицы, не попавший в разрешающие строку и столбец, вычисляется по формуле (1.12):

. (3.7)

Рассмотрим три случая:

1. b_i > 0. Если при этом a_ij = 0, то . То есть свободный член не изменился не только по знаку, но и по абсолютной величине. Если
a_ij ¹ 0, то формулу (3.7) можно преобразовать к виду:

. (3.8)
Если a_ij > 0, то , так как – минимальное симплексное отношение, а – произвольное симплексное отношение. Следовательно, в данной ситуации , как произведение двух неотрицательных чисел. То есть знак совпадает со знаком b_i.
Если a_ij < 0, то скобка в равенстве (3.8) будет отрицательной, так как оба составляющие ее слагаемые строго меньше нуля. Следовательно, и в этом случае знак совпадает со знаком b_i, так как произведение двух отрицательных чисел – положительно.

2. b_i < 0. Если при этом a_ij = 0, то по-прежнему , т.е. знаки и b_i совпадают. Если a_ij ¹ 0, то вновь воспользуемся формулой (3.8).
Если a_ij < 0, то , так как – минимальное симплексное отношение, а – произвольное симплексное отношение. Следовательно, в данной ситуации , как произведение противоположных по знаку чисел. То есть знак совпадает со знаком b_i.

Если a_ij > 0, то скобка в равенстве (3.8) будет отрицательной, так как оба составляющие ее слагаемые строго меньше нуля. Следовательно, и в этом случае знак будет отрицательным и, следовательно, совпадает со знаком b_i.

3. b_i = 0. В данном случае после одного шага модифицированных жордановых исключений знак свободного члена может стать как положительным, так и отрицательным. Точнее, из формулы (3.7) следует, что знак будет противоположен знаку a_ij. Так как число 0 можно считать как положительным, так и отрицательным, то и в этом случае можно считать, что знак совпадает со знаком b_i. Теорема доказана.

 

§3 Нахождение первоначального опорного плана

 

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

Пусть в столбце свободных членов нет ни одного отрицательного числа, т. е. В данном случае первоначальное базисное решение (0,…, 0,…, 0, b ₁,…, b_i,…, b_m), получающееся из таблицы 3.1, сразу является опорным планом задачи. Мы можем переходить ко второму этапу, т.е. к поиску оптимального плана.

Если среди свободных членов есть отрицательные числа, то от них избавляются с помощью конечного числа шагов метода Штифеля. Рассмотрим подробнее, как это делается. Пусть, например, b_r < 0. Найдем j –й столбец, содержащий отрицательный элемент a_rj в r –ой строке. Здесь возможны два случая.

1. Такого столбца не существует, т.е. все элементы r –ой строки неотрицательны (a_rj ³ 0, j = 1, 2,…, n). В данном случае мы можем сделать вывод о том, что задача не имеет решения из-за отсутствия планов. Действительно, рассматривая r – ю строку таблицы 3.1, мы приходим к выводу о том, что переменная y_r не может быть неотрицательной ни при каких неотрицательных значениях переменных x ₁, x ₂,…, x_n:

y_r = b_r + a_{r 1}(- x ₁) + a_{r 2}(- x ₂) +…+ a_rj (- x_j) +…+ a_rn (- x_n) £ b_r < 0.

Иными словами r – е ограничение системы (3.4) не выполняется ни при каких значениях x ₁; x ₂; …, x_n ³ 0

2. В r –ой строке существуют отрицательные элементы. Пусть, например, a_rj < 0. Рассмотрим j –й столбец и выберем в нем разрешающий элемент по принципу минимального симплексного отношения. Если нам повезет, то минимальное симплексное отношение будет соответствовать r –ой строке. Тогда после одного шага метода Штифеля, в соответствие с теоремой 3.1, мы добьемся того, что свободный член в r –ой строке станет неотрицательным. Остальные свободные члены не изменят своих знаков. Таким образом, количество отрицательных правых частей уменьшится. Поступая аналогично с остальными строками, мы, за конечное число шагов, добьемся того, что все свободные члены станут положительными. Тем самым мы найдем первоначальный опорный план.
Если же разрешающий элемент не попадает в r –ю строку, то соответствующий шаг метода Штифеля не приведет к изменению знака свободного члена b_r. Мы совершаем своего рода «холостой шаг», после которого опять выбираем разрешающий элемент в j –ом столбце по принципу минимального симплексного отношения. И так мы поступаем до тех пор, пока разрешающий элемент не попадет в r –ю строку.

Рассмотрим следующие примеры.

 

Пример 3.1. Найти первоначальный опорный план задачи, заданной жордановой таблицей 3.2 (все переменные, участвующие в задаче, предполагаются неотрицательными).

 

	– x 1	– x 2	– x 3	– x 4		ti 3
y 1		–4
y 2			–2		–3	1.5
y 3		–7		–4
y 4	–2		–4			–
z	–1	–15				–

Табл. 3.2.

 

Решение. Для наглядности введем в таблицу 3.2 дополнительный правый столбец для симплексных отношений. Рассмотрим столбец свободных членов, расположенных под единицей. Среди чисел данного столбца есть одно отрицательное число b ₂ = – 3. Следовательно, базисное решение (0; 0; 0; 0; 2; -3; 4; 6) не является опорным планом задачи (как всегда вначале идут иксовые, а затем игрековые координаты, в порядке возрастания индексов). Рассмотрим вторую строку таблицы и найдем в ней отрицательные числа. Такое число в данном случае единственно и равно a ₂₃ = –2. Так как данное число расположено в третьем столбце, то будем разрешающий элемент искать именно в этом столбце. Для этого вычислим симплексные отношения для элементов третьего столбца и запишем их в правый дополнительный столбец таблицы 3.2.

.

При этом симплексное отношение не вычисляется для последней строки, т.к. разрешающий элемент никогда не выбирается среди коэффициентов функции цели. Кроме того, на месте t ₄₃ в таблице 3.2 стоит прочерк, т.к. симплексное отношение не может быть отрицательно. Сравнивая полученные симплексные отношения, мы приходим к выводу, что наименьшее симплексное отношение приходится на вторую строку. Следовательно, в качестве разрешающего элемента необходимо выбрать элемент a ₂₃ = –2.

В данном случае нам повезло, т.к. разрешающий элемент попал в ту строку, в которой расположен отрицательный свободный член b ₂ = –3. Следовательно, по теореме о минимальном симплексном отношении, после одного шага метода Штифеля, мы добьемся того, что знак свободного члена b ₂¢ станет положительным, а остальные свободные члены при этом сохранят свои знаки. Мы приходим к таблице 3.3.

 

	– x 1	– x 2	– y 2	– x 4
y 1		–2	0,5		0,5
x 3	–3	–2	–0,5	–4	1,5
y 3		–3
y 4	–14		–2	–11
z		–1	3,5		–10,5

Табл. 3.3.

 

Так как среди свободных членов в таблице 3.3 нет отрицательных чисел, то, следовательно, мы нашли первоначальный опорный план задачи:
X ₀ = (0; 0; 1,5; 0; 0,5; 0; 1; 12).

Пример 3.2. Найти первоначальный опорный план задачи, заданной жордановой таблицей 3.4 (все переменные, участвующие в задаче, предполагаются неотрицательными).

 

	– x 1	– x 2	– x 3	– x 4		ti 3
y 1		–4
y 2			–2		–3	1.5
y 3		–7		–4
y 4	–2		–4			–
z	–1	–15				–

Табл. 3.4.

 

Решение. Данная задача отличается от предыдущей задачи всего одним числом (a ₁₃ = 2). Мы по-прежнему имеем только один отрицательный свободный член b ₂ = – 3. Рассмотрим вторую строку таблицы и найдем в ней отрицательные числа. Такое число, как и в предыдущем примере, единственно и равно a ₂₃ = – 2. Так как данное число расположено в третьем столбце, то будем разрешающий элемент искать именно в этом столбце. Для этого вычислим симплексные отношения для элементов третьего столбца и запишем их в правый дополнительный столбец таблицы 3.2.

.

Сравнивая полученные симплексные отношения, мы приходим к выводу, что наименьшее симплексное отношение приходится на первую строку. Следовательно, в качестве разрешающего элемента необходимо выбрать элемент a ₁₃ = 2. В данном случае разрешающий элемент не попал в ту строку, в которой расположен отрицательный свободный член b ₂ = –3. Мы вынуждены сделать «холостой шаг», после которого знак свободного члена b ₂¢ не станет положительным. Но при этом не появится других отрицательных свободных членов, что гарантирует теорема о минимальном симплексном отношении. После одного шага метода Штифеля, мы приходим к таблице 3.5:

 

	– x 1	– x 2	– y 1	– x 4
x 3	2,5	–2	0,5	1,5
y 2					–1
y 3	–2	–3	–1	–7
y 4
z	–18,5	–1	–3,5	–5,5	–7

Табл. 3.5.

 

Хотя знак свободного члена b ₂¢ и не изменился, сделанный шаг метода Штифеля позволил нам сделать определенный вывод: положительность всех элементов второй строки, за исключением свободного члена, говорит о том, что задача не имеет планов. Изменив еще одно число в исходной таблице 3.4, мы получим еще один интересный пример.

Пример 3.3. Найти первоначальный опорный план задачи, заданной жордановой таблицей 3.6 (все переменные, участвующие в задаче, предполагаются неотрицательными).

 

	– x 1	– x 2	– x 3	– x 4		ti 3
y 1		–4
y 2			–2		–3	1.5
y 3		–7		–4
y 4	–2		–4			–
z	–1	–15				–

Табл. 3.6.

Решение. Действуя так же, как в предыдущем примере, мы приходим к выводу о том, что разрешающим элементом на первом шаге должен быть элемент a ₁₃ = 2. Разрешающий элемент снова не попал в ту строку, в которой расположен отрицательный свободный член b ₂ = -3. Мы вынуждены сделать «холостой шаг», после которого мы приходим к таблице 3.7:

 

 

	– x 1	– x 2	– y 1	– x 4		ti 2
x 3	2,5	-2	0,5	1,5		-
y 2		–1			–1
y 3	–2	–3	–1	–7		–
y 4
z	–18,5	–1	–3,5	–5,5	–7	–

Табл. 3.7.

 

Вычислим симплексные отношения для второй строки:

 

 

Только t ₂₂ = 1 и t ₄₂ = 10 больше нуля, и, следовательно, являются симплексными отношениями. Так как t ₂₂ < t ₄₂, то разрешающий элемент приходится на вторую строку, и следующий шаг уже не является «холостым». Мы избавляемся от единственного отрицательного свободного члена и, тем самым, находим первоначальный опорный план:

 

 

	– x 1	– y 2	– y 1	– x 4
x 3	–19,5	–2	–1,5	–20,5
x 2	–11	–1	–1	–11
y 3	–35	–3	–4	–40
y 4
z	–29,5	–1	–4,5	–16,5	–6

Табл. 3.8.

 

Итак, первоначальным опорным планом задачи является
X ₀ = (0; 1; 3; 0; 0; 0; 5; 9). Если нас не интересуют значения переменных y_j, то мы можем отбросить последние четыре координаты вектора X ₀. Таким образом, X ₀¢ = (0; 1; 3; 0).

 

 

§4 Нахождение оптимального опорного плана

 

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

Действительно, свободные переменные, расположенные в верхнем заглавном столбце таблицы, предполагаются равными нулю (именно в этом случае мы получаем опорный план). При переходе к другому плану задачи (не обязательно опорному), мы должны изменить значения свободных переменных. Но эти значения могут только увеличиться, т.к. все переменные основной задачи неотрицательны. Добиться увеличения функции цели можно за счет увеличения тех переменных x_j, коэффициенты при которых c_j больше нуля. Например, если – c_j < 0 (см. таблицей 3.1), т.е. c_j > 0, то, увеличивая соответствующую переменную x_j, можно добиться увеличения функции цели z (X) = c ₁ x ₁ + c ₂ x ₂ +…+ c_jx_j +…+ c_nx_n.

На практике обычно так и поступают. Находят отрицательные числа (оценки свободных переменных) в последней строке таблицы, выбирают из них наименьшее число -c_j и увеличивают соответствующую переменную x_j. Увеличение переменной x_j приводит к изменению зависимых переменных y_i. При этом возможны следующие случаи:

1. Неограниченное увеличение переменной x_j не приводит к появлению отрицательных знаков ни у одной из переменных y_i. Такое возможно, когда все элементы j -го столбца a_ij меньше или равны нулю. В данном случае, увеличивая переменную x_j, мы тем самым неограниченно увеличиваем функцию цели, оставаясь при этом в области планов задачи (причем функция цели растет линейно с ростом переменной x_j). Мы приходим к выводу о том, что задача не имеет решения из-за неограниченного роста функции цели. Разумеется, такое стало возможным благодаря тому, что область планов исходной задачи неограниченна.

2. Увеличение переменной x_j рано или поздно приведет к появлению отрицательных знаков у некоторых (хотя бы у одной) переменных y_i. Для этого необходимо, чтобы некоторые элементы j -го столбца a_ij были строго больше нуля. Так как функция цели растет вместе с ростом переменной x_j, то переменную x_j стараются увеличивать до тех пор, пока это возможно. А точнее, переменную x_j увеличивают до тех пор, пока одна из переменных y_i не станет равной нулю, а остальные базисные переменные при этом останутся неотрицательными. При этом переменная x_j становится базисной, а переменная y_i – свободной.

Такое преобразование может быть осуществлено с помощью одного шага метода жордановых исключений (Штифеля). Если разрешающий элемент выбирать в j -ом столбце по принципу минимального симплексного отношения, то все базисные переменные сохранят свои знаки, т.е. мы не выйдем из области планов задачи. Это как раз и будет соответствовать тому, что из числа базисных в разряд свободных перейдет та переменная y_i, которая раньше других обратится в ноль.

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

Однако бывают случаи, когда

⇐ Предыдущая123456789Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: