Метод штучного базису

Метод штучного базису

1. На попередній лекції було розглянуто задачу, записану у формі основної задачі ЛП, для якої можна було вказати її опорний план, тому що серед векторів Pj, координатами яких є коефіцієнти при невідомих в системі рівнянь даної задачі, було m одиничних. Але для багатьох задач ЛП, записаних у формі основної задачі і таких, що мають опорні плани, серед векторів Pj не завжди є M одиничних.

Розглянемо таку задачу.

Нехай потрібно знайти максимальне значення функції

F=C1X1+C2X2+…+Cnxn (1)

При умовах

(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 с.

Tagged with: , ,
Posted in Математичні моделі в розрахунках на еом
Перелік предметів:
  1. Інформаційні технологіі в галузі
  2. Інформаційні технологіі в системах якості стандартизаціісертифікаціі
  3. Історія української культури
  4. Бухоблік у ресторанному господарстві
  5. Діловодство
  6. Мікропроцесорні системи управління технологічними процесами
  7. Науково-практичні основи технологіі молока і молочних продуктів
  8. Науково-практичні основи технологіі м’яса і м’ясних продуктів
  9. Організація обслуговування у підприємствах ресторанного господарства
  10. Основи наукових досліджень та технічноі творчості
  11. Основи охорони праці
  12. Основи підприємницькоі діяльності та агробізнесу
  13. Політологія
  14. Технологічне обладнання для молочноі промисловості
  15. Технологічне обладнання для м’ясноі промисловості
  16. Технологічний семінар
  17. Технологія зберігання консервування та переробки молока
  18. Технологія зберігання консервування та переробки м’яса
  19. Технологія продукціі підприємств ресторанного господарства
  20. Технохімічний контроль
  21. Технохімічний контроль
  22. Управління якістю продукціі ресторанного господарства
  23. Вища математика 3к.1с
  24. Вступ до фаху 4к.2с.
  25. Загальні технології харчових виробництв
  26. Загальна технологія харчових виробництв 4к.2с.
  27. Мікробіологія молока і молочних продуктів 3к.1с
  28. Математичні моделі в розрахунках на еом
  29. Методи контролю харчових виробництв
  30. Основи фізіології та гігієни харчування 3к.1с
  31. Отримання доброякісного молока 3к.1с
  32. Прикладна механіка
  33. Прикладна механіка 4к.2с.
  34. Теоретичні основи технології харчових виробництв
  35. Технологія зберігання, консервування та переробки м’яса
  36. Фізика
  37. Харчові та дієтичні добавки
  38. Фізичне виховання 3к.1с

На русском

  1. Методы контроля пищевых производств
  2. Общая технология пищевых производств
  3. Теоретические основы технологий пищевых производств
  4. Технология хранения, консервирования и переработки мяса
LiveInternet