Опорне рішення й оптимальне рішення. Загальні установки симплекс-методу

Можна довести, що якщо вже в ОЗЛП рішення є, то розташовано воно на границі тої багатокутної області, що задають обмеження й, більше того - в одній з вершин цієї багатокутної границі. Коли =2 все сказане має природний геометричний зміст (і багатокутна границя, і її вершина). У загальному ж - мірному випадку сказане означає, що якщо необхідна точка максимуму існує, то вона обертає хоч одне обмеження в рівність.

Є класичний симплекс-метод рішення ОЗЛП, що складає в тім, що спочатку відшукується хоч якась точка, що задовольняє всім обмеженням і, притім, що обертає хоч одне з обмежень у рівність. Ця точка відшукується безвідносно до цільової функції. Якщо з'ясовується, що такої точки ні, то говорять, що задача суперечлива (обмеження не здійсненні одночасно). Якщо така точка відшукується, то неї називають опорним рішенням ОЗЛП.

Потім, відповідно до симплекс-методом, проводиться спеціальний відбір опорних рішень для того, щоб знайти серед них точку максимуму. Якщо така відшукується, то ОЗЛП вирішена й знайдена точка називається оптимальним рішенням. Якщо з'ясовується, що такої точки ні, то це означає, що цільова функція необмежена в заданої обмеженнями області.

Коли =2, неважко намалювати приклади ОЗЛП, що є суперечливої, або має необмежену цільову функцію або, нарешті, що має конкретне рішення й, навіть, не одне.

3. Содержание

   • Конспект лекцій Частина і з дисципліни “Числові методи і моделювання на еом”
   • Лекция 1 числові методи алгебри. Особливості алгоритмування обчислювальних задач. Елементи теорії похибок обчислень та аналізу помилок округлення. Порядок виконання операцій
   • 1.1. Про наближені обчислення
   • 1.2. Лінійні заміни змінних
   • 1.3. Системи лінійних алгебраїчних рівнянь
   • 2.1. Апроксимація функції по Фур'є.
   • 2.1.1. Перетворення Фур'є
   • 2.2. Зворотна матриця
   • 3.1. Метод ділення відрізка навпіл для розв'язання рівнянь
   • 3.2. Метод хорд для рішення рівнянь
   • 3.3. Метод дотичних для розв'язання рівнянь
   • 3.4. Методика рішення алгебраїчного рівняння
   • Метод простих ітерацій
   • Метод Зейделя
   • Метод ітерацій для рішення рівнянь
   • 4.4. Метод ітерацій для рішення систем нелінійних алгебраїчних і
   • Лекция 5 звернення матриць. Подвійність у лінійному програмуванні. Одночасне рішення пари двоїстих задач лінійного програмування.
   • Лекція 6
   • 6.1. Чисельне диференціювання функції однієї змінної.
   • 6.2. Чисельне інтегрування функції однієї змінної.
   • 6. 3. Постановка задачі про чисельне рішення звичайного диференціального рівняння.
   • 6.5. Метод Рунге-Кутта чисельного рішення звичайного диференціального рівняння.
   • 6.6. Підхід до чисельного рішення системи звичайних диференціальних
   • Лекция 7 методи розв’язку диференціальних рівнянь та їх систем. Розв'язання систем лінійних алгебричних рівнянь із допомогою жорданових виключень
   • Лекция 8 чисельне диференціювання та інтегрування. Основна задача лінійного програмування. Дослідження її окремих випадків. Модифікований варіант жордановых винятків
   • 8.1. Постановка основної задачі лінійного програмування (озлп)
   • 8.2. Екстремальні задачі, що зводяться до озлп заміною змінних
   • 8.3. Лінійна заміна змінних і її використання в дослідженні основної
   • 8.4. Модифікований варіант жордановых виключень як спосіб організації лінійної заміни змінних
   • Лекция 9 диференціювання інтерполяційних формул. Мова « n-мірних» точок. Геометрія задачі лінійного програмування. Опорне рішення й оптимальне рішення. Загальні установки симплекса-методу
   • 9.1.Мова n-мірних точок.
   • 9.2. Геометрія задачі лінійного програмування.
   • Опорне рішення й оптимальне рішення. Загальні установки симплекс-методу
   • Підготовка озлп до рішення симплекс-методом.
   • Список рекомендованої літератури