пропускна можливість комунікацій.
Розмітка. На етапі розмітки відзначають символом В«+В» стовпці з нульовими невязкую і суттєві нулі матриці С. Точкою відзначають істотні неповні нулі, а двома точками - повні. Несуттєві нулі залишаються без розмітки. З точки зору комунікації вони є неповними.
Пошуковий етап. Метою пошуку є відшукати неповний нуль (без різниці істотний або несуттєвий), розташований у рядку з повною нев'язкої. Алгоритм пошуку по колонках відомий. p> Відшукання нуля на етапі пошуку Елемент, який стоїть на перетині виділеної рядки і виділеного стовпця називається двічі виділеним.
Вибирається коригувальний елемент h. Коригувальний елемент отримуємо як мінімальний позитивний елемент серед невиділеної частині матриці, або як мінімальний модуль двох виділених негативних елементів, якщо пошуковий етап закінчився невдачею в невиділеної частині матриці елементи непозитивні, а всі двічі виділені елементи невід'ємні, то завдання нерозв'язна при даних обмеженнях на пропускну здатність. Додається h до виділених елементів і віднімається з невиділених. Якщо двічі виділений елемент стає рівним нулю, то його виділяють "*" Знак виділення на колонку знімається.
Розрахунок цільової функції.
2. Практична частина
2.1 Опис алгоритму реалізації моделі
Визначившись з методами, які ми будемо використовувати у вирішенні завдання, приступимо до безпосереднього отриманню результату. Рішення транспортної задачі починається з знаходження опорного плану. Для цього існують різні способи. Наприклад, спосіб "Метод обмежень "/ Умови транспортної задачі задані транспортної таблицею (2.1).
Таблиця 2.1 - Умова транспортної задачі
ai/bj
B1
B2
B3
B4
25
25
15
25
A1
40
10
15
5
5
A2
30
10
12
6
6
A3
30
5
5
3
2
У даному випадку ОЈa i = 100 = ОЈb j = 100 маємо справу із закритою моделлю транспортної задачі.
Вводимо кількість постачальників і споживачів, потім будуємо матрицю елементи якої відображають вартість перевезення. Якщо завдання за умовою не є збалансованою, то для цього додаємо фіктивний пункт виробництва і споживача. У нашому випадки завдання є збалансованою, для її вирішення будуємо матрицю Х ij - план перевезень . Елементи цього типу характеризують кількість товарів, яке буде переміщатися від i-го постачальника до j-му споживачеві. Виводимо цільову функцію (див малюнок 2.1)
Малюнок 2.1 - блок-схема підпрограми перевірки на умову балансу.
В
p> Відбувається початкове обчислення опорного плану.
Побудова плану виконується зверху-вниз по стовпцях матриці Co починаючи з лівого, для O матриці Co, при цьому враховується пропускна можливість комунікацій.
На етапі розмітки відзначають символом "+" стовпці з нульовими невязкую і суттєві нулі матриці С. Точкою відзначають істотні неповні нулі, а двома точками - повні. Несуттєві нулі залишаються без розмітки. З точки зору комунікації вони є неповними. p> Метою пошуку є відшукати неповний нуль (без різниці істотний або несуттєвий), розташований у рядку з повною нев'язкої. Алгоритм пошуку по колонках відомий. p> Елемент який стоїть на перетині виділеної рядки і виділеного стовпця називається двічі виділеним.
Вибирається коригувальний елемент h. Коригувальний елемент отримуємо як мінімальний позитивний елемент серед невиділеної частині матриці, або як мінімальний модуль двох виділених негативних елементів
Якщо пошуковий етап закінчився невдачею в невиділений частині матриці елементи непозитивні, а всі двічі виділені елементи невід'ємні, то завдання нерозв'язна при даних обмеженнях на пропускну здатність.
Додається h до виділених елементам і віднімається з невиділених. Якщо двічі виділений елемент стає рівним нулю, то його виділяють "*" Знак виділення над стовпцем знімається.
В
Малюнок 2.2 - Загальний алгоритм об...
