30942

Математичне програмування

Шпаргалка

Математика и математический анализ

Введемо в розгляд нове поняття — визначник квадратної матриці порядка n .Для цього попередньо покажемо, як шукаються визначники І — 3 порядків, тобто визначники квадратних матриць 1—3 порядків.Визначник першого порядку — це сам елемент аll: Визначником другого порядку називається число

Украинкский

2013-08-25

153.39 KB

4 чел.

  1.  Матриці та дії над ними.

Матрицею (або m × n-матрицею) називається прямокутна таблиця m × n чисел, розташованих вт рядках і n   стовпцях:

Аm x n = ,

де а., називаються елементами, i - номер рядка, j - номер стовпця, тобто а., знаходиться на перетині i-ого рядка та j-го стовпця.Матриця називається прямокутною, якщо mn, і квадратною, якщо m = n. В останньому випадку число n називається її порядком.Матриці називаються рівними, якщо вони мають однакову розмірність (число рядків і стовпців співпадають) і всі відповідні елементи рівні між собою.Нульовою (нуль-матрицею) називається матриця О, псі елемент якої нулі.Транспонованою відносно матриці А називається матриця А' яка отримується із А шляхом заміни в ній місцями рядків і стовпців:

Операція переходу від А до А'  називається транспонуванням матриці А. Перевірити: (А')'= А.Діагональними елементами квадратної матриці називаються елементи, обидва індекси яких рівні між собою. Вони розташовані на так званій головній діагоналі.Діагональною називається квадратна матриця, всі елементи якої поза головної діагоналі дорівнюють нулю.

Одиничною називається . діагональна матриця Е, всі діагональні елементи якої дорівнюють одиниці.Добутком матриці А на довільне число α називається матриця.виду  αА = {αа ij}і = ; j=. Сумою (різницею) двох   m х n матриць А={аij} і В={b ij;} називається матриця   A±В = {a ij ± b ij }і=.; j=.Добутком m × s - матриці A на s х n - матрицю В справа називається m х n -матриця С = А ∙В = ; j=,де сij дорівнює сумі добутків елементів i-го рядка матриці А на відповідні елементи j-го стовпця матриці В: cij = аijbij + аi2 + …+ainbnj.Вектором-рядком називається 1 х n — матриця. Вектором-стовпцeм називається n х 1 — матриця.1’

2.Визначники та їх властивості.

Введемо в розгляд нове поняття — визначник квадратної матриці порядка n .Для цього попередньо покажемо, як шукаються визначники І — 3 порядків, тобто визначники квадратних матриць 1—3 порядків.Визначник першого порядку — це сам елемент аll :Визначником другого порядку називається число

                                                                        В (1) добуток елементів основної діагоналі береться із знаком +, а побічної діагоналі із знаком -.Визначник третього порядку — це число, що знаходиться за правилом

Запам'ятати формулу (2) важко, проте існує, просте правило трикутників, яке дозволяє легко відтворити (2). Позначивши елементи матриці точками, з'єднаємо прямолінійними відрізками ті з них, які дають доданки (2). Тоді отримаємо символічне правило трикутників.Обчислення визначників порядку n ≥ 4 можна звести, як покажемо нижче, до знаходження визначників другого і третього порядків.В якості загального означення визначника n-го порядку візьмемо таку теорему Лапласа: Визначник п-го порядку дорівнює сумі добутків елементів довільного рядка (стовпця) на їх алгебраїчні доповнення:

 ai1Ai1 + ai2Ai2+ …+ ain Ain (= aij Aij  + … +aij Aij + …+ anj Anj)          (3)

Користуючись (3), знаходження визначника n-го порядку можна звести до знаходження визначників (л -1)-го порядку. Очевидно, що об'єм обчислень значно скоротиться, якщо деякі з елементів 1-ого рядка (стовпця) дорівнюють нулю. Цього можна добитися, використовуючи властивості визначників, до розгляду яких переходимо:

1.   |А| = |А<|-

2. Якщо у визначнику поміняти місцями які-небудь два рядки (стовпці), то він змінить лише знак.

3. Спільний множник елементів рядка (стовпця) можна виносити за знак визначника.

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

5. Якщо всі елементи деякого рядка (стовпця) складаються із Двох доданків, то визначник дорівнює сумі двох визначників, в одному з яких елементами цього рядка (стовпця) є перші доданки, в другому — другі, а решта елементів такі ж, як і в даному визначнику.

