Метод штучного базису
1. На попередній лекції було розглянуто задачу, записану у формі основної задачі ЛП, для якої можна було вказати її опорний план, тому що серед векторів Pj, координатами яких є коефіцієнти при невідомих в системі рівнянь даної задачі, було m одиничних. Але для багатьох задач ЛП, записаних у формі основної задачі і таких, що мають опорні плани, серед векторів Pj не завжди є M одиничних.
Розглянемо таку задачу.
Нехай потрібно знайти максимальне значення функції
F=C1X1+C2X2+…+Cnxn
При умовах
(2)
Де 
І серед векторів
. . . 
Немає m одиничних векторів.
Визначення. Задача в якій потрібно знайти максимальне значення функції
F=C1X1+C2X2+…+Cnxn – МхN+1 – …-Mxn+M (3)
При умовах
(4)
Де М – деяке досить велике додатне число, конкретне значення якого як правило не задається, називається розширеною задачею по відношенню до задачі (1) – (2).
Розширена задача має опорний план Х=(0; 0; …; 0; B1; B2; …; Bm),
 |
N нулів
Що визначається системою одиничних векторів Pn+1, Pn+2, … , Pn+M, які утворюють базис
m-го векторного простору, що дістав назву Штучного. Вектори Pn+1, Pn+2, … , Pn+M і змінні 
називають Штучними. Якщо задача (1) – (2) має кілька одиничних векторів, то їх потрібно включити у штучний базис. Так як розширена задача має опорний план, то її розв’язок можна знайти симплексним методом. Для цього:
Складають розширену задачу (3) – (4). Знаходять опорний план розширеної задачі. Складають першу симплексну таблицю, яка містить на один рядок більше, ніж звичайна таблиця. При цьому у (M+2)-й рядок записують коефіцієнти при М, а у (M+1)-й – доданки, що не містять M.
При переході від одного опорного плану до другого в базис вводять змінну, що відповідає найбільшому за модулем від’ємному числу (M+2)– го рядка. Штучну змінну, що виводиться із базису в результаті деякої ітерації, надалі не має смислу вводити в жоден із наступних базисів і тому недоцільно обчислювати стовпчик цієї змінної.
Ітераційний процес по (M+2)– му рядку ведуть до тих пір, доки:
I. всі штучні змінні не будуть виключені із базису. В цьому випадку базис відповідає деякому опорному плану задачі (1) – (2) і визначення її оптимального плану продовжують по (M+1)– му рядку.
II. не всі штучні змінні виведено із базису, але (M+2)-Й рядок не містить більше від’ємних елементів в стовпчиках змінних Х1, х2, … , ХN+M. Якщо елемент (M+2)-Го рядка стовпчика Р0 від’ємний, то задача (1) – (2) не має розв’язку; якщо ж він дорівнює нулю то знайдений опорний план буде містити хоча б одну штучну змінну.
4. Використовуючи знайдений опорний план задачі (1) – (2), або знаходять симплексним методом оптимальний план цієї задачі, або встановлюють її нерозрішимість.
2. Термінологічний словник
Задача в якій потрібно знайти максимальне значення функції
F=C1X1+C2X2+…+Cnxn – МхN+1 – …-Mxn+M
При умовах
Де М – деяке досить велике додатне число, конкретне значення якого як правило не задається, називається Розширеною задачею по відношенню до задачі (1) – (2).
Розширена задача має опорний план Х=(0; 0; …; 0; B1; B2; …; Bm),
|
N нулів
Що визначається системою одиничних векторів Pn+1, Pn+2, … , Pn+M, які утворюють базис
m-го векторного простору, що дістав назву Штучного. Вектори Pn+1, Pn+2, … , Pn+M і змінні називають Штучними.
3. Рекомендована література
1. Богаєнко І. М., Григорків B. C., Бойчук М. В., Рюмашин М.0. Математичне програмування: Навч. посіб. – К.: Логос, 1996.
2. Бугір М. К. Зошит для практичних занять з математичного програмування. – Тернопіль: Підручники і посібники, 1999.
3. Бугір М. К. Математика для економістів. Лінійна алгебра, лінійні моделі: Навч. посіб. – К.: ВЦ «Академія», 1998.
4. Гвоздинський А. М. Оптимізаційні задачі в організаційному управлінні: Навч. посіб.-Харків: ХДТУР, 1997.
5. Гетманцев В. Д. Лінійна алгебра і лінійне програмування:
Навч. посіб. – К.: Либідь, 2001.
6. Григорків B. C., Бойчук М. В. Практикум з математичного програмування: Навч. посіб. – Чернівці: Прут, 1995.
7. Деордица Ю. С., Савченко В. Т. Компьютерные технологии в экономике и менеджменте: Учеб. пособие. – Луганск: ВУГУ, 1999.
8. Зайченко Ю. П. Дослідження операцій: Підручник. – К.:
ВШОЛ, 2000.
9. Исследование операций в экономике: Учеб. пособие / Под ред. Н. Ш. Кремера. – М.: ЮНИТИ, 1999.
10. Кігель В. Р. Елементи лінійного, цілочислового лінійного, нелінійного програмування: Навч. посіб. – К.: ІСДО, 1995.
11. Мазаракі А. А., Толбатов Ю. А. Математичне програмування в Ехсе1:Навч. посіб. – К.: Четверта хвиля, 1998.
12.Романюк Т. П., Терещенко Т. А., Присенко Г. В., Городкова І. М. Математичне програмування: Навч. посіб. – К.: ІЗМН, 1996.
13.Цегелик Г. Г. Лінійне програмування: Навч. посіб. – Львів: Світ, 1995.
14.Экономико-математические методы и прикладные модели: Учеб. пособие / Под ред. В. В. Федосеева. – М.: ЮНИТИ, 1999.
15.Крушевський А. В. Справочник по экономико-математическим моделям и методам. – К.: Техника, 1982, – 208 с.
Іб. Вивальнюк Л. М. Елементи лінійного програмування. – К.: Вищашк., 1975,-191 с.
Ви прочитали: "Метод штучного базису"Читати далі