home Other disciplines Books Mathematics programmers - Nakonechny S.I.

Mathematics programmers - Nakonechny S.I.

6.7. Butts zashosuvannya tsіlochislichih tasks lіynіynogo programvannya u planuvannі tulyavnnі vibrobnitsvom

The problem of the backpack . Nayprostіshoyu voprosyu tsiloksislovogo programvannya, and I myself set out a problem with one of the obmezhennyam, - the problem of the backpack (abo ratsn). This task is the task of applying practical practical care. The name "task about the backpack" is written in the context of the tasks of the vibor of the nimble storehouse of objects, but it is a pleasure to sing the problems of the tourist with the problems of the tourist for the optimal turn of the speeches.

Tourist can vibierati potrebnyi rechі із List z n items. Vogue of the vag of cutaneous j- th object . Vaznachenna takozh tsінність a skin kind of subjects . The maximum vag in the back of the knapsack can not be interchanged with the designated oath. Neophidno viznachiti, skilki obektiv in a skinny kind of tourist poklasti in a backpack, shchob zagalna tsіnnist sporadzhennja bula as much as possible for vikony vikonannya obmezhenna on vagu rucksack.

Significantly through - kіlкість предметів j- kind in the backpack. Todi's mathematical model of problems and mathematicians:

;

, - the number of numbers, .

A farmer for fertilizing land needs a feeder of 107 kg. Він може buy добрива in packs of 35 kg ватістю 14 ü. Od. Abac by 24 kg. Od. The farmer's method is to purchase not less than, but not to 107 kg after finishing with the minimum vitration. Prichomu potrybno kupuvati abo tsilu packing, abo not kupuvati її zovsim, bo partpolicy packing pridbati nelmozhno.

Rozvjazannya . Significantly the number of packages of wagons of 35 kg and that of 24 kg is in the form of zmіnimi That . Маємо модель цієї задачиі:

;

, - the number of numbers.

In the result of rozv'yazuvannya tasks, be it any of the wives of the methods of the optimal plan: , . Otzhe, for the optimal plan naimenshi vitrati, scho dorivnume 50 mind. Od., Mozvolі u razі procureіvі odnієї packing добрив вагою 35 кг та троох вагою по 24 кг.

The problem of optimal rozroju materіalіv . On the agenda of the meeting, the rostrum m rіznih partіy materіalіv otnagah Odinitskom rosmіru in kozhnіy partnerії. Із матеріалів усіх партій потрібно виготовити maximally кількість комплектів Z , у кожен з яких go in p різних виівівів імрехіві parts in кількості Odnitsyn, vrahovoyuchi, scho kozhnu oditnitsu materialu mozhno rozkroti v okremі nakol'nii n rіznimi mnogo, prichomu u raz i rokroju odinitsi i- oї partії j-in the way otrymuemo Details r- th kind.

The mathematical model of tasks is written down. Significantly through - kіlkість odnitsyn material i- ої партії, що will be rozkroєnі j- th way. The Todi of the i- th Party for the j- th method otsrimaeto Details r- th kind. З усієї ж i -ої партії у разі застосування до неї всіх n способів розкрою отримаємо Details r- th kind, and s usіh m partіy їх буде отримано . At kozhen komplekt moe enter Details, that vidnoshennya Viznachaet kіlkіst komplektіv, yakі mozhna vigotoviti z details r- th kind. Кількість повних комплектів для всіх видів детали визначається найменшим з цих відношень.

In the case of a different set, make it look like a vidon:

,

Zvidki p - 1 vidnoshennya can viraziti through be-yake of them, napriklad, through peshe:

Abo .

Confirming That Їх meaning, отримаємо p - 1 обмеження стосовно комплеків:

;

Vrahovoychy nayavnu kilkіst oditnits material in the parties, is written down m омемеь щодо ресурсів:

.

(Obmenzhennya shodo vikoristannaya resursiv mozut bouti rivnyanni chi neervnostyami zalizhno vid, pobnistju chi not vynnistju neobhdno vikoristyva nayavny otsyag resursiv).