6. Визначник дорівнює нулю, якщо елементи яких-небудь двох рядків (стовпців) його пропорційні.

7. Визначник не зміниться, якщо до елементів якого-небудь рядка (стовпця) додати відповідні елементи другого рядка(стовпця), помножені на одне і те ж число.

Доведення наведених властивостей проводиться з використанням рівності (3).

3.Обернена матриця.

Означення. Квадратна матриця А називається невиродженою або неособливою якщо |А| ≠ О і виродженою або особливою в протилежному випадку.Означення. Оберненою до даної квадратної матриці А називається така матриця А-1, що А-1А =АА-11=Е.Теорема. Для кожної невиродженої квадратної матриці існує єдина обернена. Можна довести, що   А-1 = | А|-1   , де     А   —  приєднана до А матриця, тобто матриця того ж порядку, елементами якої є алгебраїчні доповнення відповідних елементів матриці А' (транспонованої до А). Приклад. Знайти А ' , якщо   А =   . Переконатися, що А 'А =АА- ' = Е. Визначник дає інформацію про виродженість чи невиродженість тільки квадратної матриці. Разом з тим в ряді практично важливих випадків подібна характеристика суттєва і для прямокутних матриць. На цьрму шляху введемо такі важливі означення.Означення. Мінором к-ого порядку m х n — матриці (к ≤ min (m, n)).' називається визначник к х к -матриці, що одержується із елементів початкової матриці після викресленая довільних n  -к  стовпців іm-к рядків.Означення. Рангом матриці (взагалі кажучи, прямокутної) називається найвищий.порядок мінора матриці, підмінного від нуля. Отже, ранг невиродженої матриці А порядка n  дорівнює n: гang А=n. Самостійно знайти rаng А, якщо     А = .

5.  Предмет математичного програмування.

 Для будь-якої техніко-економічної задачі кожного рівня наприклад, керування роботою підприємства) характерними є багатоваріантність вибору тих чи інших рішень, а також наявність того чи іншого критерію доцільності прийняття чи відкидання рішень (наприклад, мінімізація собівартості, максимізація прибутку то що). Математичне програмування вивчає методи знаходження екстремальних (найбільших або найменших) значень функцій багатьох змінних, якщо на ці змінні накладаються деякі обмеження. При розв'язуванні будь-якої задачі економічного змісту із застосуванням методів математичного програмування необхідно: 1) побудувати математичну модель задачі і проаналізувати її адекватність економічній задачі; 2) з допомогою математичних методів знайти оптимальний (найкращий) розв'язок; 3) виконати економічний аналіз отриманих результатів і виробити практичні рекомендації якщо ж аналіз вказує на суперечливість результатів, то необхідно повернутися до п.1) з метою уточнення математичної моделі).

6.24.Найпростішіоматематичніомоделі математичного програмування

Побудова математичної моделі: Позначимо: хі - кількість одиниць продукції виду Пі, заплановано: до випуску (і=1,2); z - сумарний прибуток при реалізації запланованої виробничої програми. Для змінних x1, x2, очевидно, виконуються нерівності хі > 0, причому рівність для однієї із змінних відповідає випадку невиготовлення відповідного виду продукції. З'ясуємо структуру z: c1x1, - прибуток від запланованої кількості продукції П1, а с2x2 - прибуток від випуску запланованої кількості продукції П2. Тому з врахуванням мети виробника: Z= c1x1+ с2x2. Проте виробнича програма обмежується зверху наявними обсягами ресурсів. На шляху їх врахування відмітимо, що a1i - кількість одиниць сировини S1, , що витрачається на виготовлення запланованої кількості одиниць продукції виду Пi (і=1,2), тобто a11x1 +a12x2, - це сумарні витрати S1 на всю виробничу програму, а вони не можуть перевищувати існуючі запаси b1. Отже, a11x1 +a12x2 <=b1 Аналогічні нерівності отримуємо і для сировини виду S2 та S3. Остаточно в нас виходить так:

Перші три обмеження в системі (2) називаються основними, а два останні — обмеженнями на знак, природніми або економічними. Розв'язати задачу (1)-(2) означає знайти таку пару чисел (вектор) (х1, х2), яка б задовільняла системі нерівностей (2) і для якої цільова функція z набувала б максимального значення.

7.Класифікаціяозадачоматем.програмування

