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

Mathematics programmers - Nakonechny S.I.

5.8. Transport problem for the critical hour

For active minds, for example, for transported products, scho shvidko psue; Materіalіv for avarіynih ta rіtіvnih robіt тощо vаrtість transport mе odnorodryadne znachennya, and on pіshe mіsce vіdat zavdanіa mіnіmіzіtsії the hour, the length of yakogo zdіysnjutsya vsі perezveznya. So it's a transport problem for criterion hour .

Nekhay is given m points in the post-assignment A 1, A 2, ..., Am in the reserve stocks Odnitsyn producty t n spizhivachiv , The consumption of some becomes , Prichomu .

Significantly through - a product of production, and be transported to the first post-holder of the j- th dispute.

Set times for hours On the transfer of a veterinarian Before skin resuscitation , І to be admitted, sho stinks not to lie in the range of transport .

Need to know the optimal plan for transporting , Scho pleas for pleasure:

; (5.39)

. (5.40)

In addition, the hour T , a so-called vitrachachimetsya on all transport, buv bi minimum.

So yak vosi pereveznanya zakincchuyutsya in that moment, if zakynchuyutsya naidovshe of them, then the maximum value of the syshm can be meaningful , It is not necessary to transport them ( ): .

Отже, критерієм оптимальності планну є мінімальна trіvalіst здійснення всіх перевезень, scho formally note this:

. (5.41)

Zauvazhimo, scho tsya problem is not the task of the linear program, osklіki її tsіl'ova funktsіya (5.41) not і лінійною functцією від змінних . However, for rozv'yazuvannya transportnoy tasks for a critical hour, you can zastosovuvati ti sami method rozv'yazannya, sho buli sygljagnuti for transportnoi problemyi linnogo programvannya.

Rozglyanemo algorithm rozv'yannya formulated tasks, uchruntuyutsya poslіdnomu rozv'yazuvannі a number of additional tasks, rozgljanutih in ugorskomu method.

1. Knowing the minimum element of the matrix of trivialities. Significantly, the minimum element of knowledge on the first cross, through . Клітини транспортної таблиціі, які відповідають мінімальному елементу, тобто де = , Vvazhayutsya vidkritimi for transport, todi yak usi іnshі, de > , They will be buried for them.

2. Call up the doodtack task with a designated multiple of graves for the transportation of clay . Yaksho після цього кроку задовольняються умоми задачі (5.39), (5.40), then the optimal plan is known і , And yakshcho ni, then go to the third crook.

3. Analogously to the first croc, the znovu know the minimum element of the middle of the elements Matrix trivalovoy transport T , yakі vidpovidayut klitinam, zaboronenim for transport. Leave him an element of size . Тоді всі ті клітини, for some = , Приєdіdite up клітин, відкритих для перевезень.

4. Analogously to the other crook, the new problem should be supplemented with a task with a multiple clayin, І переііряють, chіkіvuyutsya umovi (5.39), (5.40). Yaksho stinks, then the plan of the optimal plan . Якщо ж ні, то дії, аналогічні to the descriptors, repeat, will not know the optimal plan.

Algorithm for scintillation, reporting for balance Table transporting without grave clitin zavzhdi mozhe bouti zapovnena, and the algorithm zabezpechuє in raz izobi ​​zvilennenya vseh klіtin vіd zaboroni v perveveznanya.

Do not forget the transport tasks assigned to the table (Table 5.28):

Table 5.28

1. The minimum element is known . In the Differential 1, the yogo is known through .

2. Rozv'yazuєmo dopomіzhnu task, de zaboronenimi for transporting є vsі klіtini, for some > (For Table 5.29 we compare the size of the walled clay tiles).

Table 5.29

The task is unleashed, the plan is not optimal.

3. You know the minimum element of the middle of the clay, but it is fenced off for transport. The approaching minor element is doubled by two. The oil, .

4. Приєднуємо до відкритих для перевезень клітин ті, for яких , І знову розв'язуєємо допоміжну a task.

Table 5.30

Otrimanie rozvjazok (Table 5.30) is not optimal.

5. Vibirayemo approaching the minimum element: .

6. I will definitely come to the task:

Table 5.31

Tse takozh does not give an optimal rozvozyu (Table 5.31).

7. Vibiraemo minor element .

8. The problem is:

Table 5.32

Umovi optimality in Table. 5.32 vikonuyutsya, otzhe, tse an optimal plan. Call min T = 4.