All Мають задовольняти смову невід'ємності: That tsіlochislovostі.

Отже, необхідно знайти найбільше значення функції:

For obmezhen:

,

- the number of numbers .

Rozglyanemo butt problems and optimal rozroju materіalіv.

At the shop, the rods of the wagon are 6 m long for harnesses with a length of 1.4, 2 and 2.5 m. The workshop is serviced by two zamovnikivs, for skinheads such asks do not need to be found:

1. Yak rozrizati 200 prutis, shchob otrimati not less yak 40, 60 і 50 zatativok zavdzhki vidpііdno 1,4; 2 і 2.5 m. Criterion optimization - minimum wake;
2. Yak rozrizati 200 rods for molding from otrimanyh zagotivok komplektiv, scho zakladayutsya z dvoh zagotivok dovzhinoyu 1,4 m, ta odnіy dovzhinoju 2 і 2,5 m. Criteria optimizatsii - the maximum number of sets.

Rozvjazannya .

1) the challenge for the minds of the first zamovnik. Маємо партію прутів у кількості Pieces. Відома нижняя межа кількості заттівок skin appearance. Introduced so:

- kind of rewind;

- sposib rozrizannya rod;

- the vihid at the time of the routing of the rod by the j -th way of harnessing r- th kind;

Cj - look at the rozrizuvannya rod in the j- th way;

- the number of valid bars;

Dr - the lower end of the consumer in the r- iy zagotivtsi;

Xj - kіlkіst prut, які розрізані for j- th way.

A mathematically designed model for rozvjazuvannya the first point of the problem and optimal rozroju.

Критерієм оптималності є мінімальна кількість відходів: .

Кількість отриманих затаівок кожного вид має бути не меншю від зазначенийх requirement:

Сумарна кількість прутів, які розрізані різними способов не може бути більшою від кількості наявних прутів:

.

Змінні задачиі - невід'ємні і tsілі numbers. Separate, mathematical model:

,

- the number of numbers .

There is a number of economical and mathematical models of roses, rozglyanuvshi mozhivі varianti їх розрізування:

Table 6.5

Bazhano, scho u mnzhinu vvіyshli vsya mozhilі varіanti, navіt takі, yakі on the first sight to be built nefektivnimi, napriklad, X 6.

The number of economy-mathematic models of the retail pruning model is as follows:

For the mind:

А) кількість затаівок задовіжки 1,4 m:

;

Б) кількість затівок задовіжки 2 m:

;

В) кількість затівок завівки 2,5 m:

;

Г) кількість наявних прутів:

;

Д) невід'ємність змінних:

;

Є) tsілочисловість змінних:

- the number of numbers .

Otzhe, zagalom maemo mathematic model of the mind:

,

- the number of numbers .

Rozv'yazuchy task one of the methods of numerical programming, otrimyemo nabir alternative optimal planіv (zagalnoy kilkistyu 146). Napriklad, such a plan zabezpechuet vygotovlennya vseh vidiv vozativok at mіnimalno mozhnivy kіlosty for namenshogo zagalnogo vyhodovіv, prichomu chtsogo vikoristovuytsya lisha 54 twigs: , , Toto 4 rods must be rozrizati in another way (for three harnesses with a length of 2 m) and 50 rods in a fourth way (according to one type of cautery). Sumarna dovzhina zalishkiv dorivnyuet p'yati meters. Analogic meaning of tsіlової функції ( ) Дає оптимальний план, за яким виготовляється більша кількість кінцевої продукції та витрачається All the original material:

.

Отримані оптимальні пла датьть набір альтернативних варіантів для прийняття управінських рішень for specific brainwashing minds.

Uskladnimo rozglyadunii application of problems and optimal rozroju materіalіv, scho perebachaet tilki one type of material that meets the requirements of the formulations of kits.