Задачі математичного програмування в залежності від виду моделі можна віднести до: ) лінійного чи нелінійного програмування (якщо змінні входять в цільову функцію та основну систему обмежень лінійно, то задача лінійного програмування, і нелінійного в протилежному випадку); 2) статичного чи динамічного програмування (в залежності від суттєвого входження в модель часу); 3) детермінованого чи стохастичного програмування (якщо всі параметри моделі — детерміновані величини, то задача детермінованого програмування, - якщо ж — випадкові, то стохастичного); Розгляд задач (1)—(2), (3)—(4),дозволяє зробити висновок, що вони є задачами лінійного статичного детермінованого програмування. Разом з тим, в умовах ринкової економіки прибуток на плановий період швидше є випадковою, а не детермінованою величиною. Тому, зокрема задачу про оптимальне використання ресурсів в повному об'ємі слід було б розглядати в загальному випадку як задачу стохастичного програмування. Проте навіть дослідження її в рамках детермінованого програмування приносить дуже цінну інформацію.

8. Стандартні форми задач лінійного програмування.

Існуючі методи розв'язування ЗЛП передбачають певні вимоги на систему основних обмежень, в силу чого розрізняють дві стандартні форми ЗЛП:

І-а — з обмеженнями-рівняннями (в такому вигляді розв'язуються задачі з допомогою універсальних методів, реалізованих на персональних комп'ютерах);

ІІ-а— з обмеженнями-нерівностями (використовується в теоретичних дослідженнях і для геометричної ілюстрації);

Лема 1. Будь-яка задача ЛП може бути приведена до рівносильної задачі ЛП, яка записана в 1-й стандартній формі. Лема 2. Будь-яка ЗЛП може бути зведена до рівносильної задачі, що має ІІ-у стандартну форму. Проілюструємо доведення цього твердження на прикладі: звести ЗЛП:

 = 2 , оскільки, зокрема, = 2 – 3 =  - 1,Отже, в якості базисних можна вибрати змінні х3, х4. Розв'яжемо систему рівнянь (12) відносно цих змінних методом . За умовою х3 > 0,  х4 > 0, тому праві частини рівнянь другої системи (13) невід'ємні:

      (13)

Виключимо з цільової функції (11) змінні х3, х4, підставивши в (11) (13):

z = 5+2х1 –х2 + 3(54-8х1-7х2) + 22  З х1- З х2 = 189-25х1 - 25х2

яка має II стандартну форму і рівносильна вихідній задачі (11)—(12). Відмітимо, що перевагою отриманої задачі є можливість знаходження її розв'язку графічним методом.

9.22.Основні властивості розв’язків задач лінійного програмування.

Множина розв'язків нерівності аі1х1 + аі2х2 b, (i = ) заповнює суцільно одну із півплощин, на які ділить площину гранична пряма аі1 x1 +ai2 Х2= b

Леми  1 та 2 дозволяють сформулювати:Властивість 1. Сукупність допустимих розв'язків задачі (])—(2) заповнює опуклий многокутник або є порожньою множиною.Означення. Оптимальним розв’язком задачі (])—(2)називається такий її допустимий план, на якому цільова функція (1) досягає екстремального (найбільшого або найменшого) значення.Властивість 2. Якщо задача (1)—(2) має єдиний розв"язок, то він знаходиться в одній із вершин многокутника допустимих розв'язків.

При доведенні властивості 2 суттєво використовується те, що многокутник допустимих розв"язків обмежений.Нехай многокутник — необмежена множина, наприклад, яка зображена на мал.1.Проведемо пряму x1 + х2 =?. Тоділдляозрізаного   многокутника справедлива    властивість 2. Для визначеності нехай цільова функція (1) максимізується. Якщо максимум досягається у вершині А1 або В1, то збільшення r приводить до збільшення цільової функції і в граничному переході отримано zmax = . Аналогічно розглядається випадок z min = - Зауваження. Властивості 1 і 2 залишаються в силі і для випадку п > 2. При цьому многокутник допустимих розв'язків стає опуклим м н о г о г р а н н и к о м    д о п у с т и м и х    р о з в ' я з к і в. Гранична пряма — площиною (n = 3) або гіперплощиною (n > 3), півплощина — півпростором, вершина многокутника — вершиною многогранника.Властивість 3. Якщо цільова функція досягає екстремального значення в двох сусідніх вершинах многокутника (многогранника) допустимих розв'язків, то вона досягає цього ж значення і в кожній точці ребра (грані-частини), що з'єднує ці точки.

