19817

Судження за допомогою оцінки клітини про її вигідність чи невигідність

Доклад

Информатика, кибернетика и программирование

3.Судження за допомогою оцінки клітини про її вигідність чи невигідність. 1. Перевіряють виконання необхідного і достатнього умови розв'язності задачі. Якщо завдання має неправильний баланс то вводять фіктивного постачальника або споживача з відсутніми запасами або за

Украинкский

2013-07-17

27.5 KB

0 чел.

3.Судження за допомогою оцінки клітини про її вигідність чи невигідність.


1. Перевіряють виконання необхідного і достатнього умови розв'язності задачі. Якщо завдання має неправильний баланс, то вводять фіктивного постачальника або споживача з відсутніми запасами або запитами і нульовими вартостями перевезень.
2. Будують початкове опорне рішення (методом мінімальної вартості або яким-небудь іншим методом) і перевіряють правильність його побудови, для чого підраховують кількість зайнятих клітин (їх має бути m + n-1) і переконуються в лінійної незалежності векторів-умов (методом викреслювання).
3. Будують систему потенціалів, що відповідають опорному рішенням. Для цього вирішують систему рівнянь + = при> 0. Для того щоб знайти приватне рішення системи, одному з потенціалів (зазвичай тому, якому відповідає більше число зайнятих клітин) задають довільно деяке значення (частіше нуль). Решта потенціали однозначно визначаються за формулами = - при> 0, (24)
4еслі відомий потенціал, і
= - При> 0, (25)
якщо відомий потенціал.
4. Перевіряють, чи виконується умова оптимальності для вільних клітин таблиці. Для цього обчислюють оцінки для всіх вільних клітин за формулами = + - і ті оцінки, які більше нуля, записують в ліві нижні кути клітин. Якщо для всіх вільних клітин 0, то обчислюють значення цільової функції, і рішення задачі закінчується, так як отримане рішення є оптимальним. Якщо ж є хоча б одна клітина з позитивною оцінкою, то опорне рішення не є оптимальним.
5. Переходять до нового опорного рішення, на якому значення цільової функції буде менше. Для цього знаходять клітину таблиці завдання, якій відповідає найбільша позитивна оцінка max {} =. Будують цикл, що включає до свого складу дану клітку і частина клітин, зайнятих опорним рішенням. У клітинах циклу розставляють по черзі знаки "+" і "-", починаючи з "+" в клітці з найбільшою позитивною оцінкою. Здійснюють зрушення (перерозподіл вантажу) по циклу на величину =. Клітка зі знаком "-", в якій досягається, залишається порожньою. Якщо мінімум досягається в декількох клітинах, то одна з них залишається порожньою, а в інших проставляють базисні нулі, щоб число зайнятих клітин залишалося рівним m + n-1. Далі повертаємось до пункту 3 алгоритму.


 

А также другие работы, которые могут Вас заинтересовать

23471. Слияние гласных в именных и глагольных формах 222.5 KB
  движение сверху вниз с чего откуда по чему под что куда а также место под которым находится ктолибо или чтолибо под чем где: κατὰ τῆς πέτρας Xenoph. промежуток времени в пределах которого осуществляется какоелибо действие в течение чего в продолжение чего при ком: κατὰ τὸν Πελοποννησίων καὶ Ἀθηναίων πόλεμον Herod. отношение соответствие или сообразность с чемлибо относительно чего в соответствии с чем сообразно чему по чему: τὸ κατὰ τοῦτον εἶναι Xenoph. ἀπέκτονα убивать умерщвлять коголибо асс.
23472. Слитные глаголы I спряжения 163.5 KB
  Спряжение глаголов на εω Образец спряжения φιλέω основа φιλη любить praesens indicativi activi singularis pluralis 1 φιλέω φιλῶ φιλέομεν φιλοῦμεν 2 φιλέεις φιλεῖς φιλέετε φιλεῖτε 3 φιλέει φιλεῖ φιλέουσιν φιλοῦσιν imperativus praesentis activi 2 φίλεε φίλει φιλέετε φιλεῖτε 3 φιλεέτω φιλείτω φιλεόντων φιλούντων infinitivus praesentis activi φιλέεν φιλεῖν1 imperfectum activi 1 ἐφίλεον ἐφίλουν ἐφιλέομεν ἐφιλοῦμεν 2 ἐφίλεες ἐφίλεις ἐφιλέετε ἐφιλεῖτε 3 ἐφίλεε ἐφίλει ἐφίλεον ἐφίλουν praesens indicativi medii passivi singularis pluralis 1...
23473. III склонение 218.5 KB
  При склонении имён третьего склонения к их основам добавляются окончания во многом сходные с окончаниями первого и второго склонений: число singularis pluralis падеж род m f n m f n nominativus ς ø ø ες ᾰ genetivus ος ων dativus ῐ σῐ accusativus ν ᾰ = nom. Ἄραψ gen. ὄρνις gen. ἐλπίς gen.
