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

Mathematics programmers - Nakonechny S.I.

2.6. The graphical method of outlining tasks of linear programming

For rozv'yazuvannya doubling tasks of linear programming , toto tasks of the dvom zmіnnimi, and takozh trivimychnyh tasks zastosovuyut gorichіchny method , sho ґruntuєtsya on geometrichnyі іnterpratatsії ta analitichnyh authorities of the tasks of linear programming. Intermediate vichorestnya graphical method zoumovlene folding of the impulses of the bagatogranist rozv'yaziv in trivimirnomu prostorii (for tasks with triom zmіnnimi), and graphical zabrazhennya zadachi z kilkistyu zmіnnikh bіols trjoh vzagali nemozhlive.

It's a glimpse of the problem.

Know

(2.17)

For the mind:

(2.18)

. (2.19)

It is permissible that the system (2.18) for the mind (2.19) sumsna i bakatokutnik izї rozv'yakіv obmezheny.

Zgіdno z geometricheskuyu іnterpretatsіyu zadachi lіnіynogo programvannya (§ 2.4) kozhne і -o obmezhennja-nervivnist y (2.18) viznachena pivploschinu with the boundary direct (I = 1, 2, ..., m ). The secondary system (2.18) can be graphically copied to the part, the conversion of the different symbols of the pinches, toto the multiply point, the coordinates of all the obedience of tasks, the bugocutnik of rozvias .

Umova (2.19) does not signify zmіnnyh meaning, but the region of permissible rozv'yakіv tasks and lie on the first quadrant of the coordinate system of a two-dimensional space. The numerical function of the tasks of linear programming is geometrically interpreted as a parallel of straight lines with 1 x 1 + s 2 x 2 = const.

Skorystaemsya for gorichnogo rozvjazannja tasks of linear programming by authorities, guidance in § 2.5:

Yakscho the task of literary programming is an optimal plan, then the extreme value of the principle function is nabuvaet in one of the vertices of the banyakutnik rozv'yakiv. Yaksho z tsilova funktsiya reach the extreme znachenny bilsh yak in one of the tops of the bagatoknika, then you can reach yogo and in the best way, at the top of the line.

Otzhe, rozv'yati problem litnogo programvannya graphically means to know taku top bahatokutnika rozv'yakiv, in the result of the addition of coordinates in (2.17), the linear function is nabuvae naybіlshogo (namenshogo) znachennya.

The algorithm of the graphical method of rozvjazuvannya tasks and linear programming is stored in such crocs:

1. Buduemo priimi, rivnyannya yakih distaemo zamenoyu v obmenenney zadachi (2.18), signs of nerves on the signs of the cities.

2. Viznachaemo pivploschini, scho vidpіdіayut kozhnomu obmezhennu zadachi.

3. Known bugakotkatnik rozv'yakіv problemy lennyi programvannya.

4. The future vector , That is, we set the value of the value of the function of tasks.

5. It should be straight with 1 x 1 + with 2 x 2 = const, perpendicular to the vector .

6. Ruhayuchi is straight with 1 x 1 + with 2 x 2 = const in the straight line of the vector (For the tasks of maximization) abo in the protivolezhnomu (for the tasks of the ministry), the peak of the bug-carrier of roses is known, the function of the trick is gaining an extreme value.

7. Viznachaemo coordinate of the point, in the yakі tsilova function, the maximum (minimum) value is obtained, and the value of the value of the function in the center is calculated.

In the case of applying the graphical method for rozvjazuvannya tasks lennyi programvannya mozhny so vikipki:

1. Tsіlова functіія gaining the maximum value in the Ідиній вершині A bugakutnika rozv'yakіv (Figure 2.5).

2. The maximum value of the value function can be reached in the AV arithmetic system (figure 2.6). The task of literary programming is alternatives to optimal planning.

3. The task of linear programming is not optimal: the current function is not affected (Figure 2.7), the system of intermediate tasks is not connected (Figure 2.8).

Fig. 2.5 Fig. 2.6.

Fig. 2.7. Fig. 2.8

4. The task of linear programming is an optimal plan for unobservable areas of permissible rozvozyv (Figure 2.9 and 2.10). In Fig. 2.9 for precision In the maximum, in Fig. 2.10 at the point A - the minimum, in Fig. 2.11 zabrazheno, yak y raz unobserved areas of permissive plans tsilova function mozhe gaining the maximum amount of the minimum value for the sake of accuracy.