10. Алгоритм графічного методу розв’язування задач лінійного програмування.

Графічний метод ґрунтується на геометричній інтерпретації ЗЛП і застосовується в основному при розв'язуванні задач в R2 і тільки деяких задач трьохмірного простору, оскільки в R3 досить важко побудувати многогранник допустимих розв'язків, що утворюється в результаті перетину півпросторів. Задачу ЛП в просторі розмірності, більшої від трьох, зобразити графічно взагалі неможливо. Якщо ж ЗЛП записана в І стандартній формі, система рівнянь якої містить n невідомих і m  лінійно незалежних рівнянь, то вона також може бути розв'язана графічним методом всякий раз, коли n і m  пов'язані співвідношенням n - m = 2. При цьому слід привести ЗЛП до ІІ-ої стандартної форми…(.в зошиті).

12.Ідея симплексного методу та його геометрична інтерпретація.

Якшо задача ЛП має канонічну форму, то для неї зразу можна виписати опорний план. Наприклад, задача (5)—(6) має такий (початковий) опорний план: Хоп. = (0; 0; b1; b2; b3). Тим самим визначається одна із вершин многогранника допустимих розв'язків. На перший погляд, достатньо перебрати всі опорні плани і серед них знайти такий, на якому цільова функція набирає екстремального значення. Проте задачі лінійного програмування, які доводиться розв'язувати на практиці, характеризуються великими числами m та n, а кількість опорних планів обмежена зверху числом

                                                Тому доцільніше було б вказати таку схему послідовного покрашення опорного плану, що при переході від одного опорного плану (вершини многогранника допустимих розв'язків) до іншого опорного плану (іншої вершини) отримується збільшення цільової функції при максимізації функції (1) і зменшення її при мінімізації функції (1). Саме такою схемою є симплексний метод, що дозволяє знайти оптимальний план, або вказати на необмеженість цільової функції на многокутнику допустимих розв'язків.

13. Алгоритм симплексного методу.

Сформулюємо алгоритм симплексного методу, використовуючи основну теорему про покращення опорного плану. При цьому компактність записів досягатиметься за рахунок роботи з так званими симплекc-таблицями по аналогії із формалізованою реалізацією методу Жордана-Гауса. Економістів цікавлять практичні рекомендації внаслідок проведеного аналізу. Тому в якості модельного прикладу візьмемо конкретну задачу про оптимальне використання сировини, числові дані якої наведені в таблиці.

Складемо математичну модель задачі:

Зведемо її до канонічної форми

де змінні  х3, х4, х5  —  кількість одиниць невикористаної сировини S1, S2,, S3 -  відповідно внаслідок випуску x 1 одиниць продукції П1, і  х 2одиниць продукції П2. 

Заповнення початкової симплекс-таблиці (перша ітерація)

Таблиця 1

              

В рядках 1—3 записані відповідні рівняння системи (12), при цьому спочатку права частина (в стовпці опорний план), а потім коефіцієнти при відповідних змінних. Така перестановка зумовлена зручністю виписування опорного плану безпосередньо із таблиці. В стовпці базисні невідомі (рядки 1—3) записані відповідні базисні змінні ху х4, ху тому решта змінних (х1, х2 ) — вільні. Отже, з початкової таблиці безпосередньо виписується початковий опорний план: Х(1) оп = (0; 0; 182; 316; 238). В нульовому рядку міститься інформація про цільову функцію: для зручності функція (11) розглядається формалізовано як рівняння z - 18х1 - 16х2 = О                                                                                                                                                             

Вмістиме клітинки "опорний план" в нульовому рядку — це значення, яке   набуває цільова функція на відповідному опорному плані. В даному випадку z(X(1))on) =18 ∙ 0+16 · 0 = 0. Надалі в наступних ітераціях необхідно слідкувати за цим значенням. Початковому опорному плану відповідає вершина многогранника допустимих розв'язків, а саме в одній з них цільова функція (11) набуває оптимального значення. Очевидно, що Х(1) оп не може бути оптимальним планом (проаналізуйте!). Цей якісний висновок узгоджується з таким твердженням, що є наслідком основної теореми. Критерій оптимальності опорного плану по симплекс-таблиці: Якщо цільова функція максимізується (мінімізується) і в нульовому рядку відсутні від'ємні (додатні) числа, за винятком стовпчика "опорний план", то опорний план є оптимальним. Аналогічні міркування приводяться і у випадку мінімізації цільової функції. Перш ніж покращувати опорний план, тобто переходити до іншого, на якому цільова функція    набере більшого (меншого) значення,  необхідно виключити випадок нерозв'язаності задачі (Z(max       = оо  ,Z min     = оо).  v   max '    mm .

