Електронна бібліотека математичні методи дослідження операцій

Розглянемо розширену матрицю системи лінійних рівнянь (3.37):

Матриця містить одиничну підматрицю близько 3 і. отже, визначає базисне рішення

системи рівнянь. причому = (0,0,0). Так як елементи (n + 1 = 6) -го стовпця матриці системи не є невід'ємними, то вона не є К-матрицею ЗЛП. Обчислимо симплекс-різниці матриці.

Так як всі симплекс-різниці матриці є невід'ємними, то базисне рішення = (-3; -6; 3) не є допустимим рішенням ЗЛП, є «кращим», ніж оптимальне рішення.

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

ВИЗНАЧЕННЯ Р-МАТРИЦІ ЗЛП

Визначення. Р-матрицею КЗЛП (3.18) будемо називати розширену матрицю системи лінійних рівнянь. равносильной системі (3.36), що містить одиничну підматрицю порядку m на місці n перших стовпців, все симплекс різниці якої невід'ємні.

Очевидно, що будь-яка Р-матриця ЗЛП визначає деякий базисне рішення системи рівнянь (3.36) (см.прімери 3.5)

Визначення. Базисне рішення системи лінійних рівнянь (3.36), яке визначається Р-матрицею, називається псевдопланом ЗЛП.

Умови переходу ВІД ОДНІЄЇ Р-МАТРИЦІ ЗЛП До ІНШИЙ

Нехай відома Р-матриця ЗЛП (3.18), що визначає псевдоплан

Теорема 1.5. нехай <0 и в l -й строке матрицы есть хотя бы один отрицательный элемент. Тогда с помощью одного шага метода Жордана-Гаусса можно построить новую Р-матрицу . выбрав направляющий элемент из условия

Зауваження 1. Якщо в матриці немає <0, то определяемый ею псевдоплан является решением ЗЛП.

Теорема 1.6. нехай <0 и в l -й строке матрицы нет ни одного отрицательного элемента. Тогда множество планов Р ЗЛП (3.18) пусто.

Зауваження 2. При переході від матриці до матриці цільова функція змінюється відповідно до формули

звідки випливає, що

так як <0 и . Из неравенства (3.40) следует, что при переходе от одного псевдоплана к другому значению целевой функции не возрастает.

Будемо вважати, що відома вихідна Р-матриця завдання лінійного програмування, що визначає вихідний псевдоплан

У методі послідовного уточнення оцінок послідовно будують Р-матриці. , ...,. ... завдання лінійного програмування, поки не отримають Р-матрицю завдання лінійного програмування, що визначає її оптимальний план.

Розглянемо алгоритм S -й ітерації методу послідовного уточнення оцінок. На початку S -й ітерації маємо Р-матрицю завдання лінійного програмування, що визначає псевдоплан

Крок 1. Знайдемо номер l з умови

є оптимальним опорним планом, а

є оптимальне значення лінійної форми. інакше переходимо до кроку 3.

то задача лінійного програмування не має рішення (безліч планів Р порожньо), інакше переходимо до кроку 4.

Крок 4. Обчислюємо для стовпців матриці (. I = 1, 2, ..., m) симплекс-різниці і знаходимо номер До з умови

Направляючий елемент на S -й ітерації методу є елемент.

Крок 5. Обчислюємо компоненти вектора.

Крок 6. Виробляємо один крок методу Жордана-Гаусса з напрямних елементом. Обчислюємо елементи Р-матриці методом Жордана-Гаусса. Надаємо змінної алгоритму S значення S +1 і переходимо до кроку 1.

РІШЕННЯ ЗАДАЧ Р-МЕТОДОМ

Вирішимо задачу з прикладу 3.5. Результати рішення наведені в симплекс-таблиці.

Так як = = -4 <0, а все 0, то множество планов ЗЛП (3.43) является пустым множеством.

Домашнє завдання №13

Підприємству необхідно випустити за планом продукції, не менше. ніж: А1 - 500 одиниць, А2 - 300 одиниць, А3 - 450 одиниць. Кожен вид вироби може проводитися на двох машинах. Як розподілити роботу машин, щоб загальні витрати часу на виконання плану були мінімальними, якщо задана матриця витрат. Ресурс часу кожної машини наведено праворуч від таблиці. Записати модель досліджуваної операції у формі, що допускає використання Р-методу.

А) за допомогою Р-методу;

Б) за допомогою методів лінійної алгебри.

Домашнє завдання №14

Вирішити задачу Р-методом.

З 4 видів кормів необхідно скласти раціон, до складу якого повинно входити не менше в1 од. речовини А, В2 од. речовини В і в3 од. речовини С. Кількість одиниць речовини, що міститься в 1 кг корму кожного виду, зазначено у відповідній таблиці. У ній же наведена ціна 1 кг корму кожного виду.

Скласти раціон, що містить не менше потрібної кількості зазначених поживних речовин і має мінімальну вартість.