1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ - МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ - Книжный рай
МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Типичной задачей линейного программирования (ЗЛП) является задача определения оптимального ассортимента. Рассмотрим более подробно ее математическую модель.

Пусть на предприятии имеется т видов ресурсов в количествах Ь\, 62) • • •) Ьт. Технологически предприятие в состоянии выпускать п видов различных изделий, причем норма расхода ресурса j-ro вида (j = 1,2,... ,т) на единицу г-го изделия (т. е. изделия под номером г) является величиной заданной, обозначим ее ау. Эффективность выпуска единицы изделия г-ro наименования, т. е. прибыль предприятия после его изготовления и реализации, является величиной известной и характеризуется показателем с, .

Задача состоит в том, чтобы определить план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности принимает наибольшее значение.

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

Функция цели вида

п

Е = /(ж) = С\Х\ + С2Х2 +----h СпХп = ^2 сгхг

г=1

должна быть максимизирована за счет наилучшего выбора значений Х\,Х2, ■ ■ ■ ,хп. Однако выбор должен осуществляться так, чтобы не

10

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

п

^2"и-''* < bji      і = 1,2,...,m.

i=l

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

Х\ > О, Х2 > 0, ..., хп > 0.

Таким образом, окончательно задача будет иметь такой вид: найти

п

max г = ^c, a;, (1.1)

г=1

при ограничениях

п

X/''Я'» < kh      І = l,2,...,m; (1.2)

г=1

X! > 0, х2 > 0,       хп > 0. (1.3) В данном случае функция цели /(ж) = ^ с,ж, и ограничения

» г=1

^ ауж, < bj являются линейными относительно управляемых пере-i=i

менных, т. е. Х\,Х2, ■ ■ ■ ,хп входят в указанные выражения в первой степени с некоторыми постоянными коэффициентами. Следовательно, имеем типичную ЗЛП.

В наиболее общем виде математически поставленная ЗЛП формулируется так: требуется найти такие значения х\, х®, ■ ■ ■, хап переменных х\, Х2, ■ ■ ■ ,хп, которые удовлетворяют соотношениям вида ацХі + аі2Х2 + ••• + alnxn R± bi,

й2\Хі + 022X2 + ••• + а.2пХп R2 b2,

' (1.4)

&тіХі ~~Ь 0>т2Х2 ~\~ ' ' ' ~\~ 0>тпХп Rrn^m

и при этом определяют экстремальное (наибольшее или наименьшее) значение функции

f(xi,X2, ■ ■ .,Хп) = СіХі + С2Х2 +----h спхп (1.5)

11

