341_3- Сборник задач по математике для втузов. В 4-х ч. Ч.3_ (ред) Ефимов А.В, Поспелов А.С_2002 -576с (987779), страница 50
Текст из файла (страница 50)
17.185. Завод производит продукцию двух видов Ас н Аж используя сырье. запас которого составлнет 5 т. Согласно плану выпуск продукции Ас должен составлять не менее 60% общего объема выпуска. Расход сырья на изготовление 1 т продукции Ас н Аэ составляет соответственно оч и аэ т. Стоимость 1 т продукции Ас н Аэ составляет соответственно сс руб. и ст руб. Определить план выпуска продукции Ас и Аэ, при котором стоимость выпущенной продукции будет максимальной. 17.186.
В начале рабочего днн автобусного парка на линию выходит хс автобусов, через час к ним добавляетсн хт автобусов, еще через час †- дополнительно хэ машин. 11аждый автобус работает на маршруте непрерывно в течение 8 часов. Минимально необходимое число машин на линии в 1-й час рабочего дня (г =- 1, 2, ..., 10) равно бо Превышение этого числа приводит к дополнительным издержкам в течение 1-го часа в размере с, руб. на каждый дополнительный автобус. Определить количества машин хм хт, хз, выходящих на маршрут в первые часы рабочего днн, с таким расчетом, чтобы дополнительные издерлщи в течение всего рабочего днн были минимальными.
17.187. Процесс изготовления изделий двух видов состоит в последовательной обработке каждого из них на трех станках. Время использования 1-го станка составляет бс часов в сутки, 1 = 1, 2, 3. Время обработки каждого изделия у'-го вида, у = 1., 2, на 1-м станке равно а; часам. Прибыль от реализации одного изделия у-го вида составляет с руб.
Составить план суточного впуска изделий так, чтобы прибыль от нх производства была максимальной. Гл. 17. Методы оптимизации 358 Если задача линейного программирования содс1нкит только две переменные, и в ее условии нет ограничений-равенств (1), то такую задачу можно исследовать и решить графически.
Рассмотрим задачу (10) .г (Х) = С~ У! + СТХТ вЂ” а Шщ ггг!хг + йгтхэ ( Ьга 1 = 1,, гй (11) хг >О, хт >О. (12) На плоскости (хы хт) любое из неравенств (11) определяет полуплогкостьг лсждшую по Одн1 из сторон От прлыой йа1Уг+йгтхэ Ьг. Длй тогг! чтобы определить расположение этой полуплоскости относительно граничной прямой, можно подставить координаты какой-лнбо точки (при Ь; ф 0 проще всего взять начало координат) в соответствуюшес неравенство (11) и проверить сто выполнение. Таким образом, допустимое множество (г' задачи (10) — (12) являем л пересечением первого квадранта хг > О, хт > 0 и полуплоскостей, со- а Ь Рис.
29 Рвс, 30 ответствующих неравенствам (11). Поэтому множество (Г представляет собой либо: а) пустое множество, тогда задача (10) — (12) нс имеет решений из-за несовмсстности ограничений (11), (12); б) многоугольнин (рис. 29); в) неограниченное многоугольнос множество (рис. 30). Для рсшенин задачи (10) — (12) в случае [l ф гЗ рассмотрим семейство линий уровня функции у(х) из (10) сгхг + сэхт —— Са С = сопас, (13) которые являются параллельными прнмымп.
Антиградиент — Г'(х) = = ( — сы — ст) = е перпендикулярен прямым (13) и указывает направление убывания г"(х). Если перемещать параллельно самой себе произвольную прнмую (13), протодлшую через допустимое множество (г', в направлении е убывания г'(х) до тех пор, пока зта прлмая будет иметь 3 3. Линейное программирование 359 хотя бы одну общую точку с множеством У, то в своем крайнем положении указанная прямая пройдет через точку множества У, в которой деловая функция у(х) принимает минимальное на У значение. Пример 2. Используя графический метод, найти решение следующей задачи линейного программирования: Дх) = — Зх! — 2хт — ! !п1п, х! + 2хг < 7, 2хг+ ха < 8, ха<3.
а Изобразим на плоскости (х!, хз) допустимое мнох!ество У наиной задачи (многоугольник АВС11Е) и одну из линий уровня — Зх! — 2хз = С целевой функции (рис. 31). Направление убывания у(х) указывает вектор е = (3, 2). Совершая параллельный перенос линии уровня вдоль направления е, находим ес крайнее положение. В атом положении при~а~ — Зх! — 2хт — — С проходит через вершину Р(3, 2) многоугольника АВС11Е.
Позтому целевая функция у(х) принимает минимальное значение у' в точке х* = (3, 2), причем у'* = у(3, 2) = — 13. с А Задача линейного программирования (10)-(12) может иметь н бесконечное мно- -Зх!-2х,=С жество решений. Пример 3. Решить задачу линейного программирования с целевой функцией г" (х) = — х! — 2хз н ограничениями на допустимое множество У, взятыми из примера 2.
0 Множество (7 построено при решении примера 2. На рис. 32 изображена линия уровня — х! — 2хт — — С целевой функции у(х). В своем крайнем положении при параллельном переносе вдоль направления е = (1, 2) она содержит сторону СЕ многоугольника АБСОЕ. Таким образом, все точки отрезка Сь! являются точками минимума фунвции у(х) на множестве У. Так как концы С и 11 зтого отрезка имеют координаты (1, 3) и (3, 2) соответственно, то любая точка минимума у(х) представима в виде х" = с!(1, 3) + (1 — п)(3, 2) = (3 — 2сг, 2+ а), где сг б [О; Ц. Минимальное значение целевой функции !' = 7(х*) = -7. В случае неограниченного допустимого множества У задача линейного программирования (10)- (12) может не иметь решения, так как целевая функция на таком множестве может быть не ограниченной снизу.
Пример 4. Решить графическим методом задачу линейного программирования Дх) = — х! — 2хт — ! пнп, х! +хг Э1, 2х! — хт > -1, х! — 2хг < О, х!, хт ) О. Гл. 17. Методы оптимизации 360 а Допустимое множество У данной задачи представляет собой неограниченное многоугольное множество (рис. 33). Функция у(х) убывает 4 -х -гхе=С ! Рис, ЗЗ Рис. 32 в направлении е = (1, 2).
При параллельном переносе линии уровня — х1 — 2хг = С вдоль направления е она всегда пересекает множество У, а целевая функция у(х) неограниченно убывает. Позтому рассмотренная задача не имеет решений. 1> Решить задачи линейного программирования 17.188-17.200 графическим методом: 17.188. У(х) = х1 — 2тг -+ пцп, — х1+тг <О, 2х1+ тг < 3, х1 — хг < 1, х1, т2 > О.
17.189. )'(х) = — х1 — Зх2 — 1 ппп, 2х1+ хг < 2, х1 — хг >О, х1 — хг < 1, т1, х2 )~ О. 17.190. ~(х) = -2х1 — хг -1 ппп, 2х1+ хг > 1, Зхг — хг > — 1, х1 — 4х2 ~ ~2, х1, хг > О. 17.191. У(х) = — х1 — хг -+ пцп, х1 < 3, хг<2 х1+хг < 1, хг,хг >О. з 3. Линейное программирование 361 17.192. у" (х) = — х1 — 4хг — ~ пйп, хг <2, хг+2хг > 2, тг (2, х1+хг ( 3, хмхг>0. 17.193. Дх) = — х| — хг — > ппп, х! + х2 ~ Э1, х1 — хг > — 1, Х1 — х2 ~< 1, х1 ( 2, хг<2, хмхг>0. 17.194.
Дх) = — 2хг — хг — > ппп, х~ + 2хг > 2, 2х1 — хг > О, х1 — 2хг < О, т1 — тг > — 1, хмхг >О. 17.195. )'(х) = -х1 — хг -+ ппп, 2хг >1, х1+х2 ~< 3~ х1 < 2, хг (2, 2х1+ хг > 2, хмхг >О. 17.196. Решить задачу 17.182 об оптимальном составе сплава. 17.197. Найти оптимальный план выпуска продукции в задаче 17.183. 17.198. Определить число формируемых пассажирских и ско- рых поездов в задаче 17.184. 17.199.
Найти оптимальный план выпуска товаров в задаче 17,18еь полагая а1 = 2, аг — — 1, Ь = 390, с| = 200, сг = 300. 17.200. Решить задачу 17.187 со следующими исходными дан- ными: А=(а,)= 0,2 0,1, Ь= Ьг = 10 а) с1 = 65, сг = 80; б) с1 = 85, сг = 60. Графический метод используется также для решения задачи линейного программирования в каноническом виде (3)-(5) с произвольным числом переменных х,, если число свободных переменных системы уравнений (4) не превосходит двух.
Гл. 17. Методы оптимизация 362 У(х) = тг + Охг + 5хз + Зхз + 4хз + 14хв — > пцп, х~ +хз = 20, хг+ хз = 50, хз + хв — — ЗО, х4+хз+хв =60, х. >О, 1=1,...,6. < В данном случае матрица системы ограничений-равенств имеет вид Ее ранг т = 4 = пг, причем минор, образованный первыми четырьмя столбцами, может быть выбран в качестве базисного (проверьте!).
Число свободных переменных и — т = 2, поэтому для решения задачи можно использовать графический метод. Решив систему ограничений-равенств относительно базисных переменных х, у = 1, ..., 4, получим х~ = — 40+ха+ха, хг = 50 — хз, хз =30 — хв, тв —— 60 — хв — хв. (14) Пусть ранг г матрицы системы ограничений (4) (т.е. матрицы А из (6)) равен рангу расширенной матрицы (А(Ь) этой системы. В противном случае система (4) несовместна и задача линейного программирования (3)-(5) не имеет решения, так как ее допустимое множество Г пусто.
Выберем произвольный базисный минор матрицы А. Для определенности будем считать, что этот минор порядка г соответствует первым г столбпам и строкам матрицы А. Если т ( т, то уравнения (4) с номерами 1 = т + 1, ..., ш являются следствиями остальных уравнений и их следует опустить. Поэтому будем считать, что г = пг.
Предположим, что и — т = 2 или и — т = 1. Считая переменныс х, у = 1,..., га базисными, а остальные — свободными, решим систему (4), т.е. выразим базисные переменные через свободные, после чего исключим базисные переменные из условия задачи (3)-(5). Для этого полученные соотношения для базисных переменных подставим в выражение (3) целевой функции и запишем условие неотрицательности (5) для всех переменных. В результате полу ~им задачу линейного программирования вида (10)-(12), эквивалентную исходной задаче и содержащую только свободные переменные исходной задачи, а их число не превосходит двух. Для решения полученной задачи можно использовать графический метод.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
