3 часть (1081356), страница 51
Текст из файла (страница 51)
т=! Таким образом, математическое описание задачи об оптимальном составе сплава принимает вид у(х) = ~ с,х, -+ шш !=1 а„.х, < 6н Е у=! в а!ух >11, (г=1,...,н!), (7) (8) ху = бо, (9) о„х, +хв, — — 6„ Е !=! обх; — хвевьы = А Е т=! (!=1,.,.,ш), = бо, т=! х, > О, у = 1, ..., н + 2гп. с т=! х, ) О, у = 1, ...,и. Запишем эту задачу линейного программирования в каноническом виде. Среди ограничений (7)-(9) на переменные х содержится 2т неравенств (7), (8). Для преобразования пх в ограничении-равснства введем 2т дополнительных неотрицательных переменных хв.ь! и х„ьв,.~!, т=1, ..., ш.
Прибавив переменные х„„, и левым частям соответствующих неравенств (7) и вычтл переменные хьч ь, из левых частей неравенств (8), получим задачу линейного программирования в каноническом виде ~а у(х) = у с,х -+ шш, т=! 356 Пл. 17. Методы оптимизации Составить математическое описание задач оптимизации 17.182-17.187, представив полученные задачи линейного программировании в каноническом виде: 17.182. Для изготовлении сплава из меди, олова и пинка в качестве сырья используют два сплава тех же металлов, отличающиеся составом и стоимостью.
Данные от этих сплавах приведены в таблице ЗА. Таблипа ЗД Получаемый сплав должен содержать не более 2 кг меди, не менее 3 кг олова, а содержание цинка может составлять от 7,2 до 12,8 кг. Определить количества х, 2 = 1, 2, сплавов каждого вида, обеспечивающие получение нового сплава с минимальными затратами на сырье.
17.183*. Длл изготовления двух видов изделий А~ и А2 завод использует в качестве сырья алюминий и медь. На изготовлении изделий заниты токарные и фрезерные станки. Исходные данные задачи приведены в таблице 3.2. Таба и па 3.2 Определить количества х, з = 1, 2, изделий А, которые необходимо изготовить для достижения максимальной прибыли. 17.184. Из одного города в другой ежедневно отправляютсл пассажирские и скорые поезда.
В таблице 3.3 указаны: состав поезда '3 3. Линейное программирование 357 каждого типа, количество имеющихсн в парке вагонов различных видов для формировании поездов и максимальное число пассажиров, на которое рассчитан вагон каждого вида. Табл и па 3.3 Определить число скорых хс и пассажирских хт поездов, которые необходимо формировать ежедневно из имеюшегосн парка вагонов, чтобы число перевозимых пассажиров было максимальным. 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) не имеет решения, так как ее допустимое множество Г пусто. Выберем произвольный базисный минор матрицы А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