по сравнению с ее значениями при всех других наборах переменных х\, Х2, ■ ■ ■, хп, удовлетворяющих систему ограничений. Здесь Ri, R2, ■ ■ ■, Rm """""""" один из знаков "<", "=" или ">"; (щ, bj, с» — заданные действительные числа.

Любой упорядоченный набор (х\, Х2, ■ ■ ■, хп) значений переменных, удовлетворяющих всем ограничениям (1.4) (т. е. любое решение системы линейных уравнений и(или) неравенств (1.4)), называется допустимым решением, или планом задачи. Множество всех допустимых решений называется допустимым множеством задачи. Допустимое решение х\,х%,... ,хап, при котором целевая функция (1.5) принимает максимальное (минимальное) значение, называется оптимальным решением, оптимальным планом или просто решением рассматриваемой ЗЛП.

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

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

Пусть эффективность производства изделий наименований 1 и 2 составляет соответственно с\ = 2; С2 = 5. Кроме того, предприятие располагает тремя видами ресурсов в объемах Ь\ = 400; 62 = 300; Ьз = 500, причем технология производства такова, что ресурсы первого вида расходуются на производство изделий первого наименования, второго — на производство изделий второго наименования и третьего — на производство изделий обоих наименований и при этом в равных долях. Модель задачи такова: найти

max z = 2х\ + 5x2

при

хг < 400,   Х2 < 300,   хг + х2 < 500 и, естественно,

Х\ > 0,    Х2 > 0.

Построив на плоскости Х\Ох2 графики функций всех ограничений, получим следующий график.

12

Таким образом, допустимая область решений данной ЗЛП представляет собой многоугольник OABCD. График целевой функции f(xi,X2) = 1х\ + 5x2 есть множество прямых линий вида 2xi + 5x2 = = const, среди которых нужно выбрать такую, чтобы значение const было максимальным. Этого можно достичь параллельным сдвигом линии 2xi + 5x2 в сторону увеличения const. Очевидно, прямая, проходящая через точку В, и будет искомой.

13

Рассмотрим прямые 2х\ + •"».>••_> = Z\; 2х\ + •"».>••_> = z2 и 2жі + •">.>••_> = z3.

Очевидно, имеет место соотношение Z\ < < Zg, т. е. прямая, проходящая через точку В, будет наилучшей, так как для всех линий, расположенных ниже, выполняется Z\ < ZiТретья прямая хотя и соответствует большей константе Zg > Zi, но не имеет с допустимой областью решений общих точек. Таким образом, единственная точка, принадлежащая одновременно прямой f(x\,X2) = Z2 и допустимой области решений, т. е. точка В, будет оптимальным решением поставленной ЗЛП. Координаты этой точки (200; 300) легко определить на графике.

В такой геометрической интерпретации становятся очевидными основные свойства ЗЛП, которые сформулированы в следующей теореме.

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

Это означает, что решение ЗЛП следует искать лишь в крайних точках допустимого множества решений.

Естественным в этом случае кажется следующий подход. Можно найти каким-либо способом все вершины допустимого множества (доказано, что их число всегда конечно) и, сравнив между собой значения целевой функции в них, выбрать наилучшее. Но такой путь решения ЗЛП, даже с относительно небольшим количеством ограничений и неизвестных, практически неосуществим, так как процесс отыскания вершин весьма трудоемкий, а вершин многогранника может оказаться очень много. Но если осуществлять целенаправленный перебор вершин, то процесс вычислений значительно сократится, так как вершины с заведомо худшим значением целевой функции будут исключены при расчетах. Для определения момента окончания вычислений используют критерий завершения процедуры. Именно такими свойствами обладает симплекс-метод решения ЗЛП (предложен в 1939 г. математиком И. Данцигом), или иначе — метод последовательного улучшения плана. Процедура вычислений в нем гарантирует "улучшение" значения целевой функции в каждой последующей вершине по сравнению с предыдущей, а также выделяет ситуации,

14

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

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

В зависимости от ограничений в условиях исходной задачи различают несколько форм представления ЗЛП. Если ограничения заданы в виде равенств

ацХі + аі2Х2 + ■■■ + а1пхп = bi,

a2lXi +   (I22X2 + ••• +   (І2пХп = &2,

(1.6)

ат1хл + ат2х2 + ■■■ + атпхп = Ьт и неизвестные удовлетворяют прямым ограничениям

Хі > О, Х2 > 0,        хп > 0, (1.7)

то такая форма ЗЛП называется канонической.

Если в ограничениях (1.6) используются не только равенства, но и неравенства вида "<", ">", а прямые ограничения (1.7) накладываются лишь на часть переменных, то такая форма ЗЛП называется общей.

Стандартная форма ЗЛП

Существуют стандартные приемы перехода от произвольной ЗЛП к любому специальному ее виду. Как правило, это достигается введением дополнительных переменных, или расширением пространства. Рассмотрим, например, способы перехода к каноническому виду ЗЛП.

Пусть исходная ЗЛП представлена не в канонической форме:

С\Х\ + С2Х2 + ■ ■ ■ + спхп —¥ min (max); (1.8)

ацХі + ai2X2 + ■■■ + alnxn = bi,

.................................... (1-9)

aklX! + ak2X2 + ■■■ + aknxn = bk;

15

(1.10)

amixi +    am2x2 + ■ ■ ■ +    amnxn < bm, xi > 0, ..., xr > 0,   r < те.

Для того чтобы от ограничений-неравенств (1.9) перейти к строгим равенствам, в неравенства к + 1,к + 2,... ,тп вводят дополнительные переменные жп+і > 0; ж„+2 > 0, ...; жп+(то_д.) > 0, которые в целевую функцию входят с нулевыми коэффициентами:

+ afc+i,2#2 + ••• +a.k+i,nxn + Xn+i        = Ьк+1,

Лк+2,іХі + йк+2,2Х2 + ■■■ +ак+2,ПХп + Хп+2 = Ьк+2,

&тіХі ""Ь      G>m2X2 ~\~ ' ' ' ~\~    0>тпХп ~~Ь <£?г+(т—&) — Ьт.

Переменные, для которых не требуется условие неотрицательности, формально заменяются разностью двух положительных переменных:

Xf~^~.\ — Xy>__j__.i^ ™~    у>__|„.;  Xfj^-^ — Xy>__j__.2 ™™™ *^у-4--25  ' ' ' 'і Xfi — X'™~ Xj^.f

где x'r+1 > 0, ж"+1 > 0, ...,      > 0, ж" > 0.

Пример. Привести к каноническому виду задачу

2.Г| — 3x2 + "».r:» —  ж4 —¥ max,

Х\ + 2x2 —  Xz +  .Г|  < 2. 2.Г| — 3^2 — 2.г:» + ">.г і = 4, Зжі + Х2 + Зжз — .Г| < 3. х\ > 0,      жз > 0.

Вводим две дополнительные переменные х% > 0 и Же > 0 в первом и третьем ограничении, а переменные ж 2 и 14, для которых не требуется неотрицательность, заменяем соответственно двумя разностями: Х2 = х'2 — ж2'; ж 4 = х\ — х'1, где х'2 > 0; х'2' > 0; х'4 > 0; ж£ > 0.

16

Таким образом, получаем следующую задачу канонического вида:

2х\ — 3(ж2 — х'2) + 5ж3 —   (х'4 — ж") + 0 • Ж5 + 0 • же —^ max, х\ + 2(х'2 х'2)  х3 +   (х'4 ж") +    ж5 =2, 2xi — 3(ж2 — х'2) — 2ж3 + 5(х'4 — ж") = 4,

Зжі +   (х'2 — ж2) + Зж3 —   (х'4 — ж") + же = 3,

жі > 0; х'2 > 0; х'2' > 0; ж3 > 0; х'4 > 0; х'( > 0; ж5 > 0; ж6 > 0.

Иногда необходимо заменить задачу максимизации эквивалентной ей задачей минимизации, или наоборот. Для этого изменяют знак целевой функции, оставляя неизменными ограничения исходной ЗЛП: тах/(жі,Ж2,.. •, хп) = min[—/(жі,Ж2, •.., ж„)]. В этом легко убедиться на примере функции одной переменной при а < х± < Ь.

Обоснование симплекс-метода решения ЗЛИ

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

С\Х\ +   С2Х2 + ■ ■ ■ +   спхп —¥ max, ацЖі + аі2ж2 + ••• + alnxn = Ъ\, а2іЖі + а22ж2 + ••• + а2„ж„ = Ь2,

&тіХі ""Ь G>m2X2 ~\~ ' ' ' ~\~ G>mnXn   — Ьті Жі > 0,     Ж2 > 0,     . . . ,     Ж„ > 0.

Такое представление ЗЛП, где все уравнения записаны в развернутом виде, называется координатной формой записи. В векторной форме эта ЗЛП выглядит так:

(с, х) —¥ max,

Aixi + А2Х2 +----h Anxn = A0,

x>0.

Здесь с — вектор коэффициентов при неизвестных в целевой функции с = (сі, с2,..., с„); X — вектор переменных х = (жі, ж2,..., ж„); Aj — m-мерный вектор-столбец коэффициентов при жj,

17

А, j = 1,2, ...,m;

40 — m-мерный вектор-столбец свободных членов, стоящих в правой части уравнения,

/ h \

Ь2

An

Пусть количество ограничений меньше количества неизвестных, т. е. тег < те. Случай m = те не представляет интереса, поскольку тогда система является крамеровской, т. е. имеет единственное реК,

ь2' ' '

является (в

шение и это решение — точка ж = силу единственности) оптимальным.

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

Пример. Пусть задана система ограничений

2.г і + ж2 + '-''.Г;; = 2,

Х\ — 2ж3 + ж4 =1,

Х\ > О,    Х2 > 0,    Жз > О,    Х4> 0.

А*

А*

3

^2

Ал

Здесь тег = 2; А\

Рассмотрим векторы        = (0,2,0,1); ж^ = (1,0,0,0); ж -,1,0,—^. Легко проверить, что они являются допустимыми

решениями. Выделим среди них опорные. В векторе ж^ вторая и четвертая координаты нулевые, а соответствующие им векторы

(3)

18

,42 = =        j и ,44 = ^ j j линейно независимы. Следовательно,

ж(і) — опорное решение.

Для ж^ только первая координата отлична от нуля, а вектор f 2 \

Ai =  I   j   I ненулевой, следовательно, соответствующая система

(2)

линейно независима и ж1' — опорное решение.

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

Замечание. Векторы Ai,A2,...,Am называются линейно независимыми, если равенство a±Ai + а2А2 + ■ ■ ■ + атАт = 0 возможно только при «і = а2 = • • • = «го = 0.

Пример. Ai = ^ J ^; А2 = ^ j ^. Тогда

лишь при «і = а2 = 0.

Таким образом, линейно независимая система векторов — это минимальный набор векторов, каждый из которого не может быть получен как линейная комбинация остальных векторов. В самом деле, никакими линейными преобразованиями нельзя получить вектор Ai из А2 и наоборот. Но любой двумерный вектор есть их линейная комбинация, а именно: произвольный вектор ^ ^ ^, где а,

Ь — произвольные действительные числа, можно представить в виде а

£  , — a Ai + ЬА2. Такая запись вектора называется разложением

по базису {Ai, А2}.

Пример. Есть набор векторов

Ai =     0    ;   А2 =     2    ; А

1,       -1    ; А

19

Известно, что для размерности т = 3 базисными могут быть только три вектора. Пусть это будут А2, A3, А5. (Матрица В, составленная из этих векторов, имеет определители, отличные от нуля вплоть до третьего порядка.) Тогда координаты любого вектора в данном базисе можно найти по формуле

Х21 \ ХП1 )

( аи \

0-21

\ ani )

где 421 любой небазисный вектор; В = {Аї,А%, А§}

\ а„і )

матрица, составленная из базисных векторов-столбцов, расположенных в порядке их следования в базисе (называется базисной); / хц \

Х21      — вектор-столбец искомых координат, т. е. А\ = A2X11 +

\ ХП1 )

+A3X2i + А5х31.

' 2 2 1

7 -3\

— 1   — 1     0    . Тогда искомые координаты для А\ прини-7    10     6 /

Здесь В

1 t ^ 3

а обратная к ней матрица В

мают значения

В-1 А!

Аналогично

В'1 А4

20

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

Х12\ ( 1 \ / Xls \ ( 0 \ / Xl5 \ ( 0 Ж22     =     0     ;        ж23     =     1     ;        а?2б     = О

хз2 )     \ 0 /      \х3з J     V 0 /      V ж35 / Vі

Если в исходном базисе Аз заменить вектором А±, то линейная независимость набора сохранится, т. е. {А2, А\, А5} также будет базисом, но координаты небазисных векторов при разложении по новому базису, естественно, изменятся.

Алгоритм симплекс-метода

Пусть задана каноническая невырожденная ЗЛП

С\Х\ +   с2х2 + ■ ■ ■ +   спхп —¥ max, (іцХі + a12x2 + ••• + alnxn = bi, a2\X\ + а22Ж2 + ••• + a2nxn = b2,

(ImlXl ""b 0>m2X2 ~~b ' ' ' ~~b G>mnXn   — bmi

x\ > 0, x2 > 0, ..., xn > 0.

Предполагаем, что ранг матрицы А = (ay) равен тег, т. е. все ограничения-равенства задачи линейно независимы.

Пусть известно какое-нибудь опорное решение       =(х^\ х^\ ■ ■ ■

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

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

1. Разложить по исходному базису все небазисные векторы, т. е. найти все коэффициенты xuj, k = 1, тег; j = 1, те, по формуле

(x1:i,x2j,...,xmj)T = B~1(alj,a2j,...,amj)T, где В — базисная матрица.

21

Для вектора An разложение известно: его компоненты совпадают с ненулевыми компонентами заданного опорного решения, т. е. ж,о =

(і)

= xs , где s — номера положительных координат исходного опорного решения.

2. Для каждого j (j = 1,п) вычислить оценку, так называемую симплекс-разность:

Aj = zi ~ сз =      Cs>t Xki ~ сз>

где Cj — коэффициенты при неизвестных переменных Xj в целевой функции; cSk — коэффициенты целевой функции при базисных переменных (всего т); хщ — компоненты соответствующего вектора Aj. Если все коэффициенты cSk объединить в m-мерный вектор с, а коэффициенты Xkj обозначить как вектор-столбец Aj, то симплекс-разность A j можно записать через скалярное произведение векторов в виде

Д,= (с,4,-)-с,-.

Если все Aj > 0, то процесс решения задачи окончен. Рассматриваемое опорное решение оптимально, а оптимум целевой функции

2max = (с, Aq).

Если есть Aj < 0, то переходим к следующему предписанию.

3. Выяснить, существует ли хотя бы одна отрицательная оценка Aj такая, что координаты xuj вектора Aj в заданном базисе будут отрицательны. Если такая оценка Aj есть, то процесс решения задачи окончен. Целевая функция задачи не ограничена (сверху) на допустимом множестве. В противном случае переходим к следующему предписанию.

4. Выбрать наименьшую оценку из Aj < 0 (пусть это будет As); вычислить отношение х^о/Xks Для всех к, для которых Xks > 0, и найти минимальное из этих отношений (пусть это будет в8 = xrn/xrs).

5. Перейти к новому опорному решению, базис которого получается заменой вектора Аг в предыдущем базисе вектором А8. Координаты всех векторов An, Ai,..., Ап в новом базисе вычисляются по таким основным формулам:

/ _ п _ %r j _ _ п

xrj — "і — ~    і     xkj — Xkj — OjXks, Xrs

j = 0,n, k = l,m, кфт.

22

6. Перейти к выполнению предписания 2 и, если потребуется, выполнить дальнейшие предписания, имея в виду новый базис — новые значения XkjКаждый переход к новому базису (а следовательно, к новым значениям величин Xkj) называется шагом, или, чаще, итерацией симплекс-метода. Доказано, что за конечное число шагов (итераций) процесс вычислений закончится либо на п. 2 (найдено оптимальное решение), либо на п. 3 (установлено, что оптимального решения нет).

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

Так, если до преобразования к каноническому виду задача имела ограничения типа "<", то дополнительные переменные, переводящие эти неравенства в строгие равенства, используются в качестве базисных. Если изначально ограничение имело вид равенства, то в его левую часть можно ввести искусственную переменную, которая отличается от дополнительной тем, что в целевую функцию входит не с нулевым, а с достаточно большим коэффициентом М (М О для задачи минимизации и М -С 0, если решается задача максимизации). Для ограничений типа ">" требуются как дополнительные, так и искусственные переменные. Дополнительная переменная, позволяющая преобразовать неравенство в строгое равенство, в этом случае имеет знак "—", тогда соответствующая ей компонента опорного плана будет отрицательной, что недопустимо при такой постановке задачи. Поэтому искусственная переменная помогает избежать подобной неувязки.

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

23

 

 

 

 

 

Л» п/п

Базис

сбаз

 

Сі

С2

 

с5

 

с„

в

Лі

Л2

 

Л5

 

Ап

1

Аіг

Сгі

Хіо

XII

Х12

 

 

 

Xln

XlO Xls

2

 

Сг2

 

Х21

»22

 

»28

 

X-2n

X20 X2s

 

 

 

 

 

 

 

 

 

 

 

г

Аіг

С;г

Хто

Хгі

 

 

Xrs

 

її-гп

XrO Xrs

 

 

 

 

 

 

 

 

 

 

 

т

Аіт

 

ХпгО

її ml

її ml

 

її ms

 

її-mn

XmO Xras

т + 1

 

 

Z

Аі

Аг

 

As

 

Am

 

Здесь z — значение целевой функции при данном опорном решении,

z = (с,ж) = chxw + сІ2х2о Н-----h cimxm0;

симплекс-разности

m

Ai = *i <-.i Y, Ci"Xko -r'k=l

Вектор Ад с наименьшей отрицательной симплекс-разностью As назовем ведущим (разрешающим). В последнем столбце запишем отношения положительных координат разрешающего вектора А8 к соответствующим координатам вектора An.

Базисный вектор Ajr с наименьшим значением в будем выводить из базиса. Строка, соответствующая этому вектору, а также элемент xrs назовем ведущими (разрешающими).

Пример. Найти максимум функции

2х\ — Х2 + Зжз + 2X4

при условиях

2xi +   3^2 —   Жз + 2X4 + Х5 =4, .Гі —   2x2 + 5жз — З.г і —      Хс, =1,

4xi + WX2 + ЗЖз +   Х4 + Х7  = 8,

Xj>0,   і = 1,2,...,7, если известно опорное решение данной задачи (1; 0; 0; 0; 2; 0; 4).

24

Очевидно, ранг матрицы

2 3-1 2 1 0 0

,1     (Л1. . l-j..     .11. .1.-,. If;.Л-)     I   1-2 5 -З 0 -1 0

4 10 3 1 0 0 1

равен 3. Данное опорное решение невырожденное, поскольку имеет три положительные координаты. Базис этого опорного решения составляют векторы А\, А5, Aj, т. е.

«    (. 11. Л-,.. 17) 10   0; В

Разложение небазисных векторов А2, A3, Aj, Ад по исходному базису в сокращенной форме имеет вид

3-1     2     0\     /-2       5   -3 -1

-2     5-3-11 = 1    7   -11     8 2 10     З     1     0/     \ 18   -17    13 it

Если во второе уравнение-ограничение ввести искусственную переменную Ха > 0, то матрица А увеличится на один столбец As, но базисная матрица В = (А$, Aj, А$) будет единичной, следовательно, В^1 = Е (единичная матрица) и коэффициенты жу небазисных векторов пересчитываться не будут.

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

А) =     8     ; А

2

3

-1

 

2

1

0

0

0

4

10

3

 

1

0

0

1

0

1

-2

5

 

3

0

-1

0

1

 

/

' 1

0

0

\

 

 

 

,А8)

=

0

1

0

.

 

 

 

 

 

. о

0

1

 

 

 

 

В = (А5,А7,А

В этом случае опорное решение задается через координаты вектора Aq в виде

ж(1) = (0;0;0;0;4;0;8;1).

25

Заполним первую симплекс-таблицу, соответствующую опорному решению

 

 

 

Л»

Ба-

сбаз

Ао

2

-1

3

2

0

0

0

в

п/п

зис

Аг

А2

Лз

A4

At,

Aq

л7

As

1

А*,

0

4

2

3

-1

2

1

0

0

0

4

-1

2

А7

0

8

4

10

3

1

0

0

1

0

8 3

3

As

1

1

-2

5

-3

0

-1

0

1

1

5

 

 

 

-М-2

2М + 1

-5М-3

ЗМ-2

0

м

0

0

 

z =

(Сбаз) Аз)

= 0-4 + 0

8+(-

М) •

1 =

-м,

 

 

Al

= Z!

Cl

= (Сбаз) Al)

Сі =

0-2

+ 0

4-М-1-2--

= -М 2,

 

А2

= Z2

Cl

= (Сбаз) -42)

— С2 =

0-3

+ 0

10 М • (-2)

+ 1 = 2М + 1

 

А3

= zz

^Сз

= (Сбаз) Аз)

^Сз =

о.(-

-1)-

Ю-З-М-5-

3= -5М-3

 

А4

= 04

c4

= (Сбаз) A4)

с4 =

0-2

+ 0

1-М(-3) -

-2 = ЗМ-2,

 

А6

= z6

^c6

= (Сбаз) Аз)

