краевая задача для системы обыкновенных дифференциальных уравнений, причем краевые условия задаются только для фазо­ вых переменных. Отсутствие краевых условий для функций существенно осложняет задачу. Ясно, что оптимальное управ­ ление и оптимальная траектория зависят от начального векто­ ра '?(/]), но, к сожалению, условия максимума для функции Н явно не указывают, как выбирать этот вектор. Численный поиск начального условия для Ч^/) можно организовывать, опираясь на условие 2 принципа максимума. Однако одного этого усло­ вия недостаточно, чтобы организовать сходящийся итерацион­ ный процесс последовательного уточнения вектора ЧЧ^).

Успех аналитического решения задачи, рассмотренной в примере, во многом объясняется тем, что система (6.32) ли­ нейна. Именно в линейных задачах проявляются преимущества принципа максимума.

6.2.4. Метод динамического программирования

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

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

В основе метода лежит сформулированный Р. Веллманом принцип оптимальности. Этот принцип верен для тех систем, последующее движение которых полностью определяется их

состоянием в текущий момент времени. К таким системам отно­ сятся, например, управляемые системы, т.е. системы, аналогич­ ные тем, для которых вводится принцип максимума.

Принцип оптимальности отражает важнейшие особенности задач оптимального управления. Его суть можно объяснять по-раз­ ному. Ввиду его важности приведем несколько формулировок.

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

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

Вторая формулировка. Оптимальное управление в любой момент времени не зависит от предыстории системы и опреде­ ляется только состоянием системы в этот момент и целью управления.

Еще один вариант принципа оптимальности дадим для за­ дачи оптимального управления с фиксированным временем и свободным правым концом. Пусть закон движения описывает­ ся автономной системой дифференциальных уравнений (6.25), причем заданы начальный t\ и конечный /2 моменты времени, а также начальное состояние x{t\) = х \ Целевой функционал оп­ ределим следующим образом:

(6.42)