14.21. Постановка транспортної задачі та її математична модель.

Деякий однорідний вантаж, зосереджений у т постачальників А1, А2,… , Аm в кількостях a1 , а2,…,am одиниць відповідно, необхідно перевезти n cпоживачам В1, В2,…Вn  в кількостях b1, b2,…, bn одиниць Відомаоматриц  вартостей перевезення одиниці вантажу від постачальника Аi до споживача Вj. Необхідно скласти такий план перевезень вантажів, який дозволить вивезти всі вантажі, повністю задовільнити потреби споживачів і сумарна вартість перевезень за яким буде мінімальною.Зауваження. Така постановка вимагає виконання рівності

                                                                Тобто сумарні запаси дорівнюють сумарним потребам Транспортну задачу, для якої виконується рівність (1) будемо називати закритою (з правильним балансом) і відкритою (з неправильним балансом) у протилежному випадку. Побудуємо математичну модель закритої транспортної задачі Позначимо через xij кількість одиниць вантажу, запланованого до перевезення від i-го постачальника до j-го споживача,z — сумарну вартість запланованих перевезень Для зручності умову задачі запишемо у вигляді таблиці (табл 1), яку надалі будемо називати транспортною сіткою При цьому постачальників скорочено позначимо літерою П, а споживачів — С                                                                            Таблиця 1

Пункти

відправлення

Пункти призначення

Запаси

Потреби

або

Знайдемо сумарну вартість запланованих перевезень Зокрема, сij — вартість перевезення одиниці вантажу відА1 до В1, а таких одиниць планується перевезти х11. Тому с11· х11- вартість запланованих перевезень від А1до В1. Аналогічно знаходяться вартості перевезень для кожної з клітинок Сума їх дасть z:

                                                                                   Систему обмежень отримаємо із умов задачі: а)  всі вантажі повинні бути вивезені, зокрема, сума всіх змінних будь-якою рядка дорівнює відповідному запасу вантажів,б)  всі потреби повинні бути задоволеними, тобто сума всіх змінних кожної колонки дорівнює відповідній потребі споживача.За змістом невідомих повинні виконуватися нерівності xij 0 для всіх значень індексів.Остаточно система обмежень набуває такого вигляду:

                                                                          Побудована математична модель являє собою задачу лінійного програмування Для існування оптимального плану задачі лінійною програмування достатньо непорожності множини допустимих планів і обмеженості цільової функції на цій множині Легко перевірити, що сукупність є                              є допустимим планом задачі (2)- (3), тобто множина допустимих планів непорожня.3 врахуванням рівнянь системи (3) можна отримати подвійну нерівність С1М≤ZС2М, справедливу для всіх допустимих планів, де С1 та С2 відповідно найменший І а найбільший елемент матриці вартостей перевезення вантажів.Таким чином, будь-яка закрита транспортна задача мас оптимальний план. В принципі, цей план можна було б знаходити одним Із аналітичних методів, розглянутих вище Проте такий підхід зумовив би великі розміри симплексних таблиць, адже чисто змінних дорівнює mn. А з другого боку, систему рівнянь (3) можна записати у векторно-матричномулвиглядіАХ=Ь,                                                   Де  А — (m +n)х (mn) - матриця, особливістю якої є те, що кожен Із елементів п є нулем або одиницею, причому кожна колонка матриці має лише по дві одиниці, решта елементів - нульові, а кожен рядок - n  або m одиниць, а решта — нулі.

15. Методи побудови початкового опорного плану транспортної задачі

Як і для симплексного методу, при розв'язуванні транспортної задачі необхідно мати початковий опорний план. В якості ілюстрації алгоритмів методів побудови початкового опорного плану розглянемо транспортну задачу з такими даними

Оскільки  = то робимо висновок, що дана транспортна задача закрита Побудуємо транспортну сітку для цієї задачі.Таблиия 2

