Industrialnet Головна Про сайт webcache.site checkip.site takescreenshot.site
  • Строрінки

  • Транспортна задача. Опорне рішення [2 ч.]

    Лінійне програмування

  • Математичні моделі задач лінійного програмування
  • Симплексний метод розв'язання задач лінійного програмування
  • Транспортна задача. Математична модель [1 ч.]
  • Транспортна задача. Опорне рішення [2 ч.]. Метод північно-західного кута
  • Зміст
  • Опорне рішення транспортної задачі
  • Метод викреслювання
  • Методи побудови початкового опорного рішення
  • Метод північно-західного кута
  • Метод мінімальної вартості
  • Теорема 38.1 Необхідна і достатня умова розв'язання транспортної задачі

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

    Теорема 38.2 Властивість системи обмежень транспортної задачі

    Ранг системи векторів-умов транспортної задачі дорівнює N=m+n-1 (m — постачальники, n-споживачі)

    Опорне рішення транспортної задачі

    Опорним рішенням транспортної задачі називається будь-яке припустиме рішення, для якого вектори умов, що відповідають позитивним координатами, лінійно незалежні.

    Зважаючи на те, що ранг системи векторів-умов транспортної задачі дорівнює m+n — 1, опорне рішення не може мати відмінних від нуля координат більше m+n-1. Число відмінних від нуля координат невырожденного опорного рішення дорівнює m+n-1, а для виродженого опорного рішення менше m+n-1

    Цикл

    Циклом називається така послідовність клітин таблиці транспортної задачі (i1, j1),(i1, j2),(i2, j2),...,(ik, j1), в якій дві і тільки дві сусідні клітини розташовані в одному рядку або стовпці, причому перша і остання клітини також знаходяться в одному рядку або стовпці.

    Цикл зображують у вигляді таблиці транспортної задачі у вигляді замкнутої ламаної лінії. У циклі будь-яка клітина є кутовий, в якій відбувається поворот ланки ламаної лінії на 90 градусів. Найпростіші цикли зображені на малюнку 38.1

    Теорема 38.3

    Допустиме рішення транспортної задачі X=(xij) є опорним тоді і тільки тоді, коли зайнятих клітин таблиці можна утворити жодного циклу.

    Метод викреслювання

    Метод викреслювання дозволяє перевірити, чи є дане рішення транспортної задачі опорним.

    Нехай допустиме рішення транспортної задачі, яка має m+n-1 відмінних від нуля координат, записано в таблицю. Щоб дане рішення було опорним, вектори-умов, що відповідають позитивним координатами, а також базисним нулях, повинні бути лінійно незалежними. Для цього зайняті вирішенням клітини таблиці повинні бути розташовані так, щоб не можна було з них утворити цикл.

    Рядок або стовпець таблиці з однієї зайнятої клітиною не може входити в якийсь цикл, так як цикл має дві і тільки дві клітини в кожному рядку або стовпці. Отже, щоб викреслити спочатку всі рядки таблиці, що містять по одній зайнятої клітці, або всі стовпці, що містять по одній зайнятої клітці, далі повернутися до стовпців (рядків) і продовжувати викреслення.

    Якщо в результаті викреслювання всі рядки истолбцы будуть викреслені, значить, зайнятих клітин таблиці можна виділити частину, яка утворює цикл, та система відповідних векторів умов є лінійно незалежною, а рішення є опорним.

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

    Приклади "викресленого" (опорного) і "не викресленого" (не опорного рішень):

    Логіка викреслювання:

  • Викреслити всі стовпці, в яких лише одна зайнята клітка(5 0 0), (0 9 0)
  • Викреслити всі рядки, в яких лише одна зайнята клітка (0 15), (2 0)
  • Повторити цикл (7) (1)
  • Методи побудови початкового опорного рішення Метод північно-західного кута

    Існує ряд методів побудови початкового опорного рішення, найпростішим із яких є метод північно-західного кута.
    У даному методі запаси чергового за номером постачальника використовуються для забезпечення запитів чергових за номером споживачів до тих пір, поки не будуть вичерпані повністю, після чого використовуються запаси наступного за номером постачальника.

    Заповнення таблиці транспортної задачі починається з її лівого верхнього кута, тому і називається метод північно-західного кута.

    Метод складається з ряду однотипних кроків, на кожному з яких, виходячи із запасів чергового постачальника і запитів чергового споживача, заповнюється тільки одна клітина і виключається з розгляду один постачальник або один споживач.

    Приклад 38.1

    Скласти опорне рішення, використовуючи метод північно-західного кута.

    Рішення:

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

    Приклад: так як його запаси a1 =100 менше запитів першого споживача b1 =100, то в клітку (1,1) записуємо перевезення x11=100 і виключаємо з розгляду постачальника.
    Визначаємо залишилися незадоволеними запити 1-го споживача b1= 150-100=50.

    150 200 100 100 100 100 100було-100треба=0залишилося 250 200

    150треба-100було=50залишилося
    Залишилося задовольнити
    запитів на 50 одиниць товару

    2. Розподіляємо запаси 2-го постачальника.
    Так як його запаси a2 = 250 більше залишилися незадоволеними запитів 1-го споживача b1 =50, то в клітку (2,1) записуємо перевезення x21 =50 і виключаємо з розгляду 1-го споживача.
    Визначаємо залишилися запаси 2-го постачальника a2 = a2 — b1 = 250-50=200. Так як залишилися запаси 2-го постачальника рівні запитам 2-го споживача, то в клітку (2,2) записуємо x22=200 і виключаємо на свій розсуд або 2-го постачальника, або 2-го споживача. У нашому прикладі ми виключили 2-го постачальника.
    Обчислюємо залишилися незадоволеними запити другого споживача b2=b2-a2=200-200=0.

    150 200 100 100 100 100
    250 50
    200

    250-50=200 200-200=0 200 150-100-50=0

    3. Розподіляємо запаси 3-го постачальника.
    Важливо! В попередньому кроці у нас був вибір виключати постачальника або споживача. Так як ми виключили постачальника, запити 2-го споживача все ж залишилися (хоч і дорівнюють нулю).
    Ми повинні записати залишилися запити рівні нулю в клітку (3,2)
    Це пов'язано з тим, що якщо в чергову клітину таблиці (i,j) потрібно поставити перевезення, а постачальник з номером i або споживач з номером j має нульові запаси або запити, то ставиться в клітку перевезення, рівна нулю (базисний нуль), і після цього виключається з розгляду або відповідний постачальник або споживач.
    Таким чином, в таблицю заносяться тільки базисні нулі, решта клітини з нульовими перевезеннями залишаються порожніми.

    У уникненні помилок після побудови початкового опорного рішення необхідно перевірити, що число зайнятих клітин дорівнює m+n-1 (базисний нуль при цьому теж вважається зайнятою кліткою), і вектори-умов, що відповідають цим клітинам, лінійно незалежні.

    Так як в попередньому кроці ми виключили з розгляду другого постачальника, то в клітку (3,2) записуємо x32=0 і виключаємо другого споживача.

    Запаси 3-го постачальника не змінилися. У клекту (3,3) записуємо x33=100 і виключаємо третього споживача. У клітку (3,4) записуємо x34=100. Зважаючи на те, що наше завдання з правильним балансом, запаси всіх поставащиков вичерпані і запити всіх споживачів задоволені повністю і одночасно.

    Опорне рішення 150 200 100 100 100 100 250 50 200 200 0 100 100

    4. Перевіряємо правильність побудови опорного рішення.
    Число зайнятих клітин має дорівнювати N=m(постачальники)+m(споживачі) — 1=3+4 — 1=6.
    Застосовуючи метод викреслювання, переконуємося, що знайдене рішення є "вычеркиваемым" (зірочкою відзначена базисний нуль).

    Отже, вектори-умов, відповідні зайнятих клітинам, лінійно незалежні і побудоване рішення дійсно є опорним.

    Метод мінімальної вартості

    Метод мінімальної вартості простий і дозволяє побудувати опорне рішення, досить близьке до оптимального, так як використовує матрицю вартостей транспортної задачі C=(cij).

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

    і виключається з розгляду тільки один рядок (постачальник) або один стовпець (споживач). Чергову клітку, відповідну , заповнюють за тими ж правилами, що і в методі північно-західного кута. Постачальник виключається з розгляду, якщо його запаси вантажу використані повністю. Споживач виключається з розгляду, якщо його запити задоволені повністю. На кожному кроці виключається або один постачальник, або один споживач. При цьому якщо постачальник ще не виключений, але його запаси дорівнюють нулю, то на тому етапі, коли від даного постачальника потрібно поставити вантаж, у відповідну клітинку таблиці заноситься базисний нуль і лише потім постачальник виключається з розгляду. Аналогічно з споживачем.

    Приклад 38.2

    Використовуючи метод мінімальної вартості побудувати початкова опорне рішення транспортної задачі.

    Рішення:

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

    2. Серед елементів матриці вартостей вибираємо найменшу вартість C11=1, відзначаємо її кружечком. Ця вартість має місце при перевезенні вантажу від 1-го постачальника 1-му споживачеві. У відповідну клітину записуємо максимально можливий обсяг перевезення:
    x11 = min {a1, b1} = min {60; 40} =40 тобто мінімум між запасами 1-го постачальника і запитами 1-го споживача.

    2.1. Запаси 1-го постачальника зменшуємо на 40.
    2.2. Виключаємо з розгляду 1-го споживача, так як його запити повністю задоволені. У матриці C викреслюємо 1-ий стовпець.

    3. В іншій частині матриці C мінімальною вартістю є вартість C14=2. Максимально можлива перевезення, яку можна здійснити від 1-го постачальника 4-му споживачеві дорівнює x14 = min {a1'; b4} = min {20; 60} = 20, де a1 зі штрихом це запаси першого постачальника.
    3.1. Запаси 1-го постачальника вичерпані, тому виключаємо його з розгляду.
    3.2. Запити 4-го споживача зменшуємо на 20.

    4. В іншій частині матриці С мінімальна вартість C24=C32=3. Заповнюємо одну з двох клітин таблиці (2,4) або (3,2). Нехай в клітку запишемо x24 = min {a2; b4} = min {80; 40} =40 .
    4.1. Запити 4-го споживача задоволені. Виключаємо його з розгляду викреслюючи 4-й стовпець матриці C.
    4.2. Зменшуємо запаси 2-го постачальника 80-40=40.

    5. В іншій частині матриці C мінімальна вартість C32=3. Запишемо в клітку (3,2) таблиці перевезення x32 = min {a3; b2} = min {100; 60} =60.
    5.1. Виключимо з розгляду 2-го споживача. З матриці C виключаємо 2-ий стовпець.
    5.2. Зменшимо запаси 3-го постачальника 100-60=40

    6. В іншій частині матриці C мінімальна вартість C33=6. Запишемо в клітку (3,3) таблиці перевезення x33 = min {a3'; b3} = min {40; 80} =40
    6.1. Виключимо з розгляду 3-го постачальника, а з матриці C 3-ю рядок.
    6.2. Визначаємо залишилися запити 3-го споживача 80-40=40.

    7. У матриці C залишився єдиний елемент C23=8. Записуємо в клітину таблиці 2,3) перевезення X23=40.

    8. Перевіряємо правильність побудови опорного рішення.
    Число зайнятих клітин таблиці дорівнює N=m+n — 1=3+4 -1.
    Методом викреслювання перевіряємо лінійну незалежність векторів-умов, що відповідають позитивним координатами рішення. Порядок викреслювання показаний на матриці X:

    Висновок: Рішення методом мінімальної вартості (таблиця 38.3) є "вычеркиваемым" і, отже опорним.

    Copyright © industrialnet.com.ua. 2016 • All rights reserved.