3 часть (1081356), страница 54
Текст из файла (страница 54)
374 Гл. 17. Методы оптимизации Считая дополнительные персменые хг, .... х1 о базисными. запиш< и симплекс-табдицу этой задачи, соответствующую угловой точке х~о~ = = (О; 0; 0; 0; 0; 0; 20; 50; ЗО; 60): Любой столбец этой симплекс-таблицы может быть выбран в качестве разрешающего, так как элементы ес последней строки отрицательны.
Выберем, например, столбец, соответствующий свободной переменной хж Тогда разрешающим будет элемент этого столбца, стоящий в первой строке, так как пцп(20/1, 60/1) = 20/1. Производя преобразования симплекс-метода, получим такую последовательность симплекс-таблиц (рамками обведены разрешавшие элементы)'): В нижней строке последней симплекс-таблицы нет отрицатсльныт элементов, а в правом нижнем углу стоит нуль. Следовательно, л~иниыум з ) Столбец симпдекс-таблнцы, соответствующий вспомогательной переменной х„ен вводимой в свободные на каждом шаге метода искусственного базиса, удобнее вычеркивать на данном шаге вместо того, чтобы исалючить такие столбцы одновременно в окончательной симппекс-таблице.
'3 3. Линейное программирование = 0 вспомогательной целевой функции достигнут и 375 хрб = (О; 40; 0; 20; 10; 30) (30) Отметим, что другие варианты выбора разрешающих элементов в Ходе реализации метода искусственного базиса могли привести к другим угловым точкам допустимого множества У исходной задачи. Использование х® из (30) в качестве начальной угловой точки симплекс-метода в рассматриваемой задаче иллюстрирует решение примера 6.
Решить задачи линейного программирования 17.213-17.225 симплекс-методом, находя начальную угловую точку методом ис- кусственного базиса: 17.213. у(зс) = — 3х1+ 2хз — 2хз + 2х4 — хз — + ш1п, хг+ хе — хз = 1, — хе + хз + х4 = 1, хз+ хз+ хз = 2 ху>0, 4=1,...,5. 17.214. Дх) = — бхг — 8хз+ хз+ Зхз -4 ш1п, 2х! + 5хт+хз + 2х4 = 20, 12х4 + 6хз + 2хз + х4 = 72, х > О, у = 1, ..., 4. 17.215. у'(х) = — хг — 4х4 -+ ппп, — хг — 2хз + 2хз + х4 + 5хз = 13) — 2х1+ 2хз+4х4+ха = 5, хг — хе+ хз — х4+ 2хз = 5, х, > 0,,4 = 1, ..., 5. есть угловая то ша допустимого множества У исходной задачи линейного программирования нз примера 5. Заменив нижнюю строку последней симплекс-таблицы на строку коэффициентов целевой функции исходной задачи, получим симплекс-табдицу этой задачи, соответствующую угловой точке хбй из (30): 376 Гл. 17.
Методы оптимизации 17.216. у'(х) = 34х1 + х2 + Зхз — Зхз -+ 1шп, ЗХ1 — 2хз + Зхз + 2Х4 = 9, Х1+ 222 — хз + х4 = О, — х1 — Х2+2хз+Х4 = 6, ху > О, у = 1, ..., 4. 17.217. ~(х) = — Х1 + 2Х2 + 2хз — х4 -+ ппп, Х1 + хз + хз + х4 = 7, — ЗХ1 + Х2 + 2хз + х4 = 6, 2х1 + х2 + хз — х4 = 2, х > О, 2 = 1, ..., 4. 17.218. ~(х) = -Зх1+ хз — 2х,1 — 1 1п1п, 15х1+ 222 — Зхз — 7х1+ хз = 4, 2х1+ х2+ хз — 2Х4 = 3, хз + 5х4 + 2хз = 7, х,>0, 2=1,,5. 17.219. Дх) = — хз -+ 1шп, Х1+ т2 3 1~ — Х1+х2 > — 1, 2Х1 — Х2 > О, х1, т2>0.
17.220. Дх) = Зх1 — 2х2 + хз -1 ппп, Зх1+ Х2 — 2хз = 2, 4Х1+ Зхз+ 2хз —— 1, х > О, у = 1, 2, 3. 17.221. у (х) = — 2х1 + х2 — хз + хз — 1 ппп, — 2х2+х4+ха = — 3, хз — 2х4 = 2, Х1+ЗХ2 Х4 ~~А х1+х2 > — 3, х > О, у = 1, ..., 5. 17.222. у(х) = — 8Х1 — 2Х2+ 5хз — 15Х4 — 1 гшп, — х1 + Зтг + хз + 10Х4 ( 25, 2Х1 + х2+ хз + 5х4 ( 10, 10х1 + 2х2 + 2хз — 5х4 ( 26, х > О, у = 1, ..., 4. 17.223. Предприятие, располагающее ресурсами сырья трех ви- дов В,, 1 = 1, 2, 3, может производить продукцию четырех видов Ат, у = 1, ..., 4.
В таблице З.б указаны затраты ресурсов В, на изготовление 1 т продукции А, объем ресурсов и прибыль, полу- чаемая от изготовления 1 т продукции А . 3 3. Линейное программирование 377 Таблица З.б Определить ассортимент выпускаемой продукции, при котором полученная прибыль будет максимальной, при условиях: а) продукции Ат необходимо выпустить не менее 8 т, продукции А4 — не более 5 т, а продукции А~ и Аз — в отношении 2:1; б) производственные издержки на 1 т продукции А, у = 1, ..., ..., 4, составляют соответственно 3, 9, 12 и 6 руб., а суммарные издержки не должны превышать 87 руб. 17.224.
Завод получает 4 вида полуфабрикатов В; в количествах: В~ — 400 т, Ве — 250 т, Вз — 350 т и Ва — 100 т. В результате смешения зтих компонентов получают 3 вида продукции Аа. Пропорции смешиваемых полуфабрикатов следующие: для А~ — 2:3:5:2, для Ат — 3:1:2:1, для Аз — 2:2:1:3. Стоимость 1 т продукции А составляет: А~ — 12 руб., Аз — 10 руб., Аз— 15 руб, Составить оптимальный план выпуска продукции по критерию: а) максимальной стоимости выпущенной продукции; б) максимального использования полуфабрикатов. 17.225. Решить задачу 17.186 об оптимальном графике работы автобусного парка при следующих исходных данных; 3. Целочисленное линейное программирование.
Во многих случаях на допустимое множество задачи линейного программирования (ЗН5) накладывается дополнительное требование целочисленности переменных Если атому требованию должны удовлетворять все переменные, то Гл. 17. Методы оптимизации получаем полностью целочисленную задачу линейного программированил, которая в каноническом виде записывается следующим образом; у(х) = ~~ с.х — ! ш)п, о=1 Е анх, =6я 1=1, ..., т, хз>0, ,1=1,...,п, (31) хзЕУ, где У вЂ” множество целых чисел. Полностью целочисленную задачу с двумя переменными можно решить графически, учитывая, что допустимое множество Сг этой задачи состоит из точек целочисленной координатной сетки, принадлежаших допустимому множеству У задачи линейного программирования без дополнительного требования (31).
Решить полностью целочисленные задачи линейного программирования 17.226-17.234 графическим методом: 17.226. Дх) = х! — 20хт — > ш(п, — х! + 10хз ( 40, 4х! + 2хэ < 29, хз >О, хзЕК, 5=1,2. З На плоскости (хм х ) построим допустимое множество У рассматриваемой задачи линейного программирования без требования целочисленности (многоугольник АВСВ на рис. 35) и отметим точки множества У с целочисленными координатами. Совокупность этих точек представляет собой допустимое множество О полностью целочисленной задачи. Перемешал линию уровня целевой функции у(х) в направлении е = ( — 1, 20) убывания у(х), находим крайнее положел ! 2 3 4 5 б 7 "~ ние этой линии, в котором она ешс имеет непустое пересечение с множеством О. В этом положении линия уровня проходит через точку В(0, 4), поэтому решение задачи имеет вид х' = (О, 4), у' = пцп у(х) = — 80.
й Отметим, что, как видно из рис. 35, точкой минимума у(х) в данной задаче без требования целочисленности является точка С(5; 4,5), 9 3, Линейное программирование 379 т.с. х' = (5; 4,5), у' = пинах) = — 85. Отсюда следует, что точкой и минимума целевой функции на допустимом множестве О целочисленной задачи не обязательно является ближайшая к решсншо х' обычной (нсцслочисленной) задачи точка множсства У с целочисленными координатами. С 17.227. Дх) = -х1 — хг -+ шш, 2х1 + Зхг < 36, х1 < 13, Зх1+ хг > 6, х. > О, ху Е 7, .7 = 1, 2.
17.228. )'(х) = — 9г1 — 11хг — ~ шш 4х~ + Зхг < 10, х1+2хг ((8, х,>0, х,ЕЕ, у=1,2. 17.229. Дх) = -4х1 — Зхг -+ пт1п, 4х1+ хг ( 10, 2х~ + Зхг < 8, ху>0, х,бК,7=1,2. 17.230. ('(х) = — т1 — хг -+ пцп, 2х~ + Зхг (5, х1<2, т >О, х,ЕК, у=1.,2. 17.231. у(х) = хг — хз — ~ нйп, Зхг+7:3+х.1 =3, х1 — 2хг+ха = 1, т >О, х ЕК, у=1,2. 17.232. Дх) = — хг — > шш, Зх1+ хг+.тз = 12, - 8х| + Зхг + х4 = 24, х >О, т, бК, у=1,2. 17.233.
В цехе плошадьк> 74 мг необходимо установить станки, на приобретение которых отпушено 42 тыс. руб. Сушествует два типа станков. Станок первого типа стоимостью 6 тыс. руб., требуюший 12 мг производственных плошадей, обеспе- чивает изготовление 70 изделий в смену. Аналогичные характери- стики станка второго типа составляют соответственно 4 тыс, руб., 6 мг, 40 изделий в смену. Найти оптимальный вариант приобретения станков, обсспсчи- ванлций максимальное производство изделий в цехе.
17.234. Решить задачу 17.182 об оптимальном составе сплава, предполагая, что сырье каждого вида приобретается в количествах, кратных 1 кг. 380 Гл. 17. Методы оптимизации Длп решения полностью целочисленных задач линейного программирования г произвольным числом переменных использустс~ жегпод Гозеори. Он состоит в последовательном отсечении от попу.стимого множества СГ нсцслочисленной задачи частей, нс сод< р"каших точек с цслымп координатами. Эти отсечения производится включением в задачу дополнительных ограничений на персменныс х . Опишем алгоритм метода Гомори, использующий симплекс-метод.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