Ідея діагонального методу (північно-західного кута) полягає в послідовному заповненні клітинок, починаючи з АД і завершуючи клітинкою А1В1.Отже, в клітинку А1 В1 запишемо мінімальне з чисел 150, 300 (проаналізуйте чому). В постачальника А, внаслідок цього залишиться 150 одиниць вантажу.

Рекомендуємо олівцем проставити прочерки в клітинках А2 В1 і А3 В1 (потреби В1 задоволені), а біля 300 справа записати залишки запасів в розмірі 150 од. Переходимо до заповнення клітинки А1В2, якій відповідають 150 од. запасів і 220 од. потреб. Знову мінімальне з цих двох чисел (150) заносимо в А1 В2, проставивши олівцем прочерки в А1В3 та А1В4 (запаси вичерпані)" і записавши під числом 220 залишок потреб 70 од. В напрямку, який визначає діагональ, переходимо до А2В2, в яку записуємо min(70, 230)=70, виставивши прочерк в А3 В2 закресливши залишок потреб під В2 і записавши справа від 230 залишок запасів 230-70=160. В клітинку А2В3, заносимо min (160, 280)= 160, виставляємо прочерк в А2В4, закреслюємо залишок запасів А2 (160), а під потребами В3 записуємо залишок потреб В3 в розмірі 120 од. В клітинку А3В3 записуємо min (120,320)=120, закреслимо 120 під потребами В3 і біля запасів А3 записуємо залишок запасів в розмірі 320-120=200 од. Нарешті, в клітинку А3В4 заносимо 200. Рекомендуємо здійснити перевірку правильності побудови опорного плану шляхом додавання величин перевезень по рядкам і колонкам - кожний раз необхідно отримати відповідну величину запасів або потреб. Після перевірки записи олівцем знищуються (табл.2). Охарактеризуємо отриманий опорний план. Заповненим клітинкам відповідають базисні змінні, значення яких дорівнюють вмістимому клітинки: х11=150, х12=150, ..., х34 =200, а порожнім клітинкам відповідають вільні змінні, значення яких дорівнюють нулю (х1314=...=х32=0). Суттєвою характеристикою кожного опорного плану є його виродженість чи невиродженість.оОзначення.оОпорнийоплан називається невиродженим, якщо число базисних змінних (заповнених клітинок) дорівнює рангу матриці обмежень (системи обмежень), тобто m + n-1, і виродженим, якщо це число менше від m + n-1. В нашому випадку  = 3 + 4 - І = 6 і число базисних змінних також дорівнює 6. Отже, початковий опорний план невнроджений.

Зауваження. Якщо при побудові початкового опорного плану або в ході його покрашення отримується вироджений план, тоді його формально слід звести до невиродженого. проставивши нулі в такій кількості вільних клітинок, щоб сумарно отримати число заповнених, рівне рангу системи обмежень. Ігнорування цією рекомендацією не дозволяє, взагалі кажучи, знайти оптимальний план (див. наступний пункт). Вартість перевезень згідно з побудованим планом отримується перемноженням чисел для кожної заповненої клітинки з наступним додаванням отриманих чисел:               

17.23.Метод найменшої вартості побудови початкового опорного плану передбачає на першому кроці вибір клітинки з найменшою вартістю перевезення одиниці вантажу (найменшого елемента матриці (cij)). Для даної задачі такою є клітинка А2В2, в яку записується найменше з чисел 220, 230. Олівцем виставляються прочерки в клітинках А1 В2, А3В2, виключаючи тим самим їх з наступного розгляду. Біля запасів А2, записуються залишки запасів в розмірі 10 од. У звуженому полі клітинок вибирається найменша вартість в клітинці А2В1 в яку записується min (10, 150) =10. В А2В3 та А2В4виставляються прочерки, бо запаси А2 вичерпані, а під потребами В1 записуються залишки потреб в розмірі 140 од. На наступному кроці серед клітинок, що залишилися незаповненими, вибирається А1 В3, в якій міститься найменша вартість. В цю клітинку записується min (280,300)=280, проставляється прочерк в А3В3 і біля запасів А1 записується залишок в 20 од. Далі заповнюється клітинка А1B4 з найменшою вартістю (числом min (20, 200)=20), виставляються прочерки в клітинках А1В1, А1В2, і записується залишок потреб В4 в розмірі 180 од. В підсумку залишаються тільки дві клітинки (А3В1, та А3В4), які не мають прочерка або чисел, що визначають величину перевезень. В першу з них (вартість менша) записуємо min (140, 320)=І40, а в другу – залишок запасів А3,. Остаточно отримаємо таблицю 3.Таблиця З

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