^с6 =

0-0

+ 0

0-М •(-!)-

0 = м.

 

В задаче максимизации eg -С 0, т. е. М 0, следовательно, отрицательными будут симплекс-разности Ai и A3, причем A3 > Ai. Вектор A3 имеет две положительные координаты и, следовательно, может быть ведущим (разрешающим), т. е. будет вводиться в базис. Последний столбец в таблице — вектор в — составлен из отношений координат вектора An к соответствующим координатам ведуъ      (   4 8 1\ „ щего вектора А2, т. е. vn = I — —; —;  . Поскольку отрицательные

V   1 3 Ь)

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

Переход к новому опорному решению осуществляется методом исключения Жордана—Гаусса. Перерасчет элементов матрицы А = = {A3, Ai, ..., А7} осуществляется так, чтобы на месте вновь введенного столбца A3 получился единичный вектор с единицей на третьей позиции (г = 3). Для этого все элементы ведущей строки делят на

26

ведущий элемент Жзз и на его месте получают "1". Остальные элементы в ведущем векторе-столбце исключают, т. е. за счет подходящего умножения ведущей строки и сложения с соответствующими строками получают "О" на всех позициях, кроме третьей. Например, чтобы исключить элемент жіз = — 1, первую строку складывают с третьей (ведущей) без дополнительного умножения, так как — 1 + 1 = 0, а чтобы исключить элемент Ж23 = 3, ведущую строку предварительно умножают на (—3). Как отмечалось, этот процесс представляется основными формулами симплекс-метода:

X'rj =ЄІ=^і к^ Г>

Xrs

Xfcj — Xfcj — OjXfcg.

Для вычисления симплекс-разностей также можно использовать подобную формулу, а именно:

д; = д,-^д..

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

 

 

 

Л»

Ба-

сбаз

Ао

2

-1

3

2

0

0

0

в

п/п

зис

А

А

Аз

A4

А*,

Ав

А7

1

2

3

А А7 А3

2 0

3

21/5 37/5 1/5

11/5 17/5 1/5

16/5 56/5 -2/5

0 0

1

7/5 14/5 -3/5

1 0 0

1/5 3/5 -1/5

0 1 0

 

 

 

 

 

 

 

 

 

 

 

 

 

27

Модифицированный симплекс-метод

При решении ЗЛП на ЭВМ (а это, как правило, задачи большой размерности) существенным является количество вычислений на каждой итерации, поскольку это сказывается на экономии памяти, времени и точности вычислений.

Анализ симплекс-метода показал, что для вычисления оценок Aj не требуется пересчета всей матрицы А = {An, А\,..., Ап}. Установлено, что А^ (I — номер итерации) можно вычислить так:

Af = (г,-».,.,!}") Г; = (сбаз.В-ЧО^і) -Cj = («(Mi)

З'

где Сбаз = (cji, • • • ,cim) — коэффициенты целевой функции при базисных переменных (третий столбец симплекс-таблицы); «О = = («д,..., щт) = Сбаз-В_1(0Координаты иц вектора называются симплекс-множителями.

Кроме того, существуют простые формулы перехода от В-1(1) к В_1{1 + 1), т. е. от обратной к базисной матрице 1-й итерации к матрице ß_1(l+ 1), обратной к базисной матрице (1+ 1)-й итерации. Это известные формулы прямоугольника (метод Жордана—Гаусса)

ь(г+і) (*)

г = k.

Алгоритм модифицированного симплекс-метода

1. Вычисляем симплекс-разность Aj = «А,—Cj, где и = с^В^1 — вектор симплекс-множителей; В^1 — матрица, обратная к базисной. Если Aj > 0, j = 1,те, то конец вычислений. Базисное решение оптимально. Если существует j такое, что Aj < 0, то переходим к следующему шагу.

2. Выбираем к такое, что Aj, < 0 (обычно наименьшее). Вычисляем новые векторы as = B^AS и ß = В^Ь. Если вектор не имеет положительных компонент, т. е. аи < 0, то конец вычислений. Целевая функция не ограничена сверху на допустимом множестве. Если существуют і такие, что ацс > 0, то переходим к следующему-шагу.

28

3. Вычисляем в = ßi/ctik для всех оцк > 0 и среди них выбираем минимальное. Пусть это в, стоящее на r-м месте. Вектор Аа вводится в базис, а вектор Аг выводится из базиса. Матрицу на 1-й итерации вычисляем по матрице — 1) (на предыдущей итерации) по формулам (*) "правила прямоугольника". Для канонической ЗЛП В-1(0) = Е — единичная матрица.