Fig. 2.9 Fig. 2.10

Rozv'yazuvati graphical method can be takozh tasks lennyi programvannya n -virnyy spaciousness, de , Yakzczo in the case of systems of problems of problems, up to sistemi rivnyan shlyom entering dodatkovyh zmіnnikh kilkist zmіnnih n n dvі bіlsha, nіzh number of m , m , tobto .

Todi, yak vidomo z course obshchei matematiki, mozhna dvі z n zmіnnikh, napriklad x 1 ta x 2, vibrotiv yak vіlnі, and інші m зробити basic and іразити through вільні. It is permissible, but it is bound together. Otrimaema Рівнянь вигляду:

Оскільки всі значення , Then makut vikonuvatis umvi:

,

(2.19.1)

Rozglyanemo, you can geometrically and geometrically. Візьмемо, наприклад, першу з них:

Having taken the value of x 3 to its own extreme value - zero, otrimaemo rivnyannya:

.

Це рівняння прямої. For such direct , On one side of the river , And for a friend - . Відмітимо that side of straight , De .

In the analogy of the course, I will do everything in a straightforward manner: ; ; ...; І Відмітимо для кожної з півплощину, де відповідна змінна більше нуля.

With such a method, we can subtract n - 2 straight lines from two coordinates ( , ). Skin of them viznachaє pivploschinu, de vikonuetsya umova . Partial plains in Nalezhit vodnochas vsim pivploschinam, utvomuyuchi bugatokutnik permissible rozv'yaziv.

It is permissible, but in tasks it is necessary to know the maximum value of the function:

.

Pistavstavshi virazy for , , , ...; З (2.19.1) у цей functііонал, зведемо подібні доданки іририємо вираз лінійної функції F всіх n змінних лише через дві вільні змінні That :

,

De - a member of the Whole, I did not bog in the covetous function.

Obviously, the linear function Reach its maximum value for the same value That , Nd d . Otzhe, procedure vidushkanya optimal plan z multiplane permissibles dalі zdіysnyuetsya behind the algorithm for vypadku two zmіnnih.

Rozv'yati graphical method of solving the problem of linear programming

.

Rozvjazannya . Маємо n = 7 - кількість змінних, m = 5 - сількість омежень. Vibermo yak vіlnі zmіnnі x 1 tak h 2 i virazimo through them all basic basics. З першого рівняння маємо:
(2.19.2)

З third рівняння:

, (2.19.3)

But from the fourth:

. (2.19.4)

Підставляючи (2.19.2) in the friend рівняння системи і (2.19.4) в останнє, розв'язуємо їх відносно х 4 та х 7. Отримаємо:

;

.

After the algorithm, take x 1 = 0 and x 2 = 0 - coordinate axis; The interspaces are directly visible, taking x3 = 0, x4 = 0, x5 = 0, x6 = 0, x7 = 0. The bagatokutnik of admissible rozvozyv is shown in Fig. 2.12.

Fig. 2.12

We know the functional function, which is vitrified through x 1, x 2. For the known digits for x3 , x4 , x5, x6, x7, through xmlnxxxxxx2, it is possible for the functionally assigned subunits, otrimayo : . Відкидаючи вільний member, маємо: . Vector will be (-5, -2), perpendicular to the bottom - straight F ' . Ruhayuchi straight F ' into the strait, the protuberance (Neobhіdno know the minimum value of the function F ), the point is the minimum - A (Figure 2.13).

Fig. 2.13

At the point A, the two lines are interchanged straight: x 6 = 0 and x 7 = 0. The annum, for the coordinate of the coordinates, you need to have the system rivnyan:

Rozv'yazkom sistemi - = 8.5; = 5. The values ​​of the values ​​for the visas, the best values ​​of the basic numbers:

= 0.5; = 16.5; = 17.5; = 0; = 0.

The written value is That In the linear function F, the value of the function is subtracted:

.

2.7. Buttons rozv'yazvanya tasks graphical method

Roshglyanemo zastosuvannya graphical method for rozv'yazvannya deykih ekonomichnih tasks.

Фірма спеціалізується на виробництві офісних меблів, зокрема вона випускає два вид збірних книжкових полиць - А та В.. Полиці обох видів виготовляють на верстатах 1 та 2. Triviality of the detail block of one polyester model is given in the table. (2.4).

Table 2.4

TRIVALTY OF THE VIGITARIAN BOOK POLICE

