Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Как продвинуть сайт на первые места?
    Вы создали или только планируете создать свой сайт, но не знаете, как продвигать? Продвижение сайта – это не просто процесс, а целый комплекс мероприятий, направленных на увеличение его посещаемости и повышение его позиций в поисковых системах.
    Ускорение продвижения
    Если вам трудно попасть на первые места в поиске самостоятельно, попробуйте технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Если ни один запрос у вас не продвинется в Топ10 за месяц, то в SeoHammer за бустер вернут деньги.
    Начать продвижение сайта
  • Цикл перерахунку.






    На другому етапі перевіряється - чи є базисне рішення оптимальним.

    Для цього спочатку потрібно виразити цільову функцію W (3.1) задачі через неосновні (вільні) змінні. Мінімум цільової функції, тобто рішення транспортної задачі, отримується тоді, коли всі коефіцієнти при вільних (неосновних) змінних у виразі для цільової функції W (3.1) через вільні перемінні невід’ємні.

    У транспортній задачі змінна хij ототожнюється з вмістом відповідної клітки (i, j) таблиці постачань. Позначимо bij коефіцієнт біля вільної змінної хij у виразі для лінійної функції цілі W (3.1) через вільні змінні; bij називається оцінкою вільної клітки (i, j).

    При даному базисному розподілі постачань клітка (i, j) - вільна (змінна хij - вільна), bij - оцінка клітки (i, j) чи коефіцієнт у виразі лінійної функції W (3.1) через вільні змінні:

     

    W = W0 + bij хij + … (3.4)

     

    де трикрапкою позначені доданки, що відповідають вільним змінним, відмінним від хij, W0 – сумарні витрати на даний розподіл постачань.

    Тоді з (3.4) випливає, що оцінка bij вільної (i, j) клітки дорівнює зміні сумарних витрат Δ W на постачання при переведенні в клітку (i, j) одиничного постачання (збільшення змінної хij від 0 до 1), тобто: bij = Δ W = Wп – Wн, де Wн - первинні витрати на постачання;
    Wп - витрати на постачання після перерозподілу. Передбачається, що у всіх вільних клітках відмінних від клітки (i, j), постачання залишиться нульовим. Очевидно, що Δ W > 0 якщо
    bij > 0; Δ W < 0 якщо bij < 0. Останнє непряме визначення оцінки вільної клітки називають економічним змістом оцінки вільної клітки.

    Знайдемо оцінку вільної клітки А3. Для цього дамо в клітку А3 одиничне постачання. При цьому буде потрібно змінити постачання в заповнених клітках так, щоб зберігся баланс по рядках і стовпцям (передбачається, що у всіх вільних клітках відмінних від клітки А3, постачання залишиться нульовим). Так, щоб 3-й район як і раніше одержав 5 тис. номерів, постачання в клітці В3 варто зменшити на 1тис. Для того, щоб АТС В як і раніше поставила 3тис. номерів, постачання в клітці В2 збільшуємо на 1тис. 2-му району необхідно тільки 4тис. номерів, тому постачання в клітці А2 варто зменшити на 1тис. З'єднавши один по одному зазначені клітки A3 à B3 à B2 à A2 à A3 одержимо замкнутий контур (цикл).

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

    Позначимо знаком «+» ті вершини, у яких постачання (перевезення) збільшуються, а знаком «-» ті, у яких вони зменшуються.

    Позначеним циклом перерахунку називається цикл, у вершинах якого розставлені знаки «+» і «-», так, що у вільній клітці стоїть знак «+», а сусідні вершини мають протилежні знаки.

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

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

    Так, якщо після перерозподілу маємо bij=Δ W з від’ємною оцінкою, то вихідний базовий розподіл – не оптимальний і його можна поліпшити.

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

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

    В отриманій базовій транспортній таблиці необхідно побудувати зазначені цикли перерахунку для усіх вільних кліток. У вихідній вільній клітці розміщаємо одну з вершин і приписуємо «+». Всі інші вершини перерахунку повинні спиратися на зайняті клітки.


     

     

    А 4 3т 7 2т  
    В  
    С    
    n       Qj
    q  

     

    А3: A3 à B3 à B2 à A2 à A3 bA3 = 6-11+15-7 = 3

    B1: В1 à А1 à А2 à В2 à В1 bВ1 = 12-4+7-15 = 0

    C1: С1 à С3 à В3 à В2 à А2 à A1 à C1 bС1 = 13-10+11-15+7-4 = 2

    C2: С2 à В2 à В3 à C3 à C2 bС2 = 7-15+11-10 = -7

     

    Для поліпшення рішення в розглянутій задачі можна виконати єдиний цикл перерахунку з від’ємною ціною bС2:

     

    А  
    В   15- 2т 11 + 1т
    С   7 + 10 - 4т
    n       Qj
    q  

     






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.