3 часть (1081356), страница 55
Текст из файла (страница 55)
1. С полгошью симплекс-метола находится рсшенис х' задачи линейного программирования без учета требования целочислснности (31). Если длп х' условие (31) выполнпетсн, то задача решена. В противном случае среди чисел 11; последнего столбца симплекс-таблицы, определяющей решение х', есть такие, что ()у;) > 0 ). 2.
Среди нсцслых элегзентов,9, выбирастсп произвольнгпй элемент 11г (например, с лгаксимзльной дробной частью (11„)). По г-й строке симплекс-таблицы составллется дополнительное ограничение вида —. и Е (цгрхУ) < — ()У„) (здесь, кав и выше, длл опРеделенности мы э=т+1 полагаем, что свободные псрсмснныс ху имеют номера ги + 1, ..., и). С помощью вспомогательной переменной х„е1 > 0 это ограничение прсдставллетсл в виде Равенства хое1 — ~~ (о„,) = — (Р'„) и вводитсЯ в ~=п$.~-1 симплекс-таблицу дополнительной строкой (32) хп+1 вопч-П пге1 .. е"пан п~А~ь! где сгпчс, = -(ег„), у = т + 1,, .., и; )Упе1 = -(11„). Так как В„ь| — — — (О„) < О, то после дополнения строкой (32) симплекс-таблица перестает соответствовать допустимому базисному решению зада ш линейного программирования, которую она описывает.
3. Длп перехода к допустимому базисному решению производлтса следующие операции: а) строка с отрицательным свободным членом 1)ь считается разрешающей (на первом шаге, очевидно, /с = п + 1); б) если все коэффициенты аь, > О, то задача нс имеет решения, в противноле случае номер 1 разрешающего столбца находится из условия Р1 . Рэ шуп (аи( ьпь,<о )еть ! в) совершается преобразование симплекс-таблицы с опорным элементом ом.
Если в новой таблице по-прежнему есть хотя бы один отрицательный своболный член, то описанная процедура повторпстсп, начинал с операции а), необходимое число раз. 4) Напомним, что всякое действительное число а можно представить в виде а = (о) + (а), гпе (а) — целая часть числа а, э (а) = а — (а) — его цробпап часть. 3 3. Линейное программирование 381 Если все элементы Д вновь полученной симплекс-таблицы неотрицательны, то допустимое базисное рсшенис найдено. Отметим, что выбор опорного элемента аы гарантирует неотрицатсльность коэффициснтов рз новой симплекс-таблицы. Поэтому найденное допустимое базисное решснис является и оптимальным. 4. Если найденное в разделе 3 рсшенис задачи линейного программирования удовлетворяет условию целочислснности, то вычисления завершаются, а если нет, то продолжаются переходом к разделу 2 описания алго1штма.
Описанный алгоритм позволяет найти решение полностью целочисленной задачи линейного программирования, или установить отсутствие рсшений за конечное число итераций. Пример 8. Решить задачу 17.226 методом Гомори. < Введя дополнительныс переменные хз, хз > О, запишем эту задачу в каноническом виде: Дх) = х~ — 20хэ — ~ пцп, -х~ + 10хз + хз = 40 4х~ + 2хг + х4 = 29, х, >О, х,бУ,, у'=1,2. Отметим, что так как все коэффициенты ограничений-равенств данной задачи цслыс, то пелочисленность исходных переменных хм хэ влечет цслочисленность и дополнительных переменных хз, хз. Поэтому и после перехода к каноническому виду можно рассматривать данную задачу как полностью целочисленную и применить для ее решения метод Гомори.
Одна из угловых точек допустимого мнолкества нсцелочнсленной задачи очевидна: хф~ = (О, О, 40, 29). Запишем симплекс-таблицу для этой угловой точки; Решение нецелочисленной задачи находится за две итерации симп- лекс-метода; Гл. 17. Методы оптимизации 382 Это решение х* = (5, 9/2, О, О), /* = — 85 нс удовлетворяет условии> цслочнслснностн, поэтому дополняем последнюю симплекс-таблицу строкой (32): Длл перехода к допустимому базиснол>у решению находнт> разрешен>ший элемент по описанному правилу и преобрааусм симплекс-таб>л>щу: Послсдннп симплекс-таблица не только соответствует допустилгому базисному решению, но и дает решение рассматриваемой задачи: х* = =(О 4):Х*= — 80 Отметим, что дополнительное ограничение, введенное в симплскс- 2 4 1 таблицу, имеет вид — — хэ — — хэ < —, С помошьк> уравнений 42 42 2 хэ —— 40 + х> — 10хэ, х> —— 29 — 4х> — 2хэ перепишем сто для персмен- ныл х> и хт> хт ( 4.
Отсюда видно, что дополнительное ограничение соответствует отсечению от допустимого мнол.ества с> (многоугольника АВСВ на рнс. 35) части, годер>кашей топ>у х* = (5, 9/2) (вершину С этого многоугольника). С Решить полностью целочисленные задачи линейного програм- мирования 17.235- 17.250 методом Гомори: 17.235. /(х) = — х> + х4 — > ппп, — 2х> + хл+ ха = 1, х> +ха — 2хл = 2, х> + хэ + 3:г4 = 3, х >О, х еК, ум=1,...,5. 17.236. /(х) = — 2х> + 2хэ — Зхз + Зх4 — > гшп, х> — 2ха+х4 = 3, ха+ха — 2х4 = 5, Зхт + ха+,та = 4, х >О, х ЕК, ум=1,...,5.
3 3. Линейное программирование 383 17.237. Дх) = — х! + хз — хз + х4 †! пип, х! +2хз+хз = 8, х! +хг — х! =4, — х! + 2хг + хз + Зх! = 6, х, >О, х.ЕУ, у=1,...,4. 17.238. Дх) = — х! — хз — у пип, 2х! + хг + хз = 5, 2х! + Зхз + хз = 9, х >О, х ЕК,1=1.....,4. 17.239.
)'(х) = х! + 2хз + ха — у пиц, х! + хз + хз + х4 + хз = 5, хз + хз + х4 — хз = 2, хз — х! + хз — — 1, х >О х ЕК,у'=1 5 17.240. Дх) = — 4х! — Зхз -+ пип, 2х! + Зхг + хз = 8, 4х! + хз + х! = 10, ху > О, ху Е .'Е, у' = 1, ..., 4. 17.241. Дх) = — х! — хз -+ пип, х! + 2хз + хз = 6, Зх! + 2хз+х4 = 9, ху>0, хзЕЯ, У'=1,...,4.
17.242. Дх) = — хз -+ пип, — бхз+бхз+ха =б, 7хз — 4хз + х4 = 4, х! + хз + хз = 9, х >О, х ЕК,1!=1,...,5. Отметим, что переход к каноническому виду в полностью целочи- сленной задаче линейного программирования, содержащей ограничения- неравенства п а!!ху < Ь!, (33) у=! не приводит, вообще говоря, к полностью целочисленной задаче в каноническом виде, так как в преобразованных ограничениях (33) а„х + х„+! — — б; Е вспомогательные переменные х„ч.! не подчинены требованию целочисленности. Однако если всс козффициенты аоо б! в !33) — цслыс числа, то условие целочисленности монино распространить и на х„+!, как зто сделано при решении примера 8.
384 Гл. 17. Методы оптимизации Полностью целочисленную задачу в каноническом виде можно получить также, сели в (33) ао, Ь; — рациональные числа. Для этого следует умножить (33) на общее кратное знаменателей коэффициентов асн Ь, (т.с. перейти к целым коэффициентам в (33)) н лишь после этого ввести вспомогательные переменные х„ы. 17.243. Дх) = Зх1+ 2хг+ хз — 1 ппп, х1+Зх2+хз ~> 10, 2х1 + 4хз > 14 2хг+хз > 7, х >О, х Е.'Е, у'=1,2,3.
17.244. ~(х) = — 2х1 — хг — хз — 1 ппп, х1+ 2хг + 2хз = 16, х1+хг < 7, Зх~ + 2хз > 18, ху > О, хг Е Ж, у = 1, 2, 3, 17.245. У(х) = — 4х1 — Зхг — 1 ппп, 4х1+ хг < 44, х1 < 22, хг <18, х,>0, х,бК,у=1,2. 17.246. у (х) = х1+ 2хг + х — 1 1п1п, 1 1 2 х1+ х2+ хз ~ ~1~ 3 3 3 2х1+ хг > 1, 1 3 2 4 -хг+ -хз > 1, х >О, х ЕУ, 1=1,2,3. 17.247. ~(х) = — х1 — 2хг — Зхз 1 ппп, 2 1 25 Х1+ -хг+ -ХЗ < —, 3 2 6' 3 2 х1+ -хг + -хз <~ 3, 5 5 хг)~0, хуЕУ, 1=1,2,3. 17.248.
В цехе размещены 100 станков 1-го типа и 200 станков 2-го типа, на каждом из которых можно производить детали А1 и Аг. Производительность станков в сутки, стоимость 1 детали каждого вида и минимальный суточный план их выпуска пред- ставлены в таблице 3.7. 9 3.
Линейное программирооаняс 385 Таблица 3.7 Найти количества т,, станков г-го типа, 1 = 1, 2, которые нсобходимо выделить для производства деталей А, у = 1, 2, с таким расчетом, чтобы стоимость продукции, производимой в сутки, была максимальной. 17.249. Решить задачу 17.183, считая, что в результате усовершенствования технологического процесса расход меди на изготовление одного изделия Аз снизился с 50 до 40 кг. 17.250. Решить задачу 17.199 в прелположеени, что товары А| и Аз выпускакггся в количествах: а) кратных 1 кг; б) кратных 2 кг. Если требованию цслочислснности подчинены не все переменные задачи линейного программирования, то такая задача называется частпично целочисленной.
Для решения частично целочисленных задач также используется метод Гомори, но его алгоритм в этом случае отличается видом коэффициентов а„„к в дополнительной строке (32), а именно ч <ьи если а„> О, о„,к, = (д) ою, если о„< О, 1- У,) если переменная х. подчинена требованию целочислснности, и 1 — (о„у), если (а,у) < )11„), она ну = (73,) ()осу) — 1), если (а„у) ) (1Ц, — (77,) для х,, свободных от этого требования. Разумеется, вычисления заканчиваются, когда целыми являются нс обязательно все коэффициенты 71, симплекс-таблицы, а толька те, которым соответствуют переменные х„подчиненные требованию цслочисленности. Решить частично целочисленные задачи линейного программирования 17.251-17.256 методом Гомори: Гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