2) rozv'yazhemo task for the minds of another zamovnik. Оскільки in other items of taskі відсутні обмеження shodo kіlostі zagotіvok, protivіmagієt formіvnya komplektіv, neobhіdno дещо змінити позначення:

- kind of rewind;

- sposib rozrizuvannya rod;

- the vihid at the time of the routing of the rod by the j -th way of harnessing r- th kind;

- the number of valid bars;

Xj - kіlkіst прутів, які розрізані за j -им варіантом;

- кількість r- го виде поготівок у комплекі;

- the number of all types of r- th kind.

A mathematical model in the sense of time is in the model, in which the viscose is viscous.

З усього матеріалу може бути отримано Harness r- th kind. At kozhen the complete set mju enter dvі zagotivki the first type , That vidnoshennya Viznachaet kіlkіst komplektіv, yakі mozhna vozmozhnosti z zagotivok first form. Analogically, it is possible to assign a number of sets for other types of harbors That . Кількість можливих повних комплеків визначається найменшим з цих виідношень: . Until then, in the case of a different set, make it look like a vidon: , Zvidki two z vidnoshen can viraziti, napriklad, through peshe:

, Звідки , .

Obviously That The following meanings:

Abo ;

Abo .

Vrahovoychy nayavnu kіlkіst oditnits materіalu, zapishemo obmezhennya shodo vіkoristannya resources:

.

All Мають задовольняти увуву невід'ємності: That tsіlochislovostі.

Отже, необхідно знайти найбільше значення функції:

For obmezhen:

,

- the number of numbers .

A numerically mathematically model is written down, being skorostavshis alternately give roses rozpunkіv mozlivih varіantіv rozrizuvannya prutiv (Table 6.5).

Із умов формування комплектів маємо: , Тобто затівок першого вид має бути вдвічі більше, ніж зазатвок other that third kind. Звідси випливає, що за мінімальну кількість комплеків може бути прийняте одне з двох vidnoshen: Chi . Vibéramo, for example, . Використовойчи дані таблиці, запишемо вираз для цільової функції:

.

Obmezhennia schodo formvaniya setіv matimut viglyad: , Abo

,

Zvidsy

,

Analogous to :

, Abo

.

Омеження щодо використання наявних прутів:

.

Омеження стосовно невід'ємності та цілочисловості змінних:

;

- the number of days .

Otzhe, zagalom maemo taku mathematic model:

Max

- the number of numbers .

Having solved the problem of whether or not a method is used, the optimal plan is: ,

Complete set.

The task of the salesman . Розглядається n міст А 1, А 2, ..., Ан , що пов'язані між собою транспортною мережею. Відома матриця відстаней від кожного міста до усіх інших:

,

Prichomu in a fatal vipadka not zavzhdi . Composer is guilty of indulging in the leather misty one time and turning in those places, since he has lost control of himself. It is necessary to take such a route, to pass through the lintel misto lishe once and i dovzhina yakogo mіnіmalna.

Significantly:

Otzhe, hij mozhe nabuvati more than two of them: the odinitsi abo zero. Takі zmіnnі мають shall be called bulovikh zmіnnih. Obviously, they are stinking. Цільовою функцією цієї задачі є мінімізація vsogogo route komіvozhera:

,

De сij - відстань між містами і та j .

Mixed odnozovnoy vdozhdu in the skins of the city:

.

Obmenzhennya schodo odnorazovogo vizdu z kozhny mista:

.

Signed omegzhennya not ponnyistyu opykuyut permissible route and not turn on the route. Щоб усунути цей недолік, ввестиемо невід'ємні цілочислові змінні , Yakі in the process of rozv'yazuvannya tasks i nabuvatimut 'meaning of the ordinal numbers of the city for the optimal route of directing the comic. Замешемо обмеження, які усувають можливість існування підмаршрутів:

.