Прибуток фірми від реалізації однієї полиці моделі А дорівнює 50 у. And model B - 30 at. about. Вивчення ринку збуту показало, що тижневий попит на книжкові полиці моделі А ніколи не перевищує попиту на модель In bіlsh yak for 30 oditnits, and sales politsі modelі In the 80-odyshnitsy not to perish.

It is necessary to vignify the vibrokittyws' contacts with books of two models, which maximize the surplus. For the whole series, the economical and mathematical model of the tasks set up is to be solved graphically.

Pobudova mathematical model . Змінними в моделі є тижневі обсыги виробництва книжкових полиць models А та В. В. Нехай х 1 - кількість полиць моделі А, виготовлених фірмою за тиждень, and х 2 - кількість полиць model B. В. Цільова funktііya zadachi - at the most with the reception of companies in the realty of production. Mathematically, it's like:

.

Omezhennya zadachi vrahovuyut trivalist robot verstativ 1 to 2 for vygonovlennya produktsii that popit politsy riznikh models.

Intermediate for trivalist robot verstativ 1 ta 2 muyut kind:

For verstat 1:

30 х 1 + 15 х 2 ≤ 2400 (хв);

For verstat 2:

12 х 1 + 26 х 2 ≤ 2160 (хв).

The obmenzhennya on popit record as follows:

Х 1 - х 2 ≤ 30 та х 2 ≤ 80.

Zagalom ekonomiko-mathematica model of tasks can be written as follows:

Max Z = 50 X 1 + 30 X 2 (2.20)

For the mind:

Tsya ekonomiko-mathematicheskaya model - the model of problems of the linear program, the mesh lishhe dvі zmіnnі, і to that mozhe bouti rozvjazana it is graphical.

Rozvjazannya . The first krok zgіdno z graphіchnim method polagae in the geometric zabrazhennyi permissive planіv problems, tobto u viznachennі takoi oblastsi, de vodnochas vikonuyutsya vsi obmezhenna model. It is replaced by signs of nerves on the signs of strict rivnost і and induce the graphs of the direct (figure 2.14). Skin from the forward straight lines below the plane by the coordinate systems on the two faces. Coordinate point odnієї з піввплощин задовольняють розглядувану нерівність, and іншої - ні. Щоб визначити необхідну півплощину (in Figure 2.14 її is directly known to the page), take it to the yak point and pereviriti, chi zadovolnyayut її coordinate zachazhene obmezhennia. Yaksho zadovolnyayut, then pivposhchina, in a vibrant vibe point, geometric zobrazhennyam nervivnosti. Іnakse to such zobrazhennyam є інша півплощинащина.

Fig. 2.14

Умова невід'ємності змінних х 1 ≥ 0, х 2 ≥ 0 between the region of admissible plan problems and the first quadrant of coordinate systems. Переріз усіх піввплощин визначає area permissible planів задачі - sixakutnik OABCDE . Coordinate be-yoga yogo point zadovolnyayut system obmezhen zadachi i umowu nevіd'єmnosti zmіnnih. I set the task to be rozv'yano, yakzchemo zmozheto vidshukati taku point bahatokutnika OABCDE , in ykіy tsil'ova z function zabira най naybіlshogo znachennya.

For whomever is the vector , The coordinates of what I mean - in the case of problems in the function of tasks. Vector We must find the coordinates of the directions to the point with coordinates ( x1 = c1; x2 = c2). In our problems vector . Він задає прям збільшення значен цільової функції Z , and the vector, the protruding yoma, is straightforward.

Pobuduєmo lіnіyu, shоо відповідає, наприклад, Z = 0. If it's straight, it's 50 x 1 + 30 x 2 = 0, which is perpendicular to the vector I pass through the coordinate cob. Oskilki in danyomu priemi neobhіdno viznachit naybіls znachennja tsil'ovoy funktsii, then peresuvatimem straight 50 x 1 + 30 x 2 = 0 in parallel samі sobі zgіdno z volnomu vectora Dots, docks are not viznachimo top bugakotkatika, yaka vidpіdієe optimal plan tasks.

Fig. 2.14 it can be seen that the rest of the straight point of the direct function of the bagatellite OABCDE is the point C. Coordinate the point - the optimal plan of tasks, tobto such vibrokittyva knizhkovt polits vidiv A and V, scho obezpechuyut maximum pributku vid їh realizatsii for giving minds.

