Сдвижков О.Л. Математика на компьютере - Maple 8 (1185914), страница 19
Текст из файла (страница 19)
Вводим данные и находим объемы валовой продук)(ии отраслей: > А: еаггйх([[0.2,0.6,0.1), [0,0.2,0.4), [0.3,0.1,0.2]) ) г О .2 > у: =каггз.х ( [ [1000], [500], [800) ) ) Б1 > В:=Магх1х(3,3,зааре=зоеагзгу) Е:= 0 1 0 > ч1гп(11па10): > х: ви1г1р1у (аочехае (ечатл (к-А) ), у) ) 2857.187501 1773.437501 2296.875001 Глава И. Мвтвмвтичвскив модели в экономикв 3. Расчет матрицы (хз)) потоков средств: > И1 з =еча1аз (со1 (А, 1 ) *Х [1, 1) ) з М!: = [573.4375002, О., 860.1562503] > И2 з =еча1аз (со1 (А, 2) *Х [2, 1] ) з'..
М2: = [1 064. 062501, 354 6875002, 177.3437501! > ИЗ: =еча1аз (со1 (А, 3) *Х [3, 1] ) з МЗ: = [229.6875001,9187500004, 459.3750002) > хз=сопсаа(И1,И2,ИЗ) 573.4375002 1064.062501 229.6875001 О. 354.6875002 918.7500004 860.1 562503 177.3437501 459.3750002 4. Вычисления общих доходов отраслей: > к [1, 1] -ачаз(х [з., 1], з.=1 .. 3) з 1433.593751 > Х [2, 1] -ачга(х [з., 2], з.=1 .. 3) з 177.343750 > Х[3,1]-ащп(х[1,3],з 1..3); 689.062501 5.
Вывод матрицы коэффициентов полных затрат > 1пчесае(еча1аз(Е-А))з 1.562500000 !.276041667 .8333333333 3125000000 1.588541667 .8333333333 6250000000 .6770833333 1.666666667 Задача ([6[, 23). Предприятие выпускает три вида продукции в количестве, характеризующемся вектор-планом Х = (!0,7, 4). Для его изготовления используются 5 видов сырья.
Известна матрица А: где ам характеризует расход к-го вида сырья на 1 единицу [-го вида продукции. Наконец, вектор С = (7, 4,5,10,2) задает стоимость 1 единицы каждого вида сырья. Определить необходимое количество единиц сырья каждого вида для обеспечения плана, стоимость сырья для единицы каждого вида продукции и общую стоимость всего сырья для всей продукции. /7отоки в сетях Решение Ввод д З,9,2], [Ч,В,5,6,8], [Е,12 4 З 1)) ) А:= 4 8 5 6 > Х:=еаьсьх ( [ [1О], [7] [Ч] ] ) > С;=ваСгах( ( [7), [4], [З], [10], [2] ] ) ' 7 4 5 10 2 Необходимое количество сырья каждого вида: > еп1С1р1у(вгапврове(а),Х); 102 204 81 144 116 Стоимость сырья для единицы каждого вида продукции: > ви1ььр1у(а,о)' Общая стоимость сырья: > мо1с1р1у (ссапврове (Х), Ь); (36071 .
9 5. Потоки в сетях Пусть задана ориентированная 2-полюсная сеть, один полюс — вход, другой — выход, весовые коэффициенты дуг — максимальные пропускные способности дуг, Требуется определить максимальную пропускную способность сети. 766 Глава Ч!. Математические модели в экономике Геометрическое решение данной задачи основано на теореме Форда-Фалкерсона, согласно которой максимальная пропускная способность сети равна минимальной пропускной способности сечений сети. Аналитически задача решается сведением ее к задаче ЛП.
Рассмотрим сеть, представленную на рисунке: Рис. 6.7 Ыифры рядом с дугами — максимальные пропускные способности дуг, х,, х„х,, х„, х, — планируемые потоки в дугах. Аналитическая постановка задачи о максимальном потоке для данной сети имеет вид: х4 + хз -+ шах, при условиях О < х, < 3, О < х, < 1, О < х, < 1, О < х„ < 1, 0 ь х < 4, а также Х~ +Хз =Хо Хз =Хз +Хм так как входящие и выходящие потоки в каждом транзитном узле (С и Р) должны быть равны. Ее решение в Мар!е: > вахльхе(х4>х5, 10<=х1, х1<=1, 0<=х2, х2< 1, 0<=хз, хз<=1, 0<=х4, х4<=1, 0<=х5, х5<=4, х1+хз=х4, х2=хз+х5 Н; (хЗ = 0 х2 =1 хб =1 х4 =1 х! =1) Следовательно, максимальная пропускная способность сети равна 2. Задача ((1), 19.4), 1. Чему равен максимальный поток автомашин (количество машин в час) для системы автодорог, представленной на рис. 6.8.
2. Рассматривается возможность введения секции Е-Р, с пропускной способностью 3 тыс. автомашин в час. Насколько увеличится величина максимального потока автомашин? Решение. 1. Заданная сеть частично ориентирована. Необходимо перейти к ориентированной сети или к системе ориентированных сетей. На Участке С~) пропускная способность 2 тыс. автомашнн в час как в одну сторону так н в дру- Потоки в сетях Рис.
6.8 гую (двустороннее движение). Не нарушая общности решения, можно считать участок ориентированным от С к Р. Ориентация участков С-Е и Е-Г, как видно из числовых значений, представленных на схеме, на пропускную способность потока автомашин от А к В не влияет. Приходим к ориентированной сети Рис. 6.9 Ответ становится геометрически очевидным: б.
Сечение с минимальной пропускной способностью: СО, ВЕ, гВ. 2. Добавляем в предпоследней схеме дорог участок ЕО: Рис. 6ДО Глава И. Матаматичвскив модели в экономика 468 Вводим обозначения планируемых потоков автомашин хь х,, ...,кв х, на каждом нз участков схемы — АС, Аг, СР, РВ, АЕ, ЕВ, РВ, ЕР, СЕ, соответственно. Составляем н решаем задачу линейного программирования:: вахьв1ге (х4+хб+х7, (О< х1, х1<~4, О< х2, х2< 2, 0<=хЗ, хЗ<=2, О< х4, х4< 5, О< х5, х5< 3, О< хб, хб< 2, О< х7, х7<=2, 0<=х8, х8<=3, 0<=х9, х9< 1, х1=хЗ+х9,хЗ+х8 х4,х5+х9 хб+хз, х2=х7) ) г; (х4 = 4, хУ = 2 хб = 3 х2 = 2 хЗ = 2 хб = 2 х! = 3 хб = 2, хр =1) > зчьз(е,х4+хб+х8)г Ответ: 1) б; 2) 2.
5 6. Сетевое планирование Пусть задана ориентированная 2-полюсная (А, — вход, Ак — выход) сеть Б[Аь Аг, ..., А, ие], весовые коэффициенты ск дуг иа = А,.А,. которой являются длинами дуг, н требуется определить кратчайший путь нз Ат в А, Сопоставим ]б, 12] каждой дуге ит булеву (альтернатнвную) переменную Ь, е (0,1) н наложнм на переменные следующне условия. Для переменных, соответствующих дугам с началом А,: ~х;Ь(1,),) = 1.
Для переменных, соответствующих дугам с концом А„: ~~',Ь((„, Ф) =1. Для переменных, соответствующих дугам с началом нлн с концом в А» (К = =2, ...,А( — 1): ~Ь((к, К) = ~~',Ь(К, ( ). В силу первого условия — только одна нз переменных Ь(1,!',) равна 1, в силу второго условия — только одна нз переменных Ь((к, Ж) равна 1. В силу третьего условия, если для фиксированного К все Ь((, К) равны нулю, то все Ь(К, !к) тоже нулевые, а если одно нз Ь((к, К) равно 1, то одно нз Ь(К, ! ) также 1.
Поэтому прн этих условиях значения функции ~~себе ! ( равны длинам простых путей нз А) в Ал( н задача нахождения кратчайшего пути сводится к задаче линейного программирования. Следовательно, задача нахождення кратчайшего пути решается в Мар!е встроенной функцней ппп!т!ге.
Свтввов планорованов 'Посмотрим, как в Мар!е находится кратчайший из трех параллельных пу~~й из А в В, представленных на рисунке: А хЭ Рис. 6.(( Ставим в соответствие верхнему пути булеву переменную хо среднему— х,, нижнему — х,. Так как из трех путей должен быть выбран только один, то дополнительное условие х, + х, + х, = 1.
Пеленая функция г = 5х, + 4х, + бх3. Применение функции гп(п(ппге дает: > м1е1т1ге (5*х1+4*х2+б'хЗ, (х1<=1, х2<=1, хЗ<=1, х1+х2+х3=1), НОННЕБАТ1ЧЕ)г (хЗ = О,х! = Ох2 =1) Таким образом, как и следовало, ожидать, кратчайший п:.ь — средний. Добавим еще два пути и найдем кратчайший маршрут из А в С: хЗ Рис. 6.(2 В этом случае вычислительная секция имеет вид: > ехпамьге (5*х1+4 *х2+б*хЗ+2*х4+3*х5, (х1<=1,х2<-1,хЗ<=1,х4<=1, х5< 1,х1+х2+х3=1,х4+х5 1),НОННЕПат1ЧЕ); (хl = О, хЗ = О, хЗ = О, х4 = 1, х2 = 11 Кратчайший путь: хс х4 ПУть, имеющий наибольшую длину, находится аналогично: > вахавьгЕ (5*х1+4*х2+б*хЗ+2*х4+Зххб, (х1<=1,х2<=1,хЗ<=1,х4<=1, Х5< 1,Х1+Х2+ХЗ 1~Х4+Х5 1)'НОННЕП)(тг)(Е)г 1х4 = О,ху-,О,х2.= О,хЗ =1 хб = 1~, Глава И.
Матвматочвскив модело в экономика 160 Рассмотрим типовую задачу управления проектом с детерминированным временем выполнения работ. Задача ([1], 14.3.1). Сеть проекта представлена следующими данными Найдите критический путь (макснмальный по времени). Сколько времени потребуется для завершения проекта? Решение. В соответствии с условиями задачи строим ориентированную сеть: С(7) Рис. б.
(3 Оо ней составляем целевую функцию, задаем ограничения на перемен- ные и получаем: > п~ах1т1хе(5*х1~-3*х2~-7*хз+б*хл~-7*х5+3*хб+10*х7+8*хв,(х1<=1, х2<=1,хЗ<=1,х4<=1,х5<=1,хб<=1,х7<=1,х8<=1,х1+х2=1,х1=х4+х З,х2=хб,х4+х5=хб+х7,хЗ+хб=хе,х7+х8=1),МОННЕ6ЛТ1ЧЕ(; (ху = О хд = 1 х! = !,хб = ! хд = О хб = О х4 = 1 х2 = О) > всьв($,5*х1+3*х2е7*хЗ+б*х4+7*х5>3*хб+10*х7+8*х8]; 22 Ответ: критический путь АРРН, ! = 22. Разберем решение в Мар!е задачи «коммивояжера» ((б), стр. 197). Имеются п + 1 пунктов (! = О, ..., и) с заданными расстояниями д,„между (-и и )с-м пунктами. Требуется составить оптимальный маршрут из условия'минимизации сум- Свтввов'ппвнироввнив про ега дли машины, выходящей из «нулевого» пункта, которая д и'быв'т' ' ~~ждом пУнкте по одному и только по одному разу и ~,р~у "' пункт Задача «коммивояжера» сводится к частично целочислени „- ""'"' 'иненного программирования относительно пз булевых переменных, 2 ~~язанных с х,„дополнительными и ограничениями-неравен „.
ми' обеспечивающими «не рерыв осты маршрута (6(. Заметим, что доп "льнь)е ограничения-неравенства можно заменить условиями на мошнос„с,. чений (сечений нулевой мощности быть не должно). Не имеет смысла включать их все в систему ограничений. Рациональнее решать задачу без них и только в случае появления подциклов, вводить дополнительные условия в систему ограничений, причем именно на те сечения, дуги которых не вошли в предполагаемый маршрут. С учетом сказанного решаются следующие две задачи.
Задача ([6], 297), Составить математическую модель и решить задачу коммивояжера при следующих числовых данных: и =3 <(о = 25 доз = 40 Ио, =30 д,з =50 Ы,з =20 дз =60. Решение. Делаем чертеж к задаче: А1 А2 АО Рис. 6.)4 Каждому ребру построенного графа сопоставляем свою булеву переменную х„( = 1, 2, ..., б, значение которой равно 1, если ребро входит в кратчайший путь, и равно О, в противном случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