Dobedo, scho for dovilnogo route, a way to start in point A 1, you can know so , Scho happy to induce nerivnist. Nehaj komіvojazher perezhdzhzhaє z mіsta Aі to mista Aj na r- m krotsi i permissibly takozh, scho , Тоді з міста Аj комівояжер flaw on the offensive, ( р + 1) -ю кроці і . Звідси випливає, що:

.

Taka nervіvnіst vikonuetsya for be-yakikh meaning i ta j u razi, coli , While Нерівність виконується як строге рівняння. Otzhe, yakshcho vibrato route transplanted from the i- th city to the j- th, then zagadana nervivnost fіksue two pіddyad orderly number tsikh mist.

Otzhe, maemo taku mathematic model:

There are 6 points in the economical region. Комівояжер, який виїжджає з міста 1, має be impelled in the leather industry once and turn to the void point. Know the shortest route, yakshcho vіdstanі між містами відомі (induced in km in Figure 6.7).

Fig. 6.7

Rozvjazannya . Маємо 6 пунктів, де має побувати комівояжер.

Significantly:

Otzhe, hij - bulovі (tsіlochislovi) zmіnnі. A number of economy-mathematical model of tasks for a comic writer for giving minds is written down.

As you can see in Fig. 6.5, visnovuєmo, scho vseih mozhlivih rozdіv є 12. Z pervohogo mista mozhna pozhapiti up to the cutaneous p'yati p'yati, the pathways are known by the explanations , , , , . To another, the people of the world are deprived of their lives, but the first, the fourth, the fifth, the third, the third and the third: , , . Analogously cognitively, you can postpone the routes from the third, fourth, fifth, and the shosty mist:

Third - , , ,

The fourth - , , , , ,

The fifth - , , , ,

S shostogo - , , , .

Zagal otrimali 24 zmіnnі. However, the actions, That , That Describe one route, the dovzhin I for the purpose of tasks and not zaminjuetsya zalizhno vid stitchesku peresuvannya (at razi from the first city to another chi from another to the first need to be fitted 50 km). Otzhe, koefitsynt y tsilovіy funktsii with such zmіnnih bude novoim.

Criterion of optimality - the minimization of the long route of the comic seller:

;

A) mocha odnozhennogo odozhennoy v'їzdu kozhne misto:

B) obmezhenna shodo odnorazovogo vizdu z kozhny mista:

;

;

;

;

;

C) obmezhennya shodo usunennya pіdmarshrіv:

;

;

;

;

;

;

;

;

;

;

;

;

;

;

Ui ( uj ) - the number of numbers .

So tasks are rooted in special methods.

In the result, the optimal variant is overshadowed by such a route (Figure 6.8).

Tobto of the first city for the optimal plan for neobhidno perezhzzhati to the fourth, and the fourth - to the third, third - to the shiny, the shostoy - to the fifth, the fifth - to another, and the other - to the first. Dovzhina of the route, yaka є mininimalnoy, dorivnyuє 300 km.

Zauvazhimo, scho analogychny problemy neridko vinikayut on pravitcі, especially in dribnomu biznesi. Tipovim mozhe bouti, napriklad, takie zavdanya: "Fіrma u mіstі myo 25 kіoskіv, yakі trade in nonalcoholic ones. Shchodenno z basis avtomobilyom rozvozyat to them the goods. Yak optimally organizuvati rozvezennia pivnogo otnagu goods? ".

The problem is with post elements of vitrates . Відомо, що витрати на виготовлення be-яіїї produktsії zakladayutsya z dvuh part: postійних та змінних витрат.

Нехай розглядається процес виробництва продукції за умов використання m видів ресурсів. Відомі обсыги skinage resources , And that is the norm of the vicarage of the i- th The kind of resources for the literacy of the j- th Product type .

Умови використання ресурсів на виготовлення продукції можно в вигляді эти обмежень:

.

Vitrati on vygodovlennya produklyayut podilyayut for two vises: postyny ​​vitrati - , Yaki do not lie in the vibrobitvtas' oath, і змінні - сj, що rorakhovuyutsya v oditynitsu vigotovlenії produktsії, de j - kind of products. It is necessary to excel the optimal conditions for the production of virgin products , For some zagalnі vitrati buli b mіnіmalnimi.