The coordinate of the point C by the rovvian system (2.17) and (2.18):

Звідси маємо: х 1 = 50; X 2 = 60.

The annulus, X * = (50; 60);

Tse means, scho koli firma schotizhnya vigotovlyatime 50 zbirnih knizhkovyh polits model And the 60 - model B, then vonima otrimaє maximal pributok - 4300 y. about. Tse neobyvatime mnogo vikoristanna tizhnevikh resursiv robochogo chasu verstativ 1 1 2.

For small ptahofermi potrybno rozrauvaty optimal kormovy ratsion on 1000 kurchat, yakih virochyut 4 to 8 tizhnevogo visku. Nehtoyuchi tim, scho potyzhnevі vitrati kormmiv for kurchat popoljat vid їhnygo vіku, vvazhatimemo, scho for 4 tizhni kurcha spizhivaє not less than 500 g sumіshі. Крім цього, кормовий раціон курчат має задовольняти певнні вимоги щодо поживності. It is possible to formulate the vimogy of the requested vigil, the beruchi up to the respect of the lisha, the life of the rechovin: bilok i klitkovinu, sho mistyatsya at the fodder of the two species - grains and soyevikh beans. Vmist zhivnovnyh rechovin u kozhnomu kormy i tak vartim menesso tabl. 2.5.

Table 2.5

Pozhivnosti TA VARTY KORMIV

Ready to feed the sum of the sum of money, not less than 20% of the price and not 5% of the price.

Viznachiti Masu kozhny z dvuh vidіv kormіv, scho utvoryuyut kormovu sumіsh mіnimalnogo varsty, vodnochas zadovolnyayuchi vimogi before zagalnoy masi kormovoy sumyushi ta її zhivnovnosti.

Pobudova ekonomiko-mathematical model. Nekhay x 1 - cereal grain, and x 2 - soyevih bobiv (in kg) for the preparation of feed sushi.

Загальна кількість суміші х 1 + х 2 має становити понад 500 кг, тобто

X 1 + x 2 ≥ 500.

Розглянемо обмеження чодо поживності кормової суміші.

Суміш має містити не менш як 20% білка:

10 х 1 + 50 х 2 ≥ 20 ( х 1 + х 2),

And takozh not more than 5% cotton:

2 x 1 + 8 x 2 ≤ 5 ( x 1 + x 2).

A loophole mathematical model of problems and optimization of food ration is such a vigil:

Min Z = 0.40 x 1 + 0.90 x 2 (2.26)

For the mind:

(2.30)

Rozvjazannya . A graph of the tasks is given in Fig. 2.15. The multiplicity of admissible її rozv'yazіv is not mixed. For the vector = (0,4; 0,9) can scale the scale, for example, = (200; 450). Naimenshogo znachennja tsil'ova funktsіya Z reach the point A , scho lie on the margins of the borderline, yakі vidpovidayut to the alternatives (2.27) and (2.28). Viznachimo її coordinate:

The annunciator, X * = (375; 125); Min Z = 0.4 • 375 + 0.9 • 125 = 262.5.

Zgіdno z vіdshukanim optimal plan of problems, in order to give 500 kg of feed amount of the minimum wage (262.50 USD), take 375 kg of grain and 125 kg of co-beans. For such a sfіvvidnoshennya componentіv kormovoy sumyshі vimogi up to її zhivnovnosti vikonuvatimutsya:

0,10 • 375 + 0,50 • 125 = 100 kg білка, що to become рівно 20% of the gross amount of money;

0,02 • 375 + 0,08 • 125 = 17,5 kg of clay in the feed of the sum, but to become 3.5% її masi і not transplanted 5%.

Фірма виготовляє з одного вида сировини two products А та В, що продаються відповідно for 8 та 15 копійок за упаковку. Rinok zbutu for cutaneous from them practically non-cutting. Syrup for product A is crushed with verstat 1, and for product B - with verstat 2. Potiim offspring products are packed in the factory. Scheme vibrobitntsva product A and B is shown in Fig. 2.16.

Fig. 2.16. The layout of the products

The price is 1 kg of sirovini - 6 kopiyok. Verstat 1 crumbles for an hour 5 tons of sirovini, and verstat 2-4 tons of sirovinium from it, it becomes 10% and 20%. Verstat 1 can pratsyuvati 6 year on the day, prichomu yogo vicaristan koshtuy 288 UAH / year; Verstat 2-5 year on the day, sho koshtue 336 UAH / year.

