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

Число перебираемых допустимых базисных решений можно сокра­тить, если производить перебор не беспорядочно, а с учетом измене­ний линейной функции, т. е. добиваясь того, чтобы каждое следующее решение было «лучше» (или, по крайней мере, «не хуже»), чем предыду­щее, по значениям линейной функции (увеличение ее при отыскании максимума F , уменьшение — при отыскании минимума iv ).

Такой перебор позволяет сократить число шагов при отыскании оптимума. Поясним это на фактическом примере.

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

Рис 6.4. Многоугольник допустимых решений

Идея последовательного улучшения решения легла в основу уни­версального метода решения задач линейного программирования — Симплексного метода.

Симплекс (лат. simplex — простой) — простейший выпуклый мно­гогранник в 72-мерном пространстве сп+1 вершиной (например, тег-
раэдр в трехмерном пространстве); симплексом является также об­

Ласть допустимых решений неравенства вида <1.

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

Симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако еще в 1939 г. идеи метода были разра­ботаны российским ученым Л. В. Канторовичем.

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

Для реализации симплексного метода — последовательного улуч­шения решения — необходимо освоить три основных элемента:

Способ опрсде.%еН’1я какого-либо первоначсыъинго допустимого базисного решения задачи;

Правило ?Tepexoda к лучшему (точнее, не худшему) региению; критерий проверки оптимаъъиости найденного решения.

Для использования симплексного метода задача линейного про­граммирования должна быть приведена к каноническому виду, т. е. система о1раничений должна быть представлена в виде уравнений. Алгоритм конкретной вычислительной реализации этих элементов рассмотрим на примерах.

(6.53)

(6 54)

Алгоритм аналитического решения задачи линейного програм­мирования В качестве примера рассмотрим задачу об использова­нии ресурсов, сфюрмулированную в разд. 6.5.2. Решить симплексным методом задач)’:

F = 2х] + 3*2 —> max

При ограничениях:

Л-] + Зх2 < 18, 2х! + х2<16, Х2 <5. ‘5x^21,

Л*! >0, х2>0.

Решение. С помощью дополнительных неотрицательных перемен­ных перейдем к системе уравнений. В данном случае все дополни­тельные переменные вводятся со знаком плюс, так как все неравен­ства со знаком «<».

(6.55)

Получим систему ограничений в виде

+ 3*2 — 18,

2Xj + Хс) + =16,

Х2 + х5 = + х6 =21.

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

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

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

Шаг1. Основные переменные: ху х4, х5, х1у. Неосновные перемен­ные: X, Хг

Выразим основные неременные через неосновные:

Х3 = 18-Xj — Зл^, X/^ =16 2xj Х2,

(6.56)

Положив неосновные переменные равными нулю, т. е. х} = 0, х, = О, получим базисное решение Х{ = (0; 0; 18; 16; 5; 21), которое является
допустимым и соответствует вершине 0(0;0) многогранника OABCDE На рис. 6.5. Поскольку это решение допустимое, нельзя отбросить возможность того, что оно оптимально. Выразим линейную функцию через неосновные переменные: F= 2х{ + Ъхг При решении Х^ значе­ние функции равно F(X) = 0. Легко понять, что функцию F можно увеличить за счет увеличения любой из неосновных переменных, входящих в выражение для F с положительным коэффициентом.

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

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

Система (6.56) накладывает ограничения на рост переменной х*,. Поскольку необходимо сохранять допустимость решений, т. с. все переменные должны оставаться неотрицательными, должны выполняться следующие неравенства (при этом х{ = 0 как неоснов­ная переменная):

Х3 =18-3×2 >0, х4 =16-^2 >0,

= 5 — > 0, (6.57)

=21.

Откуда х2< 18/3; х2< 16/1; *2< 5/1.

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

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

Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) возможно, если не нарушается ни одна из полученных во всех уравнениях границ. В данном примере наи­большее возможное значение для переменной х2 определяется как Х2 = min {18/3; 16/1; 5/1; = 5. При х, = 5 переменная х5 обращается в нуль и переходит в неосновные.

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

Шаг II. Основные переменные: х , ху *4, хG. Неосновные перемен­ные: А’г X.

Выразим новые основные переменные через новые неосновные, начиная с разрешающего уравнения (его используем при записи вы­ражения для х<2):

Х<2 — 5 — Хг),

Хд = 18-xj -3(5-Х5),

Х4=16-2Х1-(5-Х5), (6.58)

Х^ —21 — 3xj

Или

[*3 = 3 — xj + Зх5 ],

«

Х4 =11-2х] +х5, (6.59)

Х() = 21-3xj.

Второе базисное решение Х2 = (0; 5; 3; 11; 0; 21) является допусти­мым и соответствует вершине А (I); 5) на рис. 6.5. Геометрическая интерпретация перехода от к Х^ — переход от вершины О к сосед­ней вершине А на многоугольнике решений OABCDE.