Порівняння отриманих значень цільової функції на планах, побудованих різними методами, вказує на те, що опорний план, записаний в табл. З кращий (цільова функція мінімізується). Відмітимо, що можна навести багато прикладів ТЗ, в яких значення цільової функції на опорному плані, побудованому діагональним методом, е меншим, ніж на плані, побудованому методом найменшої вартості. Проте в середньому метод найменшої вартості дає краще наближення до оптимального плану в порівнянні із діагональним методом.

18. Метод потенціалів побудови оптимального плану

Побудова системи потенціалів.Потенціали знаходяться як розв'язки системи рівнянь. Побудований опорний план може бути й оптимальним, а може і ні. Сформулюємо критерій оптимальності Канторовича опорного плану ТЗ:Опорний планоптимальний тоді і тільки тоді, коли для цього плану існує система чисел-потенціалів u1,u2,...,um, v1,v2,...,vn таких, що для кожного хij > 0 виконується рівність u1+ v1=cij, а для кожного хij=0 виконується нерівність ui+vj ≤ сij.Іншими словами, для оптимальності опорного плану необхідно і достатнє існування такої системи потенціалів, що для заповнених клітинок виконується система рівнянь

                                                                   а для вільних клітинок виконується система нерівностей

                                                                        де К1, К2, множини пар індексів і та j), які визначають всі заповнені та вільні клітинки відповідно. Для доведення критерію достатньо побудувати задачу ЛП, двоїстою до якої і є задача (2)—(3). До речі, змінними цієї задачі і с потенціали  А потім скористатися загальним критерієм оптимальності Канторовича. Пропонуємо самостійно здійснити цей план.

Таким чином, для перевірки плану на оптимальність необхідно спочатку побудувати систему потенціалів. Розглянемо алгоритм методу потенціалів І одночасно проілюструємо його застосування на опорному плані, отриманому в табл. 3. Для цього таблицю доповнимо рядком знизу і колонкою справа, в яких записуються значення потенціалів B результаті отримаємо Таблиця 1.

Зауваження. При розв'язанні конкретної задачі доцільно поміщати знайдені потенціали справа і знизу табл. З, не будуючи табл. 4. Для заповнених  клітинок рекомендуємо здійснити перевірку правильності знаходження потенціалів.

 


 

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

2063. Создание и редактирование базы данных 345.56 KB
  Создание таблицы в режиме конструктора. Редактирование базы данных. Создание запросов. Настройка Параметров запуска базы данных.
2064. Аналіз сучасного стану управління транспортними потоками Жовтневого району м. Харкова 74.85 KB
  Аналіз методів організації дорожнього руху. північна частина Жовтневого району м. Харкова. Характеристики транспортних потоків. Характеристики технічних засобів регулювання дорожнього руху.
2065. Цитологические основы полового и бесполого размножения 39.65 KB
  В основе бесполого размножения лежит митоз. Митоз состоит из четырех фаз: профазы, метафазы, анафазы, телофазы.
2066. Закономерности наследования признаков, установленные Менделем 37.29 KB
  Часть открытий из области основных закономерностей наследования признаков принадлежит Менделю. Он проводил опыты по гибридизации гороха. Он отбирал растения, отличающиеся парой альтернативных признаков.
2067. Основные положения хромосомной теории наследственности, сформулированной Морганом 37.93 KB
  Поскольку число генов у каждой особи намного больше числа хромосом, в одной хромосоме располагается множество генов. Т. Морган и его ученики обнаружили, что гены, локализованные в одной хромосоме, наследуются совместно, то есть сцеплено.
2068. Типы взаимодействия генов 39.77 KB
  Различают следующие основные типы взаимодействия генов: 1) комплементарность, 2) элистаз, 3) полимерия, 4) модифицирующее действие генов.
2069. Роль ДНК как материального носителя наследственности 38.18 KB
  Доказательства роли ДНК как материального носителя наследственности. Структура ДНК, объясняющая ее роль как материального носителя наследственности.
2070. ДНК – основной материальный носитель наследственности 39.4 KB
  Доказательства важнейшего генетического значения ДНК были получены в результате анализа многих факторов и специально поставленных опытов.
2071. ДНК и вирусы 38.46 KB
  Вирусы — это внутриклеточные паразиты животных, растений и бактерий.