Masa to product A in one package is 1/4 kg, and product B is 1/3 kg. The factory can pratsyuvati 10 years a day, shogodolini packing 12 000 oditnits product Ao 8,000 odnitsyn product V. Vartizh roboti in the course of 1 year to become 360 ​​UAH.

It is necessary to adhere to the meaning of x 1 t x 2 obyagiv vikoristan sirovini for vigotovlennya produktiv A ta V (tons), yaki zabezpechuyut naybіlshy schodennny pributok firmi.

Pobudova ekonomiko-mathematical model . Nekhay x 1 ta x 2 - vidpovidno sirovini, vikoristovuvani vigotovlennya product A and B in one day, that is,

Recordable obmezhennia tasks. Zgіdno z umovoi obmezhenimi resources є trivalvost vikoristan verstativ 1 і 2, and takozh trivalist roboti factory z pakakuvannya produktiv And that V.

1. The mockery of the Vicar-verstat 1.

Economical zmist ttsogo obmezhenna such: actual trivality vikoristan verstat 1 z obobki sirovini vigotovlennya product A mae not perevischuvati 6 year, tobto:

Mathematically tse write down like this:

X 1/5 ≤ 6, abo x 1 ≤ 30.

2. Obmenzhennia shodo vikoristanna verstata 2 virazim analog:

X 2/4 ≤ 5, abo x 2 ≤ 20.

3. Obmenzhennya shodo trivalosti roboti factory z pakakuvannya produktiv A ta V.

Economical zmist ttsogo obmezhennia as such: the actual number of hours, vitrachenogo on packaged products A and B, mae not perevischuvati 10 yrs a day:

Mathematically tse write down like this:

Abo:

0.3 x 1 + 0.3 x 2 ≤ 10,

3 x 1 + 3 x 2 ≤ 100.

Pobuduєmo tsil'ovu funktsiu tasks. Прибуток фірми дорівнює різниці між доход від реалізації виготовленої продукції та витратами на її виробництво.

1. Дохід від виробництва продуків А та В визначається так:

Abo

.

Загальний дохід дорівнює 288 х 1 + 360 х 2.

2. Vitrate on sirovin viznachaemo yak zagalnu kilkіst sirovini in tons, vikoristivovanoi for viribnitskva produktiv And that in multiplied by vartit 1 ton of sirovini in hryvnias:

60 ( х 1 + х 2) = 60 х 1 + 60 х 2.

3. Witraty, assigned to vikoristani verstativ 1 1 2, viznachaemo mozhennyam actually tristovalov robot verstat z obobki sirovini na vartist 1 year robot vidpovidnogo verstat:

.

4. Vitrati, pozhyanni z pakakuvannyam produktiv A ta V, dorivnyuyut dobutku de facto trivalosti robot factory (0,3 x 1 + 0,3 x 2) for vartit 1 year її roboty, yaka become 360 ​​UAH:

360 (0.3 x 1 + 0.3 x 2) = 108 x 1 + 108 x 2.

Beruchi up to the respect of all the warehouses of the rules of function, you can write mathematics viraz pributku fyrmi per day:

Z = (288 x 1 + 360 x 2) - (60 x 1 + 60 x 2) - (288/5 x 1 + 84 x 2) - (108 x 1 + + 108 x 2) = 12/5 • ( 26 x 1 + 45 x 2).

Otzhe, maemo such a residual note of the economy-mathematical model:

Max Z = 12/5 • (26 x 1 + 45 x 2) (2.31)

For the mind:

(2.35)

Unfettered at the collapsed modular process, mathematically, the problem is very simple and easy to straightforward graphically.

Rozvjazannya. Graph graph of tasks and drawings 2.17.

The region of permissible plans, that is, the system of tasks, is the bagatoclete ABCDO . Найбільшого значення цільова функція досягає у вершині В. Координати цієї точки визначаються розв'язанням системи рівнянь:

Оптимальний план задачі: Х * = (40/3; 20); max Z = 2992 грн.

Отже, для того, щоб отримати найбільший денний прибуток 2992 грн, фірма має обробляти 40/3 тис. кг сировини, виробляючи продукт А, і 20 тис. кг — виробляючи продукт В. За такого оптимального плану випуску продукції верстат 2 працюватиме 20/4 = 5 год на день, тобто з повним навантаженням, а верстат 1 працюватиме лише 40/15 = 2 год 20 хв щодня.