загрузка...
загрузка...
На головну

ГЛАВА 4. ГЕОМЕТРИЧНИЙ МЕТОД ВИРІШЕННЯ ЗАВДАНЬ лінійного програмування

  1. Case-метод Баркера
  2. CLIPS як багатофункціональне середовище програмування (інженерії знань)
  3. I. 2. 1. Марксистсько-ленінська філософія - методологічна основа наукової психології
  4. I. 2.4. Принципи та методи дослідження сучасної психології
  5. I. ЗАВДАННЯ АРТИЛЕРІЇ
  6. I. Методичні рекомендації
  7. I. Методичні рекомендації

Розглянемо задачу в стандартній формі (1.4) - (1.6) з двома змінними (n = 2). До такої форми може бути зведена канонічна задача (з обмеженнями у вигляді рівнянь) коли число змінних п більше числа рівнянь т на 2, тобто n - т = 2.

Мал. 4.1

Нехай геометричним зображенням системи обмеження є багатокутник ABCDE (Рис. 4.1). Необхідно серед точок цього багатокутника знайти таку точку, в якій лінійна функція  приймає максимальне (або мінімальне) значення.

Розглянемо так звану лінію рівня лінійної функції F, Тобто лінію, уздовж якої ця функція приймає одне і теж фіксоване значення a, тобто F=a або  . (4.1)

Рівняння лінії рівня функції (4.1) є рівняння прямої лінії. При різних рівнях a лінії рівня паралельні, так як їх кутові коефіцієнти визначаються тільки співвідношенням між коефіцієнтами c1 и c2 і, отже, рівні. Таким чином, лінії рівня функції F це своєрідні «паралелі», розташування зазвичай під кутом до осей координат.

Важлива властивість лінії рівня лінійної функції в тому, що при паралельному зсуві лінії в одну сторону рівень тільки зростає, а при зсуві в іншу сторону - тільки убуває. Строго це властивість виражається наступною теоремою.

Теорема. Нехай є три лінії рівня

 (I)

 (II)

 (III)

причому лінія II укладена між лініями I і III. тоді  або .

 На штриховий лінії (перпендикулярної до ліній рівняння на рис. 4.2 рівень є лінійною функцією, а значить при зміщенні в одному з напрямків зростає, а в іншу - убуває.

рис 4.2

Для визначення напрямку зростання рекомендує зобразити дві лінії рівня і визначити, на якій з них рівень більше. Наприклад, одну з ліній можна взяти проходить через початок координат (якщо лінійна функція має вигляд  без вільного члена, то це відповідає нульового рівня). Іншу лінію можна провести довільно, так, наприклад, щоб вона проходила через безліч рішень системи обмежень. Далі, з визначивши напрям зростання лінійної функції (позначимо його вектором ), знайдемо точку, в якій функція приймає максимальне або мінімальне значення подібно до того як на карті знаходиться найпівнічніша або найпівденніша точка (на рис. 4.1 - точка С або А).

Приклад 4.1.Вирішити геометрично задачу 1 в § 1.2: при обмеженнях

рис.4.3

Рішення.Зобразимо багатокутник рішень (аналогічно тому, як у прикладі 2.5) на рис. 4.3. Очевидно, що при F = 0 лінія рівня 2x1 + 3х2 = 0 проходить через початок координат (будувати її не обов'язково). Задамо, наприклад, F = 6 і побудуємо лінію рівня 2x1+ 3x2 = 6. Її розташування вказує на напрям зростання лінійної функції (вектор ). Оскільки розглянута задача на відшукання максимуму, то оптимальне  рішення в кутовій точці З, що знаходиться на перетині прямих I і II, тобто координати точки С визначаються рішенням системи рівнянні

 звідки  , Тобто C(6; 4).

Максимум (максимальне значення) лінійної функції Fmax= .

Отже, Fmax=  при оптимальному рішенні  , Тобто максимальний прибуток в 24 руб. може бути досягнута при виробництві 6 одиниць продукції Р1і 4 одиниць продукції Р2.

Приклад 4.2.Вирішити геометрично задачу 2 в § 1.2:

F = 4x1+ 6х2  min при обмеженнях

Рішення.Багатокутник рішень представляє необмежену багатокутну область (рис. 4.4). За розташований лінії рівня, наприклад, F = 12 або 1+ 6x2 = 12, знаходимо напрям вектора  (Цей вектор вказує на напрям зростання лінійної функції).

Мал. 4.4

Очевидно, що точка мінімуму - це точка входу "в багатокутник рішень, при подальшому переміщенні лінії рівня в напрямку вектора  значення лінійної функції збільшуються. Знаходимо координати точки В (2; 3), при цьому Fmin= .

Отже, Fmin=  при оптимальному рішенні x1= 2, x2= 3 тобто мінімальна вартість раціону 26 руб., якщо в нього включити 2 одиниці корму 1 і 3 одиниці корму II.

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

приклад4.3. Вирішити геометрично наступні завдання:

 а)  б)

при обмеженнях при обмеженнях

Рішення.а) Геометричне рішення задачі показано на рис. 4.5 а, З якого випливає, що лінія рівня з максимальним рівнем збігається з граничною лінією АВ багатокутника рішень ABCD, тобто з лінією  . Отже, на всьому відрізку АВ лінійна функція  приймає одне і те ж максимальне значення, рівне  . Це означає, що завдання має нескінченно багато оптимальних рішень (їх задають координати точок відрізка АВ), серед яких базисних оптимальних рішень два - відповідно в кутових точках А(3; 5) і В (6; 2). точки відрізка АВ задаються рівнянням х2 = 8 - х1 де  . Отже, Fmax= 24 при нескінченній множині оптимальних рішень .

Мал. 4.5

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

б) Геометричне рішення задачі показано на рис. 4.5, б, з якого випливає, що якщо лінію рівня переміщати в напрямку зменшення лінійної функції (тобто в напрямку, протилежному вектору  ), То вона завжди буде перетинати багатокутник рішень, отже, лінійна функція необмежено убуває. Отже, кінцевого оптимуму лінійної функції немає, тобто .

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

Розглянутий в цьому розділі геометричний метод розв'язання задач лінійного програмування має ряд переваг. Він простий, наочний, дозволяє швидко і легко отримати відповідь.

Однак тільки геометричний метод рішення ніяк не може задовольнити ні математиків, ні економістів. Можливі "технічні" похибки, які неминуче виникають при наближеному побудові графіків. Іншим важливим недоліком геометричного методу є те, що багато величини, які мають чіткий економічний зміст (такі, як залишки ресурсів виробництва, надлишок поживних речовин і т.п.), не виявляються при геометричному вирішенні завдань. Але найголовніше - геометричний метод неприйнятний для вирішення практичних завдань. Він застосовується лише в разі, якщо число змінних в стандартній задачі дорівнює двом. Тому необхідні аналітичні методи, що дозволяють вирішувати задачі лінійного програмування з будь-яким числом змінних і виявляти економічний сенс входять до них величин.

 



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   Наступна

ЗАГАЛЬНА ПОСТАНОВКА ЗАВДАННЯ лінійного програмування | Економіко-математична модель | Приклади завдань лінійного програмування | Загальна задача лінійного програмування | Відшукання максимуму лінійної функції | Відшукання мінімуму лінійної функції | при обмеженнях | Особливі випадки симплексного методу | II. Проблема виродженого базисного рішення | сімплексні таблиці |

загрузка...
© um.co.ua - учбові матеріали та реферати