Основні типи та види моделей. Основні методи складання початкового опорного плану. Поняття потенціалу й циклу. Критерій оптимальності базисного рішення транспортної задачі. Методи відшукання оптимального рішення. Задача, двоїста до транспортного.
У системі (2.3) виділений зазначений вище базис: базисні невідомі з перших т рівнянь утворять перший стовпець матриці перевезень, а базисних невідомі інших рівнянь утворять перший рядок матриці перевезень без першого невідомого [вона входить у перше рівняння системи (2.3)]. У першому випадку ми можемо виключити стовпець, що містить заповнену на цьому кроці клітку, і вважати, що задача звелася до заповнення таблиці із числом стовпців, на одиницю меншим, чим було перед цим кроком, але з тією же кількістю рядків і з відповідно зміненим запасом вантажу на одній з баз (на тій базі, який був удоволений замовник на даному кроці). нові значення: Очевидно, якщо постачити вершини циклу по черзі знаками “ ” і “-“, приписавши вершині у вільній клітці знак “ ”, те можна сказати, що у вершинах зі знаком “ ” число додається до колишнього значення невідомого, що перебуває в цій вершині, а у вершинах зі знаком “-“ це число віднімається з колишнього значення невідомого, що перебуває в цій вершині. Отже, алгебраїчна сума тарифів для вільної клітки дорівнює різниці її сьогодення (“щирого”) і непрямого тарифів: З (4.3) треба, що якщо непрямий тариф для даної вільної клітки більше її щирого тарифу, те алгебраїчна сума тарифів по циклі, що відповідає цій клітці, буде негативна; якщо ж непрямий тариф менше щирого, те алгебраїчна сума тарифів позитивна, і, нарешті, якщо непрямий тариф дорівнює щирому, те алгебраїчна сума тарифів дорівнює нулю. У випадку якщо алгебраїчні суми тарифів для всіх вільних кліток позитивні, ми маємо єдине оптимальне рішення; якщо ж алгебраїчні суми тарифів для всіх вільних кліток ненегативні, але серед них є алгебраїчні суми тарифів, рівні нулю, то оптимальне рішення не єдине: при перерахуванні по циклі для клітки з нульовою алгебраїчною сумою тарифів ми одержимо оптимальне ж рішення, але відмінне від вихідного (витрати по обох планах будуть однаковими).
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