Выразив линейную функцию через неосновные переменные на этом шаге, получаем

F = 2xj +3х2 =2х1 + 3(5-Х5) = 15 + 2Х1 — ЗХ5.

Значение линейной функции F = F(X>) = 15. Изменение значения линейной функции легко определить заранее как произведение наи­большего возможного значения переменной, переводимой в основ­ные, на ее коэффициент в выражении для линейной функции; в дан­ном случае &F, =5-3=15, F = F + = 0+15 = 15. Однако значение F2 не является максимальным, так как, повторяя рассуждения шага I, обнаруживаем возможность дальнейшего увеличения линейной фун­кции за счет переменной х,, входящей в выражение для Fc положи­тельным коэффициентом. Система уравнений (6.59) определяет наи­большее возможное значение для Xj = min 3/1; 11 /2; 21/3} = 3. Второе уравнение является разрешающим, переменная х3 переходит в неосновные, при этом ДF2 = 3-2 = 6.

Шаг III. Основные переменные: х,, х?, х4, х(. Неосновные пере­менные: X., X,.

S Э

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

X] = 3 — х3 + ЗХ5»

Х~) = 5 — Х5,

(6.60)

[х4 = 5 + 2х3 — 5х5 ],

Х^ = 12 + Зх3 -9х5.

Базисное решение X = (3; 5; 0; 5; 0; 12) соответствует вершине В (3; 5) Выражаем линейную функцию через неосновные перемен­ные: F= 2х, + Зх2 = 2(3 — х^ + Зх.) + 3(5 — х.) = 21 — 2х, + Зх5, Fs = F{XJ = 21. Проверяем: F% — F., = 21 — 15 = 6 = ДF4. Третье допустимое базисное решение тоже не является оптимальным, поскольку при неосновной переменной х5 в выражении линейной функции через неосновные переменные содержится положительный коэффициент. Переводим х. в основную переменную. При определении наибольшего возмож­ного значения для х, следует обратить внимание на первое уравне­ние в системе (6.60). которое не дает ограничений на рост х., так как свободный член и коэффициент при хГ) имеют одинаковые знаки. Поэтому х = miii{oo; 5; 1; 12/9} = 1. Третье уравнение является разре­шающим, и переменная х4 переходит в неосновные; AF^ =1-3 = 3.

ШагIV. Основные переменные: х., х^., х6. Неосновные перемен­

Ные: X.., X..

5 -1

После преобразований получим

TOC o "1-3" h z А 1 3

5 5

, 2 1

Э 5

(6.61)

5

2 1

F О

3 9

Х6 =3—7*3+7*4- 5 5

Базисное решение Х} = (6; 4; 0; 0; 1; 3) соответствует вершине С (6; 4) на рис. 6.5.

Линейная функция, выраженная через неосновные переменные,

4 3

Имеет вид F = 24 —х3 — . Это выражение не содержит положитель-

5 5

Ных коэффициентов при неосновных переменных, поэтому значе­ние F4 = F(X4) = 24 максимальное. Функцию FНевозможно еще увели­чить, переходя к другому допустимому базисному решению, т. е. ре­шение Х4 оптимальное. Вспоминая экономический смысл всех пере­менных, можно сделать следующие выводы.

Прибыль предприятия принимает максимальное значение 24 руб. при реализации 6 единиц продукции 1 (х, = 6) и 4 единиц продукции Р2(*2 = 4). Дополнительные переменные хг х4, хг, х6 показывают раз­ницу между запасами ресурсов каждого вида и их потреблением, т. е. остатки ресурсов. При оптимальном плане производства х = х4 = О, т. е. остатки ресурсов. S, и S2 равны нулю, а остатки ресурсов 5 и S4 равны соответственно 1 и 3 единицам.

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

СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ УПАКОВОЧНОГО ПРОИЗВОДСТВА

Использование специализированных САПР в допечатной стадии производства упаковки

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

Математическое обеспечение подсистем машинной графики и геометрического моделирования

Изучение математического аппарата, лежащего в основе машин­ной графики и проектирования геометрии упаковки, начнем с рассмот­рения способов вывода и преобразования точек и линий. Эти спосо­бы наряду с соответствующими алгоритмами рисования используют­ся для изображения объектов или визуализации графической инфор­мации. Возможность проводить преобразования точек и линий явля­ется фундаментом машинной графики. Нарисованный объект может быть представлен в нужном масштабе, […]