мих рішень. Воно є рішенням системи лінійних обмежень, яке не можна представити у вигляді лінійної комбінації ніяких інших рішень.
При вирішенні задачі лінійного програмування можна поступити наступним чином: знайти будь-яке з таких "вершинних" рішень, не обов'язково оптимальне, і прийняти його за вихідний пункт розрахунків. Таке рішення і буде базисним. Якщо виявиться, що воно і оптимальне, розрахунок на цьому закінчено, якщо ні - послідовно перевіряють, чи не будуть оптимальними сусідні вершинні точки. Ту з них, в якій план ефективніше, приймають знову за вихідну точку і так, послідовно перевіряючи на оптимальність аналогічні вершини, приходять до шуканого оптимуму. На цьому принципі будуються так званий симплексний метод рішення завдань лінійного програмування, а також ряд інших способів, об'єднаних загальним назвою "методи послідовного поліпшення допустимого рішення (МПУ)": метод зворотної матриці, або модифікований симплекс-метод, метод потенціалів для транспортної задачі та інші. Вони відрізняються один від одного обчислювальними особливостями переходу від одного базисного рішення до іншого, поліпшеному. [2]
6. Методи побудови початкового опорного рішення
6.1 Побудова початкового плану за способом північно-західного кута
У цьому випадку не звертають уваги на показники витрат. Почавши заповнення з клітини (1.1) - "північно-західного кута" таблиці, ступенями спускаються вниз до клітини ( k , l ), викреслюючи або один рядок, або один стовпець. На останньому кроці викреслюються остання ( k -я) рядок і останній ( l -й) стовпець. При практичному заповненні таблиці, викреслення рядків і стовпців проводиться лише подумки.
Коли здійснюється початкове розподіл поставок, то не ставиться мета отримати оптимальний розподіл. Досягненню цієї мети служать наступні етапи рішення задачі. Вони полягають у переходах до нових розподілів поставок, поки не буде знайдено оптимальний розподіл поставок. [4]
6.2 Побудова початкового плану за способом мінімального елемента
При побудові початкового плану за способом північно-західного кута абсолютно не враховуються тарифи, тому план виходить дуже далеким від оптимального. Для вирішення завдання доводиться робити багато наближень (Кроків). p> Спосіб мінімального елемента враховує тарифи і тому дозволяє знайти план, ближчий до оптимального.
Цей спосіб полягає в наступному.
1. Маємо у своєму розпорядженні всі клітини таблиці в чергу по мірі зростання тарифів, починаючи з мінімального.
лінійне програмування транспортна задача
2. У клітку з мінімальним тарифом записуємо найбільшу можливу перевезення (виходячи із запасів і потреб), потім заповнюємо чергову по порядку клітку і т.д., поки не отримаємо план. При цьому повинен суворо дотримуватися баланс по рядках і стовпцях. Порожні клітини прокреслюється, а не зап...