Третья формулировка. Начиная с любого момента време­ ни V е [tu t{\, участок оптимальной траектории также является оптимальной траекторией.

Другими словами, каково бы ни было положение точки х*(/') на оптимальной фазовой траектории, ее участок от точки **(/') (участок 2 на рис. 6.10) тоже является оптимальной траекторией.

Что же касается участка 1 оптимальной траектории до точки **(/')> то можно утверждать, что

	этот участок			есть	оптимальная
	траектория,		когда точка дг*(/') - x f
	является фиксированной,					т.е. ко­
	гда по условию задачи допустимая
	траектория		обязательно			должна	Рис. 6.10. Иллюстрация
	проходить через точку х'. Если же
							метода динамического
	задана	только		начальная		точка
							программирования
	JC*0 I) -	JC1, то участок 1 оптималь­
							и свойств оптимальной
	ной траектории сам по себе может
							траектории
	и не быть оптимальной траекто­
	рией,	т.е. может не			доставлять

минимумцелевому функционалу в задаче со свободным пра­ вым концом.

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

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

дущем исправить уже нельзя.

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

П р и м е р 1. Задача об использовании оборудования. Рассмотрим простейший вариант дискретной задачи рас­

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

цип оптимальности. Производственно-экономический процесс

состоит в следующем. Некоторая начальная сумма денег s =*1 затрачивается на приобретение оборудования двух типов: А и В, с помощью которого организуется производство. Пусть на обо­ рудование типа А выделена сумма 0 < щ <*i, тогда за опреде­ ленное время его эксплуатации будет получен экономический эффект g{u\). Оставшаяся сумма х\ - щ пойдет на приобретение оборудования типа В, которое за тот же период времени даст экономический эффект h(x\ - щ). К концу срока эксплуатации

суммарный экономический эффект составит
R i( x h «О = g(wi) + h(X] - Ml)-	(6.43)

По истечении срока эксплуатации оборудование реализу­ ют, за оборудование типа А выручают сумму аии 0 < а < 1, а за оборудование типа В - сумму b(xi - Mi), 0 < Ъ< I. Этим заверша­ ется первый цикл производства. Вырученную от продажи обо­

рудования сумму
Х2 = ащ + b(x\ - Mi)	(6.44)

используют как стартовую для организации второго цикла про­ изводства. Из нее на оборудование типа А выделяется сумма О < М2 < Хг, а оставшаяся сумма х2- м2 идет на приобретение обо­ рудования типа В. Следующий цикл эксплуатации оборудования даст экономический эффект g(M2) + й(х2 - м2) и остаточную сум­ му хз = аи2 + Ъ(х2- м2) за проданное оборудование. Описанный цикл производства многократно повторяется.

Считая известными функции g(^), й(^) и постоянные а и Ь, найдем такую стратегию распределения средств при покупке обо­ рудования типов А и В, чтобы обеспечить наибольший экономиче­ ский эффект за фиксированное количество п производственных циклов. Другими словами, надо так выбрать значения Mt, ..., и„ в допустимых пределах, чтобы получить максимум величины

п
К (s, м,,м2,..., м„) = £ (g(uk) + h(xk - uk)),	(6.45)
*=1

гдех| =s,xm+i =aum + b(xm- u m), 0< um<xm, m= 1,2 , ...,«.

Мы пришли к дискретной задаче оптимального управле­ ния. Параметры мьм2,...,ып, которые нужно определить, решая задачу, есть управление, неравенства 0 < ит< хт, т = 1, 2, ..., п описывают область допустимого управления, а суммарная вели­ чина (6.45) есть целевой функционал. Отметим, что для плани­ рования процесса на к-м цикле необходимо знать лишь величи­ ну %к и число п —к оставшихся циклов. Процесс планирования впредыдущие циклы никак не влияет на планирование в текущем цикле, т.е. «история» процесса не имеет значения. Основной ин­ терес в этой задаче представляет не значение максимального экономического эффекта, а процедура его достижения, или, дру­ гими словами, оптимальная стратегия распределения средств.

Принцип оптимальности предполагает использование хо­ рошо известного приема, состоящего в планировании от конца к началу. Рассматривая последний и-й цикл, найдем значение оптимального управления и„ как функцию состояния процесса на начало этого цикла. Это позволит распределять средства на этом цикле в зависимости от их количества х„. Затем, используя оптимум последнего цикла, найдем оптимальную стратегию на двух последних циклах как функцию состояния процесса в начале предпоследнего цикла. Для этого достаточно найти величину м„_i как функцию х„-\. Процедуру повторяем для трех последних цик­ лов, четырех и так далее до тех пор, пока не охватим все циклы. На последнем шаге, найдя щ как функцию х, и зная фактическое значение хх = s, мы сможем вычислить всю серию значений щ, и2,

..., и,„ т.е. определить оптимальную стратегию.

Итак, на и-м цикле	в зависимости от хп максимальный
экономический эффект равен
rn(х ) =	max (g(w„) + Л(х„ - и„)),	(6.46)

а значение н*(х„), на котором достигается этот максимум, явля­ ется искомым оптимальным значением в зависимости от х„. Считая, что на последнем цикле и„ = и*„(х„) и достигаемый эко­ номический эффект равен г„(х„), ищем максимум r„..i(x„_i):

Найденный максимум г„-\(х„-]) и соответствующее значе­ ние 1, при котором он достигается, позволяют перейти к сле­ дующему этапу.

Продолжая продвигаться к началу процесса, мы на к-м ищем максимальный экономический эффект гт(хт), т = п - к + \ , за последние к производственных циклов в зависимости от средств х,„ на начало т-то цикла по формуле

гп_х(*_,) = max [g(ua) + h(xm- u m) +
о а д '	_	(6.48)
+rm+i(.aum+b(xm- u m) l	m = n - k + l, k = \,n.

Соотношение (6.48) - это рекуррентное соотношение Беллмана для рассматриваемой задачи. Оно сводит задачу оп­ тимизации на к последних циклах к оптимизации на первом из них с учетом уже найденной оптимизации на k - 1 последних циклах. Величина rrfxi) представляет собой суммарный эконо­ мический эффект за все п производственных циклов в зависимо­ сти от стартового значения xj. Задача отыскания максимума функции п переменных с очень сложной зависимостью свелась к п последовательным задачам поиска максимума функции од­ ного переменного.

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

С помощью перехода к дифференциальным соотношени­ ям можно показать, что функциональное уравнение Беллмана по существу эквивалентно уравнениям, вытекающим из принципа

максимума Понтрягина. Данное уравнение можно получить при замене интеграла в выражении (6.42) суммой, а дифференциаль­ ные уравнения (6.25) —уравнениями в конечных разностях.

	П р и м е р 2 . Задача о движении автомобиля.
	Пусть минимизируемый функ­
	ционал представляет		собой	время,		b,d	C,d В
	затрачиваемое на движение автомо­				27' 5 Т ,10! 2
	биля из пункта А в пункт В. Предпо­				,	6	5		2;
	лагается, что эти пункты соединены				9	4 S			6 9 3
	прямоугольной	сетью	дорог	(рис.	2		.	!
	6.11), причем	для каждого участка				3			4
	известно время движения в минутах,				10		3j		2 5	■а
					а	ь			----(
	указанное на рисунке цифрами. Для							с
					Рис. 6.11. Решение задачи
	простоты будем считать, что движе­
	ние осуществляется в три этапа, на				о движении автомобиля

каждом из которых автомобиль пе­ ремещается на следующую вертикальную полосу.

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

(с, d) =>В, h = 10 мин;

(с, d)=>(c, c)=>{d, с)=>В, /з = 7 мин;

(с, d)=>(c, с)=>(с, b)=>(d, b)=>(d, с)=>В, h = 23 мин; (с, d)=>(c, с)=>(с, b)=>(d, b)=>(d, с)=>В, t3 = 25 мин. Очевидно, оптимален второй вариант пути:

(с, d)=>(c, c)=>(d, с)=>В, h ~ l мин.

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

(с, с) : (с, с) => (d, с) =>В, h = 4 мин;

(c, b) : (с, b)=>(c, c)=>(d, c)=>B, t3= 10 мин;

(с, а) : (с, а)=>(с, b)=>(c, c)=>(d, с)=>В, (3 = 12 мин.

На предпоследнем этапе (этапе 2) осуществляется переход с вертикальной линии Ъ на линию с. Перед этим этапом автомо­ биль может находиться в любой точке вертикали Ъ. Если авто­ мобиль находится в точке (b, d), то попасть в точку вертикали с он может четырьмя путями:

(b, d) => (с, d) =>..., t2= 3, /2 + *з = Ю мин;

(b, d)=>(b, с)=>(с, с)=>... /2 = 10, /2 + 13 = 14 мин;

(b, d)=>(b, c)=>(b, b)=>(c, £)=>..., t2 = 24, /2 + /3 = 34 мин;

(b, d)=>(b, c)=>(b, b)=>(b, а)=>(с, а)=> ..., t2 = 21, /2 + *з= 33 мин.

Очевидно, оптимален ио суммарному времени t 2 + /3 пер­ вый путь:

(b, йО => (с, й() =>..., /2 = 3, /2 + /з = Ю мин.

Важно подчеркнуть, что расчет ведется лишь для текуще­ го этапа, так как оптимальные траектории для последнего этапа

уже определены.

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

(b, с) : (Ъ, с) =>(с, с) =>..., t2= 5, t2+ /3 = 9 мин;

(A, Z>) : (6, b)=>(b, а)=>(с, а)=> ..., (2 = 6, t 2 + /3 = 18 мин;

(Z>, а) : (6, а)=>(с, а)=> ..., /2 = 3, /2 + h = 15 мин.

Наконец, на первом (третьем с конца!) этапе автомобиль перемещается из точки А в одну из точек второй вертикали. Это можно сделать четырьмя способами:

Л=>(а, b)=>(a, с)=>(а, d)=>(b, d) =>..., t\ = 20, l%- 30 мин;

A=>(a, b)=>(a, c) =>(£, c)=> ..., t\ = 17, t%= 26 мин;

A=>(a, b)=>(b, b)=> ..., t \ = 6, /£ = 24 мин;

A=>(b, a)=> ..., t\ - 10, t z = 25 мин.

Легко видеть, что оптимальная траектория движения

(на рис. 6.11 показана пунктиром) представляется следующим образом:

4 =>(а, b)=>(b, b)->(c, а)=>(с, b)=>(c, c)=>(d, с)=>В.

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

6.2.5. Линейное программирование

Задачи линейного программирования были первыми под­ робно изученными задачами оптимизации при наличии ограни­ чений типа неравенств. Термин «линейное программирование» возник в результате неточного перевода английского «linear pro­ gramming». Одно из значений слова «programming» - составле­ ние планов, планирование. Следовательно, правильным перево­ дом этого термина было бы не «линейное программирование», а «линейное планирование», «планирование на основе линейных соотношений», что более точно отражает его содержание.

Будем рассматривать задачу максимизации линейной функции

f x ) = c'x'+cV +... + спхп = (с, х).

Эта функция не ограничена, и поэтому искать ее макси­ мум, не налагая никаких ограничений на область изменения

вектора х, бессмысленно.

Интерес представляет задача максимизации J[x) при усло­ вии, что х принадлежит некоторому множеству. Те из соответ­ ствующих задач, в которых область изменения х ~ многогран­ ник, т.е. выбор значений вектора х стеснен условиями типа ли­ нейных равенств и неравенств, составляют предмет линейного программирования.

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

fix)=clx l+ сУ +... + c V = (с, х)

(6.49)

на множестве значений х1,..., JC”, удовлетворяющих ограничени­ ям, в числе которых могут присутствовать только равенства и неравенства вида

аахх+ апх +... + а,У < Ъ'

ак\х]+ аих2 +... + а*У ^ Ък

(6.50)

ацх' + апх2 +... + а/пх" < У.

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

x!> Q ,j= \,...,p.

(6.51)

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

Целевую функцию J{x) = (с, х) принято называть критерием за­ дачи линейного программирования (иногда ее называют также функционалом задачи линейного программирования). Допусти­ мое решение, на котором линейная форма fix) принимает мак­ симальное значение, называется оптимальным решением или просто решением задачи.

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

1. Задача о выборе оптимального плана.

Допустим, что для создания некоторого продукта требует­ ся т видов ресурсов и можно использовать п способов (техноло­ гий) производства. Обозначим через % расход ресурса номера / при единичной интенсивности использования технологии номе-

Paj- '^ТУ интенсивность можно измерять, например, долей суток, в течение которой эксплуатируется данная технология. Одним из ресурсов в таком случае будет время. Через d обозначим ко­ личество производимой при этом продукции, и будем считать, что зависимость расходов и выпусков от интенсивностей линей­ на. Предположим далее, что производству выделено Ъ‘ единиц /-го ресурса, и обозначим через У интенсивность использования у-й технологии. Тогда под оптимизацией плана можно понимать поиск максимума объема выпуска продукции, равного

п

2 У У (6.52) У=1

при заданных расходах ресурсов:

ацх1+ апх2+... + ахУ < У

П21х'+ СГ22Х2 + ... + СЬ/У й У

(6.53)

ат\У+ ат2х2 +... + amnd' < Ьт

Интенсивности использования технологий по смыслу не­ отрицательны, т.е. переменные У должны подчиняться еще и

ограничениям:
У >0,у = 1, ...,и.	(6.54)

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

2. Транспортная задача.

Транспортная задача рассматривалась ранее в разделе 5, где отмечалось, что помимо использования сетевых моделей для ее решения могут быть применены другие методы.

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

найти наиболее экономичный способ перевозки продукта со складов к потребителям, если затраты на перевозку единицы продукта с /'-го склада в у-й пункт потребления равны Су. Обо­ значим через Ху количество продукта, перевозимое с /-го склада в 7-й пункт. Тогда задача минимизации транспортных расходов формулируется так: найти

	minZ	Z	ci/*!/	(6-55)
	/=1	7=1
при ограничениях
5Х £ а,. Yjx,j			bJ, Х у > 0.	(6.56)
J =1	/=1

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

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

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

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

В общем случае эта задача не является тривиальной. Сим­ плекс-метод предусматривает построение некоторого возмож-

262

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

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

			А х>с)=-2-х1- 3-х2		(6.57)
при трех ограничениях:
			2-х1 + Зле2 <18,
			х1- 4х2 < 4,		(6.58)
			- 2 -х1 + х2 < 2 .
Из рис. 6.12, ясно, что за­
дача имеет бесконечное множе­
ство оптимальных			решений,
расположенных		на	прямой
2х1+ Зх2= 18, причем W = -18.
Допустимое			множество
решений (см. рис. 6 .12) лежит
в заштрихованной		области, ог­
раниченной	тремя		прямыми	Рис. б. 12. Иллюстрация
и осями координат.
Для формального поиска				двумерной задачи линейного
оптимума	вводятся		дополни­	программирования

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

каноническому виду, добавив уравнение, содержащее функцию цели и заменив неравенства равенствами :

W+ 2 -х1 + 3х2 = 0,
2-х1+ Зх2 +х3= 18,	(6-59)
х‘ -4-х2 + х4 = 4,

-2-х' + х2+ х5 = 2.

Дополнительные свободные переменные удовлетворяют соотношениям:

х3 > 0, х4 > 0, х5 £ 0 . _

(6.60)

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

х1= 0,x2 = 0,xs = 18, JC4 = 4, JC5 = 2, W= 0.

(6.61)

Очевидно, это решение (на рис. 6.12 отмечено точкой с цифрой I) не относится к числу лучших, но может быть улуч­ шено при оптимизации. Отличные от нуля переменные х3, х4, х5 называют базисными переменными, переменные, равные нулю - х1, х2 - внебазисными.

Улучшение базисного плана может быть достигнуто за счет изменения (увеличения) внебазисных переменных. При этом увеличение на единицу переменной х1 приводит к умень­ шению W на 2 единицы, увеличение на единицу перемен­ ной х2 - к уменьшению W на 3 единицы.

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

Врассматриваемом случае обе переменные х1 и х2 входят

ввыражение для W с положительными коэффициентами, и зна­ чит, улучшение возможно. Однако увеличение х1 и х2 в силу ог­ раничений приводит к уменьшению других переменных (х3, х4, х5),

аони, в свою очередь, не должны быть меньше нуля. Порядок улучшения решения определяется симплекс-критерием II, кото­ рый требует выбора наиболее сильно влияющей на W перемен­ ной (в данном случае х2), определения ее максимально возмож­

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

В силу первого ограничения (2-я строка системы (6.69)) х2 не может быть больше 6, в силу третьего ограничения (4-я стро­ ка системы (6.69)) х не может быть больше 2 . Второе ограниче­ ние (3-я строка системы (6.69)), куда xj входит с отрицательным коэффициентом, при увеличении Х2 не действует. Это, кстати, очевидно из рис. 6.13. Таким образом, необходимо изменить значения х2и х5:

х2 = 2, х5 = 0

(6.62)

и включить х2 в базис вместо х5 Результаты первой итерации формализованы в табл. 6 .1.

Процедура замены базиса требует исключения новой ба­ зисной переменной х2 из выражения для W и преобразования ограничений.

Для этого четвертую строку системы (6.59) - действую­ щее ограничение на х2 - нужно умножить на 3 и вычесть из пер­ вой и второй строк системы, а потом умножить на 4 и прибавить к третьей строке системы:

W+ 8-х' +3х2-3 х 5 =-6,
8-х! + х3 -З х 5=12,	(6.63)
-7хх- 4-х2 + х4 + 4х5= 12,
-2-х1+ х2 + Xs = 2.

После преобразования новая базисная переменная хг вхо­ дит только в одну строку системы (6.73), эквивалентной исход­ ной системе (6.59). Новое базисное решение на рис. 6.12 показа­

но точкой с цифрой II:
х1 = 0, х2= 2,х3 = 12, х' = 12,х5= О, W = - 6.		(6.64)
Очевидно, оно	лучше исходного решения,	но по-

прежнему (в силу симплекс-критерия I) допускает улучшение за счет переменной х1. Переменная х1 в силу второй строки систе­

мы (6.63) не может быть больше —. Третья и четвертая строка

системы не накладывают ограничений на увеличение JC1 Поэто­ му необходимо включать в базис переменную х1вместо х3:

х' = | , х 3 = 0.

(6.65)

Результаты второй итерации формализованы в табл. 6.1. Преобразование системы (6.63) осуществляется так же,

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

W - x 3 = - 18,

X	I .		1	з 3	5	=	12	(6	.66)
	+ - х			— X			8
			8	8
7		3	,	4 , 1 1		5	180
----X			+ х	+ ---X = -----.
8				8			8

x>+ 2.x> + lxf = 2.

Новое базисное решение (точка 3 на рис. 6 .12)

х' = | , х 2 = 5,х3 = 0,х4 = у , х 5 = 0, W = -18

(6.67)

в силу симплекс-критерия I не допускает дальнейшего улучше­ ния (попытка увеличивать х3 приводит лишь к увеличению W) и, следовательно, является оптимальным. Оптимальная точка, разумеется, лежит на прямой 2х' + Зх2 = 18. Остается убедиться, что значения переменных (6.67) действительно удовлетворяют (6.57) и (6.58). Из рис. 6.12 видно, что поиск оптимума осущест­ вляется путем перебора вершин области возможных решений.

4. Изменяется базисное решение. Преобразуется сист ма уравнений задачи, после чего осуществляется переход к процедуре 2 .

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

В частности, в рассмотренном примере при первоначаль­ ном улучшении по переменной х 1будет получено равнозначное (6 .88) оптимальное решение (точка IV на рис. 6 .12).

J = ^ , х 2 = ™,х* = 0,х4‘=0,х* =		fT= -18.	(6 .68)
11	11	11

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

х х= - с о + — ( 1 - со) ; х 2 = 5 ш + — ( 1 - с о ) ; 0 < © < 1 . ( 6 . 6 9 )

2 11 11

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