числення опорного плану
Обчислення нев'язки.
На підставі матриці З 0 будується початковий план. Заповнення плану здійснюється по нулях матриці З 0 , рухаючись по стовпцях зверху вниз, зліва направо.
Після заповнення елемента плану обсяги виробництва і споживання коригуються. Корекції передує побудова ланцюжка. Ланцюжок містить обов'язково непарне число нулів і в принципі може складатися з одного нуля. Побудова ланцюжка починається з останнього знайденого нуля зі штрихом. Потім по стовпу до нуля із зірочкою, а вже від нього по рядку до нуля зі штрихом. Для корекції плану вибирається коригувальний елемент . Він вибирається з нев'язки рядки спочатку, з нев'язки кінця ланцюжка і елементів кінця Х, відповідних нулях із зірочкою, які увійшли в ланцюжок. Елемент додається до елемента Х ij, якщо йому в ланцюжок відповідав елемент З ij = 0 ', і віднімається від елемента Х ij , якщо в ланцюжку йому відповідав елемент З ij = 0 * . Для корекції плану розраховується нев'язка по рядках і стовпцях, а так само сумарна нев'язка.
Розраховуються нев'язки по стовпчиках і рядках.
Невязка по рядку, i = 1, m, j = 1, n (2.19)
Невязка по рядку, i = 1, m, j = 1, n (2.20)
Потім розраховується сумарна нев'язка плану
О” (2.21)
В
Якщо сумарна нев'язка плану пЃ„ = 0, то це говорить про отримання оптимального рішення. Якщо пЃ„ не дорівнює 0, то переходимо до етапу розмітки. Виводимо L - загальна вартість перевезень (див малюнок 2.3).
Малюнок 2.3 - блок - Схема підпрограми обчислення нев'язки. p> Опис програми.
Опис роботи програми:
користувач вводить кількість постачальників і споживачів;
користувач вводить всі дані про постачальників і споживачів;
користувач вводить обмеження;
будує матрицю З ij, елементи якої відображають певну знижку;
Всі використовувані в програмі змінні і підпрограми, коротко описані в таблицях 2.1
Опис блок-схеми:
блок-схема перевірка на умову балансу представлена ​​на малюнку 2.1;
блок - схема загального алгоритму обчислення опорного плану представлена ​​на малюнку 2.2;
блок схема обчислення нев'язки представлено на малюнку 2.3
Таблиця 2.1-Використовувані змінні
Ім'я
Тип
Опис
Cont
TZLPTableContext
У кожній конкретній бібліотеці буде свій тип контексту
Значення функції
Integer
Код повернення:
ResultError = - 1 - помилка в алгоритмі;
ResultFinish = 0 - успішне закінчення розрахунків;
ResultNoSolution = 1 - немає рішення;
SourceF
TFunction
Цільова функція
Limitations
TLimitations
Обмеження
MinMax
TFunctionType
Функція на мінімум або максимум.
ftMin - Мінімум;
ftMax - Максимум. /Td>
Len
В
Integer
Довжина масиву обмежень
Factors
TDynIntegerArray
Масив обмежень: послідовність з Len цілих чисел (Integer) /Td>
Значення функції
TIntegerMatrix
матриця з цілих чисел