Теория двойственности и двойственные оценки линейных оптимизационных моделей

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

Aj

«2

2J

dr.

mj \    Ъ J

где ay — количество г-го ресурса, затрачиваемого при единичной интенсивности данной технологии; <у — количество получаемой при этом продукции.

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

Запишем математическую модель данной задачи. Пусть х\, х2, ■ ■ ■ ... ,хп — искомые интенсивности. Будем считать, что затраты ресурсов и объем выпуска готовой продукции пропорциональны соответствующей интенсивности. Тогда общее количество продукции выразится суммой

С\Х\ + СчХч +----Ь спхп,

29

а используемый в различных технологиях г-й ресурс не должен превышать имеющиеся запасы bj, т. е. для всех і = 1,2,... , тег должно выполняться неравенство

ацХ\ + а,2ж2 + • • • + аіпхп < Ь,.

Все Xj (j = 1,2,..., те) в соответствии с их смыслом неотрицательны, т. е. Xj > 0, j = 1,те. Таким образом, получается ЗЛП:

С\Х\ +   С2Х2 + ■ ■ ■ +   спхп —¥ max, ацХі + аі2Х2 + ••• + alnxn < bi,

Ü2\Xi +  (I22X2 + ••• +  (І2пХп   < Ь2,

amlX! + am2X2 + ■ ■ ■ + amnxn < bm, Xj>0,   j = 1,2,..., те.

Чтобы объективно соизмерить общие затраты с результатом, необходимо определить удельные оценки у і (г = l,m) всех задействованных в производстве ресурсов. Тоща функция

hyi + b2y2 Н-----h bmym

есть суммарная оценка всех ресурсов в тех их количествах Ь\, Ь2, • • • ... ,Ьт, которые есть на предприятии.

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

«иуі + «21 г/2 + ••• + ат1ут > сі,

«122/1 + «22У2 + • • • + ат2Ут > с2,

«іпУі + а2пХ2 + • • • + атпут > сп.

Здесь используется знак ">", поскольку стоимость произведенного продукта Cj не может превышать его производственные затраты: нел

 

 ...  4



Обратная связь

По любым вопросам и предложениям

Имя и фамилия*

Е-меил

Сообщение*

↑ наверх