Zauvazhimo, scho vygotovlennya be-yakoyi kіlkosty produkcii You need to use fischovani Ta zmіnnih Vitrate, tobto zagalna suma vitrat on vygodovlennya produkcii obyagom Viznachaetsya for the formula: . Однак у разі, якщо (Products do not vypuskatsya), then rozhraunok vitrate for the formula To bring up an additive value, but wrong. For an adequate visualization of the functional zalozhnosty zagalnyh vitrate vіd otsygu vyroblenії produktsії j- th kind mozhna skoristatisya nakolіnіynoju funktsієyu:

,

De Є bulbous species:

Taku umovu can be recorded in viglyadі lіnіynoї nerіvnostі. It is permissible, but it is necessary to finish the number M , Vikonuvatimetsya for vseg permissible value . Todi wearing the look:

Zavjdi vikonuetsya when , І, moreover, yakshchio - the number, then the minimum value of the function will be reduced to the renting of the value . Yakshto , Then the nerves To steal .

Otzhe, maemo taku mathematic model:

Цільова функція, що descriptive мінімальні загальні витрати on виробництво всіх видів продукції, набуває вигляду:

For the mind:

;

;

- the number of numbers .

The farmer plans to vibrolyat three kinds of products: winter wheat, tsukrovi buryaks and milk. Загальні витрати складаються з двох частин: постійних та змінних. See the table in Table. 6.6:

Table 6.6

It is necessary to visibly optimize the plan for the vibrobitvita production of the cutaneous species for the purpose, the farmer is 100 hectares.

Rozvjazannya . Nehai xj - the vibrobitztva's j- th type of product m , .

Funktsy zagalnyh vitrat on vyrobnitsvoto j- th kind of product moe viglyad:

.

Цільовою функцією в цьому прикладі може бути maximмізація прибутку:

,

Де рj - ціна одниці j -ї продукції.

Obmenzhennia shodo vikoristanna rіlli is written down like this:

,

De aj - the norm of the consumer in the ryll on the virbitnitsu odinnitsi j- produkcii; A - area.

Загалом маємо таку математичну model:

;

;

- the number of numbers .

The number of economical and mathematical models of a number of tasks is written down. Obviously, as much as possible, the vibro- = 500 tons, tsurychiny Buryak - = 5000 tons, milk - = 400 tons. Otzhe, M može dorivniuvati 5000. Звідси маємо:

For the mind:

;

;

;

;

;

- the number of numbers .

Having solved the problem, the optimal plan is:

. .

Mozhna visnovuvati, the farmer for the cynicism of minds nayvigіdnіsi zanyаtisya virochuvannjam on all the ploshi rіllі tilki tsuzkikh buryakiv.

Zvichayno, in the real situation, існує більший набір можливих видів продукції, and takozh bіshe more обмежень щодо використання ресурсів.

The task of planning a vibronichnia lіnії . To look at the process of functioning of the vibro-clinic line. Відома схема, яка зображає послідовність робіт для виготовлення k видів продукції . Відомі також: aj - trivalість виконання j -ї операції ; - termin for k- th virologic, to yakogo neobhidno finish the operation j ; Xj - the moment of the commencement of the j- th operation; T is the triviality of all transactions. Admitted, at any moment, one operation is required to verbalize.

It is necessary to visually optimize the mantle of the skin operation.

Economical-mathematical model of virbnichoi lіnії міститиме такі групи обмежень:

1. After the vikonannya j- ї опера ц ц запис запис запис запис запис запис запис запис запис запис запис запис запис запис запис запис запис запис Yakschoo j -th operation is transferred to the i- th operation.

2. Obmenzhenya schodo nezrozgalozhenosty virobnikogo process for the operation і ta, yaki not vikonuytsya one-hour ( i ≠ j ), mi Viglyad:

Abo xi - xj = aj , yakzscho operation j translate the operation;

Abo xj - xi = ai , as well as the operation and operation of the operation j .

Zauvazhimo, scho logichnі obmezhennya mind "abo-abo" can not enter the economy-mathematical model of problems of linear programming, the stink of stink of rocks do not inflame a multitude of permissible rozv'yakiv. Тому необхідно ввести допоміжні змінні, які уможливлюють запис наведених вище логічних умов у вигляді лінійних обмежень. Це такі бульові змінні:

Скориставшись прийомом з попереднього прикладу 6.6. (введення досить великого числа М ), запишемо обмеження:

;

,

де М — досить велике число.

3. Обмеження щодо термінів виготовлення кожного виробу:

,

де j — остання операція для k -го виробу.

4. Усі операції мають бути виконані до моменту t :

, .

Критерій оптимальності:

,

тобто ставиться завдання, щоб тривалість виготовлення всіх видів виробів була мінімальною.

Отже, маємо таку математичну модель:

, — цілі числа .

Потрібно оптимізувати функціонування виробничої лінії, яка охоплює 11 операцій з виготовлення двох виробів. Лінію обладнано одним багатоопераційним верстатом. Послідовність і тривалість (у хвилинах) виконання операцій відображені на рис. 6.9.

Fig. 6.9

Визначені тривалості виготовлення виробів А та В відповідно дорівнюють 120 і 150 хв. Передбачається, що в кожний момент часу на верстаті може виконуватися тільки одна операція. Визначити оптимальні моменти початку кожної операції.

Rozvjazannya . Позначивши через хj момент початку j -ої операції, запишемо числову економіко-математичну модель функціонування виробничої лінії:

за наведених нижче умов.

1. Обмеження стосовно послідовності виконання операцій:

;

;

;

;

;

;

;

;

;

;

;

.

2. Обмеження щодо нерозгалуженості виробничого процесу:

;

;

;

;

.........................................

;

;

...........................................

;

.

3. Обмеження щодо тривалостей виготовлення виробів:

;

.

4. Усі операції мають бути виконані до моменту t :

;

;

;

.....................

;

..................

.

5. Обмеження щодо невід'ємності змінних:

;

, — цілі .

Отже, маємо частково цілочислову задачу з бульовими змінними.

Задача про призначення . Ця задача була розглянута в розділі 5 як така, що зводиться до транспортної і може бути розв'язана одним з відомих методів знаходження оптимального плану транспортної задачі. Проте такий вид задач належить до задач цілочислового програмування, оскільки їх змінні є бульовими і оптимальний план може бути знайденим також методами цілочислового програмування. Не повертаючись до загальної постановки задачі та побудови її математичної моделі (див. § 5.10), наведемо ще один приклад задачі про призначення.

Необхідно розподілити чотирьох робітників за чотирма видами устаткування так, щоб їх загальна продуктивність праці була максимальною. Дані стосовно продуктивності праці кожного робітника на устаткуванні кожному виду наведено в табл. 6.7:

Таблиця 6.7

Rozvjazannya . Зазначимо, що дану задачу можна розглядати як транспортну, в якій робітники ототожнюються з постачальниками вантажів, а види устаткування — зі споживачами цих вантажів. Обсяги пропозиції та попиту в кожному разі дорівнюють одиниці. Отже, змінні будуть бульовими:

Якщо відома продуктивність праці і -го робітника на j -му устаткуванні, то числова модель про призначення набуває вигляду:

For the mind:

;

;

;

;

;

;

;

.

;

— цілі числа .

З огляду на особливу структуру цієї задачі, зокрема на її «транспортний» характер та рівність правих частин обмежень, для її розв'язування можна застосувати ефективніший алгоритм, ніж для звичайної задачі цілочислового програмування з бульовими змінними. Пропонуємо читачеві ознайомитися з такими алгоритмами, які детально описані в літературі [12].