23474. III склонение. Основы на -ν 147.5 KB
  существительные имеющие асигматический именительный падеж с удлинением последнего гласного: ὁ ἡ γείτων gen. γείτονος сосед соседка ὁ ποιμήν gen. существительные с асигматическим именительным падежом распространившие конечный долгий гласный на все формы: ὁ ἀγών gen. ἀγῶνος собрание состязание борьба ὁ Ἕλλην gen.
23475. Aoristus (аорист) 107.5 KB
  а также при некоторых близких им по значению прилагательных и указывает на цену чеголибо за сколько достойный чего: πολλοῦ πωλεῖται продаётся за большие деньги ἄιος ἐπαίνου достойный похвалы ; τῶν πόνων πωλοῦσιν ἡμῖν πάντα τἀγάθ᾿ οἱ θεοί Xenoph. ᾐνιάμην говорить загадками выражаться туманно намекать на чтолибо асс. ἠκολούθηκα следовать за сопровождать коголибо чтолибо dat. ἠτύχηκα терпеть неудачу не достигать чеголибо gen.
23476. III склонение. Основы на заднеязычные (γ, κ, χ) 111.5 KB
  κόρα gen. αἴ gen. ὄνυ gen. Образцы склонения ὁ κόρα ворон ἡ αἴ коза ὁ ὄνυ ноготь коготь ὁ ἅρπα λύκος жадный волк основа κορᾰκ αἰγ ὀνῠχ ἁρπᾰγ singularis nominativus ὁ κόρα ἡ αἴ ὁ ὄνυ ὁ ἅρπα λύκος genetivus τοῦ κόρακος τῆς αἰγός τοῦ ὄνυχος τοῦ ἅρπαγος λύκου dativus τῷ κόρακι τῇ αἰγί τῷ ὄνυχι τῷ ἅρπαγι λύκῳ accusativus τὸν κόρακα τὴν αἶγα τὸν ὄνυχα τὸν ἅρπαγα λύκον vocativus ὦ κόρα ὦ αἴ ὦ ὄνυ ὦ ἅρπα λύκε pluralis nominativus οἱ κόρακες αἱ αἶγες οἱ ὄνυχες οἱ ἅρπαγες λύκοι genetivus τῶν κοράκων τῶν...
23477. III склонение. Основы на губные (β, π) 141 KB
  Расстояние от одного места до другого как далеко проходимое пространство какое расстояние а также дорога по которой ктолибо или чтолибо движется каким путём6 обозначаются в греческом языке винительным падежом без предлога accusativus spatii винительным протяжения в пространстве: ἀπέχει ἡ Πλάταια τῶν Θηβῶν σταδίους ἑβδομήκοντα Thuc. ᾐδέσθην стыдиться совеститься; чтить уважать коголибо асс. ἀπέχω быть удалённым отстоять находиться от чеголибо на расстоянии чеголибо gen. ἐβλάβην вредить комулибо чемулибо ...
23478. III склонение. Основы на переднеязычные (δ, τ, θ) 191 KB
  ἐλπίς gen. ἐσθής gen. κόρυς gen. Образцы склонения ἡ ἐλπίς надежда ἡ ἐσθής одежда ἡ κόρυς шлем ὁ τάπης ковёр основа ἐλπῐδ ἐσθητ κορῠθ τᾰπητ singularis nominativus ἡ ἐλπίς ἐσθής κόρυς ὁ τάπης genetivus τῆς ἐλπίδος ἐσθῆτος κόρυθος τοῦ τάπητος dativus τῇ ἐλπίδι ἐσθῆτι κόρυθι τῷ τάπητι accusativus τὴν ἐλπίδα ἐσθῆτα κόρυν κόρυθα τὸν τάπητα vocativus ὦ ἐλπί ἐλπίς ἐσθής κόρυ κόρυς ὦ τάπη τάπης pluralis nominativus αἱ ἐλπίδες ἐσθῆτες κόρυθες οἱ τάπητες genetivus τῶν ἐλπίδων ἐσθήτων κορύθων τῶν ταπήτων dativus...
23479. Coniunctivus (сослагательное наклонение) 131.5 KB
  Все времена сослагательного наклонения кроме перфекта впрочем малоупотребительного1 образуются посредством добавления к соответствующей основе глагольной или настоящего времени долгих тематических гласных ω η2 служащих показателем сослагательного наклонения и первичных личных окончаний при соединении которых получается следующий набор практических окончаний:3 activum medium singularis pluralis singularis pluralis 1 ω ωμεν ωμαι ωμεθα 2 ῃς ηις ητε ῃ ηαι ησαι ησθε 3 ῃ ηι ωσιν ηται ωνται Coniunctivus...