341_3- Сборник задач по математике для втузов. В 4-х ч. Ч.3_ (ред) Ефимов А.В, Поспелов А.С_2002 -576с (987779), страница 53
Текст из файла (страница 53)
'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. Методы оптимизации Длп решения полностью целочисленных задач линейного программирования г произвольным числом переменных попользуется жегпод Гозеори.
Он состоит в последовательном отсечении от попу.стимого множества СГ нсцслочисленной задачи частей, нс сод< р"каших точек с цслымп координатами. Эти отсечения производится включением в задачу дополнительных ограничений на персменныс х . Опишем алгоритм метода Гомори, использующий симплекс-метод. 1. С полгошью симплекс-метола находится рсшенис х' задачи линейного программирования без учета требования целочислснности (31). Если длп х' условие (31) выполнпетсн, то задача решена. В противном случае среди чисел 11; последнего столбца симплекс-таблицы, определяющей решение х', есть такие, что ()у;) > 0 ). 2. Среди нсцслых элегзентов,9, выбирастсп произвольнгпй элемент 11г (например, с лгаксимзльной дробной частью (11„)).
По г-й строке симплекс-таблицы составллется дополнительное ограничение вида —. и Е (цгрхУ) < — ()У„) (здесь, кав и выше, длл опРеделенности мы э=т+1 полагаем, что свободные псрсмснныс ху имеют номера ги + 1, ..., и). С помощью вспомогательной переменной х„е1 > 0 это ограничение прсдставллетсл в виде Равенства хое1 — ~~ (о„,) = — (Р'„) и вводитсЯ в ~=п$.~-1 симплекс-таблицу дополнительной строкой (32) хп+1 вопч-П пге1 ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
