Сдвижков О.Л. Математика на компьютере - Maple 8 (1185914), страница 20
Текст из файла (страница 20)
Для каждой вершины сумма значений переменных, соответствуюи(их ребрам, выходяи(им из нее, должна быть равна 2, так как по условию задачи коммивояжер в каждый пункт въезжает, а значит, и выезжает из него. Составляем математическую модель задачи и находим ее решение: > оз1п1ыьзе (25*х1+40*х2«30*хЗ«20*х4+50*х5«60*хб, (х1<=1, х2<=1, хЗ<=1, х4 <=1, х5<=1, хб< 1, х1+х2+х3=2, х1+х4+х5=2, хЗ+х4+хб=2, х2+ х5«хе=2),НОННЕСЛТ1ЧЕ)з (хб = Ох! = Ох4 = 1 х2 = (хг = (хб =1) > зоЬз(«,25*х1+40*х2+30*хЗ+20*х4+50*х5+60*хб) )40 Ответ: Ао - Аз - Аз - Аз Ао гзм« = 140 твг Глава И. Математические модели в экономике Замечание. Небольшие и достаточно очевидные изменения ограничений, в решении последней задачи, приводят к кратчайшему остовному дереву графа, представленного на рисунке 6.14: > в1оьм1ге(25*х1+40*х2+30*хЗ+20*х4+50*х5+60*хб,(х1<=1,х2<=1, хЗ<=1,х4<=1,х5< 1,хб<=1,х1+х2+хЗ>=1,х1+х4+х5>=1,хЗ+х4+хб> =1,х2+х5+хб> 1,х1+х2+хЗ+х4+х5+хб=З ), НОННЕОЛТ1ЧЕ) г [х1=1х5 = 0 х3= 0 хб =Ох4=1,х2=1) > ве)>в (%, 25*х1+40*х2+30*хЗ+20*х4+50*х5+60" хб) 85 В слУчае, когда сРеди РасстоЯний ([в и ([х есть не Равные ([ х1), Решение задачи о коммивояжере несушественно отличается от предыдушего.
Задача. Решить задачу о коммивояжере с матрицей расстояний между пунктами 0 4 9 6 1 2 0 9 2 10 1! 11 0 8 1 5 4 3 0 8 111!80 Решение. > с:=масгзх( [ [О, 4, 9, 6, 1), [2, О, 9, 2, 10], [11, 11, О, 8, 11, ['5, 4, 3,0,8], [1,11,1,8,0]])' 0 4 9 6 1 2 0 9 2 10 11 11 О 8 1 5 4 3 0 8 111 1 8 0 > х: =ма ггьх ( [ [О, х12, х1 3, х14, х15], [х21, О, х23, х24, х25], [х31, х32, О, х34, х35], [х41, х42, х43, О, х45), [х51, х52, х53, х54, О! ] ); 0 х12 х13 х!4 х15 х21 0 х23 х24 х25 х31 х32 0 х34 х35 х41 х42 х43 0 х45 х51 х52 х53 х54 0 > г: воа(вот(с[1,З]*к[1,3],1=1..5),3=1..5); а: = 2х2! +11х31+ 5х4! + х51+ 4х12+1!х32+ 4х42+11х52+ 9х13+ 9х23 + Зх43+ х53+ 6х14+ 2х24+ 8х34+8х54+ х15+10х25 + х35,+ 8х45 Цвпочиопвнное провравг]иирование 163 > евпасзхае (а, (зес)(зазс(к [1,5),5=1.. 5) т, в=1..
5], зен(заас(х [а, ]], ° 5) =т ° 3=2 .. 5), вес[(х[1, З) <"1, 5=[ ..5), зес](х [2,5) <41 5-1 ° ° 5) ° зеч(х [3, 1) <=1, 5< т .. 5), зес](к[4, 51<=1, 4=1 . 5), зес((х [5, 5] <=т, 5=1 .5) васа(зае(х[',5],х=[..5),5 2..5)=5),ионнво]сттчв); (х31 = О, х32 = О,х34 = О, х41 = О,х13 = О,х!4 = О,х15 = О, х2! = О, х42 = О, х45 = О, х53 = О,х54= О, х23 = О, х25= О, х52 = О, х5! = 1,х!2 = 1,х24= 1, х35 = 1, х43 = 1 Ответ: А, — А, — А, — А, — А, — А,.
9 7. Целочисленное программирование Частично целочисленные задачи линейного программирования можно решать сравнением оптимальных значений целевой функции при тех целых значениях указанных целочисленных переменных, которые удовлетворяют системе ограничений. Задача ([6), 288.4). Решить частично целочисленную задачу з=х, +х,-+шах ( 2х,+х,<4, х,+2х,<4, х, > О, х, > О, х, — целочисл. Решение. Из ограничешсй находится диапазон 10, 2/ изменения х, и с помощью оператора цикла 1ог последовательно вычисляются наибольшие значения г при целых значениях х2 из данного диапазона.
Из них выбирается наибольшее: > сезсахссетьп(з1сартех)стог х2 сгое О Со 2 Оо х:=[заьз(еаххмвхе(хтах2,(2*хтех2<=4,х[а2*х2<=4),НОННЕСАТ[ЧЕ),х т.гх2),сзахзсатхе(хтгх2,(2*х1.гх2<=4,х[.г2"х2<=4],НОННЕС](ттЧЕ),х2]," ос(; (в; = [2,(х1 = 2), 0[ Г5 3 гв: = ~-, (х! = -), 1 [2 2' ш:= [2,(х1 = 0),2) 3 5 Ответ: ( —,1), гпаха = —. 2' ' 2' Полностью целочисленная задача Л11 решается программным модулем, сравниваюгцим каждое следующее значение 2, в целочисленной точке.
удовлетаоряюшеи системе ограничений, с предыдушим, используя вложенные циклы и оператор условного перехода 1[, причем без пакета зппр1ех. Поскольку в программный модуль входит система ограничений, то определяя диапазоны измене- 164 Гпава И. Математические модели е экономике ния переменных, необходимо следить только за тем, чтобы они не оказались меньше возможных. Задача [[б[, 284.1). Найти полностью целочисленное решение а = Зх, + Зх, -5 гпах, х,+Зх,>б Зх, +2х, < Зб х, <13 х,>Ох,>О Решение.
> 2[1):=О: > бог х1 Ггов О Го 12 4)о бог х2 ггов О Го 13 4[о 3*х1+3*х2; 15 3*х1+3*х2>2[1) апг[ х143"х2>=б ап4) 3"х1+2*х2<=35 ап4[ х2<=13 гьеп 2 .= (3*х1+3*х2, х1,х2) оа о<[2 > 24 [48, 3, 13[ Ответ: гпах г = 48, [3,13). Аналогичным образом решаются задачи на минимум. Задача [[б[, 284.1). Найти полностью целочисленное решение а = х, + 2х, + х -+ пп'п Х, +Х, +Х5+Х, +Х, =5, Х2+Х5+Х4 — Х5 =2, хз — Х4+х5 =1, х, > О х, а Ох, > О х4 > О хз > О. Решение. > в[1)4=20: > гог х1 бгов О Со 5 бо бог х2 Егов О Го 5 4[о гог хЗ тгов О го 5 бо бог х4 ггов О Го 5 4[о гог х5 ггов О Го 5 4[о х1+2*х24254 12 х1+2*х2+х5<в[1) апс[ х1+х2+хЗ+х4+х5=5 ап4[ х2+хЗ+х4-х5=2 апг[ хЗ-х4+х5=1 Гпеп в:=(х1+2'х2+х5, х1,22,23,х4,25] 11; о<[ ог[ ог[ ос[ ос[2 > в; Ответ: гп[па = 4, 0,1.1,1,1).
Целочисленное программирование Убб Произвсдствен. ) Экономмвский площвди, м. кв. ~ эффект, млн р. Финвнсовва ресурсы, мпн руб. Трудовые ресурсы, чел-дней Мероприятие 130 ~ 13000 3000 Закупка станков с ЧПУ 350 400 ]текущий ремонт 90 250 60 , '300 ; 8000 Монтвх транспортного конвейера ( 100 ) Установка рельсового крана ! 200 , 300 ~ 150 ! 1 2000 ) Ввод системы контроля качестве т30 ~ — ~ 150 , '2500 800 500 / 100 ) 15000 Разработка АСУП На реализацию всех мероприятий завод может выделить: трудовых ресурсов 1300 чел-дней, финансовых — 1 млрд руб., производственных плошадей— 700 и.
кв. Какие мероприятия следует провести, чтобы общий зкономический эффект был максимальным? 1) Каков максимальный экономический эффект от проведения мероприятий (млн руб.)7 2) Какое количество мероприятий следует провести? Решение. Делим все показатели на 100, обозначаем меропоиятия: закупка станков — хы ..., разработка АСУП вЂ” х,.
Приходим к целочисленной задаче линейного программирования с булевыми 1альтернативньгми) переменными: г =130х, + ЗОх, + 80х, +120х, + 25х, +150х, -о птах, с 3.5х, + 2.5х, + х, + 2х, +!.Зх, + 8х, > 13, 4х, +09хз +Обх, +Зх, +5хв < 10, 1.3х, + Зхз +!.5хч + 1.5хз + хе < 7. Программный модуль вычисления гпаха имеет вид: > щ!1]:=От > бог х1 бсощ О Со 1 с]о бос х2 Гсощ О Со 1 т]о бос хЗ ксопт О Со 1 с]о бох х4 бсогп О Со 1 с]о бох х5 Вком О со 1 с]о Вох хб бхопт О со 1 с]о 130*х1+30*х2+80*хЗ+120*х4+25*х5+150*хбг 130*х1+30*х2+80*хЗ+120*хе+25*х5е150*хб>щ!1] апс] 3.5*х1+2.5*х2+хЗ+2*х4+1.3*х5+8*хб< 13 апс! 4*х1+0.9*х240.6*хЗ+3*хе+5*хб< 10 аоа Задача ()1), 20.1), Руководство завода предполагает провести комплекс организационно-технических мероприятий с целью модернизации производства.
Мероприятия предполагают затраты производственных, трудовых и финансовых ресурсов. Глава И. Магпематические модели е экономике 1.3*х1+З*ха+1.5*х4+1.5*х5+хб< 7 Гьеп в: [130*х1+ЗО*х2+80*аз+120*х4+25*х5+150*хе, х1,х2,хз,х4,х5,хб1 ттз оа ос[ ос[ ос[ оо оби > П14 [375, О, О, 1, 1, 1, 1] Ответ: 1) 37500 млн руб., 2) 4. Задача ([6], 308).
Общую сумму капиталовложений К = 1200 необходимо разделить между пятью объектами, потребности которых 420, 180, 240, 560, 300, а ожидаемые прибыли 80, 65, 90, 210, 150. На каждый объект капиталовложения или выделяются в необходимой сумме, или вообще не выделяются. Составить математическую модель задачи целочисленного программирования, заключающейся в оптимальном распределении капиталовложений, и найти ее решение.
Решение. Задача также сводится к целочисленной задаче линейного программирования с булевыми переменными: г = 80х, + 65х, + 90хз + 210х4 +! 50хз -+ [пах, 420х, +180х, + 240хз + 560х4 + 300х, < 1200. Составляем программный модуль и выводим результаты: > в[11:=0: > бог х1 ггов 0 Го 1 ао гог х2 гсов 0 го 1 с[о гог хз тгов 0 Го 1 оо Еог х4 тгов 0 Го 1 с[о бог х5 тгов 0 Го 1 с[о 80*х1+65*х2+90*хЗ+210*х4+150*х5ь Гд 80*х1+65*х2+90*хЗ+210*х4+150*х5>в [11 ап<[ 420*х1+180*х2+240*хЗ+560*х4+ЗОО*х5<=1200 Гпеп в:=[80*х1+65*х2+90*хз+210*х4+150*х5, х1,х2,хз,хл,х5] 61; ос[ оо оо ос[ о<[; > вь [450, О, О, 1, 1, 1] Ответ. (О; 0; 1; 1; 1), г в в 450.
возможны различные варианты данной задачи. Пусть, например, задано дополнительное условие: капиталовложения обязательно вкладываются или в 4-й, или в 5-й объект. Добавляя в программный модуль условие х, + ха = 1, получаем: > в[1): 0: > тог х1 тгов 0 Го 1 оо гог х2 тгов 0 Го 1 ао гог хЗ гсов 0 Го 1 с[о гог х4 тгов 0 Го 1 оо гог х5 гсов 0 Со 1 ао 80*х1+65*х2+90*хз+210*х4+150*х57 1г 80*х1+65*х2+90*ха+210*х4+150*х5>в[11 аост тбЧ Целочисленное программирование 420*х1+180*х2+240"хз+560*х4+300*х5<=1200 асс) х4+х5 1 Сиеп и:=[80*х1+65*х2+30*хз+210*х4+150*х5, х1,х2,хз,х4,х5) г1; ос( ос( ос( ос( ос) > и; [385, 1, 1, 1, О, 11 Аналогичным образом решается задача об оптимальном назначении [[б], стр.
196). Имеется и работ и и) механизмов, способных выполнять эти работы. Известна матрица эффективностей выполнения работ. При условиях, что каждый механизм должен выполнять только одну работу и каждая работа должна выполняться только одним механизмом, требуется составить оптимальный план размешения механизмов. Пусть матрица эффективностей выполнения трех работ четырьмя механизмами имеет вид 5 2 3 4 2 4 4 3 3 3 4 4 Тогда решение задачи об оптимальном назначении им ет вид: > о:=пагг1х( [ [5,2, 3), [4,2,4), [4,3,3), [3, 4, 4] ] ); 5 2 3 4 2 4 4 3 3 3 4 4 > х: паггзх (4, 3) х: = аггау(1 ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
