74558

Задача лінійного програмування та методи її розв’язування

Лекция

Информатика, кибернетика и программирование

Основні властивості розвязків задачі лінійного програмування. Графічний метод розвязування задач лінійного програмування. Називається допустимим розвязком планом задачі лінійного програмування.

Украинкский

2015-01-04

2.06 MB

12 чел.


  1.  Задача лінійного програмування та методи її розвязування

Анотація

Загальна економіко-математична модель задачі лінійного програмування. Форми запису задач лінійного програмування. Геометрична інтерпретація задачі лінійного програмування. Основні властивості розв’язків задачі лінійного програмування. Графічний метод розв’язування задач лінійного програмування.

3.1 Загальна економіко-математична модель задачі лінійного програмування

Загальна лінійна економіко-математична модель економічних процесів та явищ – так звана загальна задача лінійного програмування подається у вигляді:

 (3.1)

за умов:

 (3.2)

 (3.3)

Отже, потрібно знайти значення змінних x1, x2, …, xn, які задовольняють умови (3.2) і (3.3), і цільова функція (3.1) набуває екстремального (максимального чи мінімального) значення.

Для довільної задачі математичного програмування у п.2.1 були введені поняття допустимого та оптимального планів.

Для загальної задачі лінійного програмування використовуються такі поняття.

Вектор Х = (х1, х2, …, хn), координати якого задовольняють систему обмежень (3.2) та умови невід’ємності змінних (3.3), називається допустимим розв’язком (планом) задачі лінійного програмування.

Допустимий план Х = (х1, х2, …, хn) називається опорним планом задачі лінійного програмування, якщо він задовольняє не менше, ніж m лінійно незалежних обмежень системи (3.2) у вигляді рівностей, а також обмеження (3.3) щодо невід’ємності змінних.

Опорний план Х = (х1, х2, …, хn), називається невиродженим, якщо він містить точно m додатних змінних, інакше він вироджений.

Опорний план , за якого цільова функція (3.1) досягає масимального (чи мінімального) значення, називається оптимальним розв’язком (планом) задачі лінійного програмування.

Задачу (3.1)—(3.3) можна легко звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (3.2) всі bi (i = 1, 2, …, m) невід’ємні, а всі обмеження є рівностями.

Якщо якесь bi від’ємне, то, помноживши i-те обмеження на
(– 1), дістанемо у правій частині відповідної рівності додатне значення. Коли
i-те обмеження має вигляд нерівності аi1х1+аi2х2+…+аinxnbi, то останню завжди можна звести до рівності, увівши додаткову змінну xn+1:

ai1x1+ai2x2+…+ ain xn + xn + 1 = bi.

Аналогічно обмеження виду аk1x1 + ak2x2 + … + aknxnbk зводять до рівності, віднімаючи від лівої частини додаткову змінну хn+2, тобто:

ak1x1 + ak2x2 + … + aknxnxn + 2 = bk (хn+1 ≥ 0, хn+2 ≥ 0).

3.2 Форми запису задач лінійного програмування

Задачу лінійного програмування зручно записувати за допомогою знака суми «». Справді, задачу (3.1)-(3.3) можна подати так:

за умов:

 (3.4)

Ще компактнішим є запис задачі лінійного програмування у векторно-матричному вигляді:

max(min) Z = CX

за умов: 

 АХ = А0; (3.5)

Х ≥ 0,

де

є матрицею коефіцієнтів при змінних;

 — вектор змінних;  — вектор вільних членів;

С = (с1, с2, …, сп) — вектор коефіцієнтів при змінних у цільовій функції.

Часто задачу лінійного програмування зручно записувати у векторній формі:

max(min)Z = CX

за умов: 

 A1x1 + A2x2 + … + Anxn = A0; (3.6)

X ≥0,

де

є векторами коефіцієнтів при змінних.

3.3 Геометрична інтерпретація задачі лінійного програмування

Розглянемо на площині х1Оx2 сумісну систему лінійних нерівностей:

 (3.7)

Кожна нерівність цієї системи геометрично визначає півплощину з граничною прямою ai1x1 + ai2x2 = bi (i=1,2, ..., т). Умови невід’ємності змінних визначають півплощини з граничними прямими х1 = 0 та х2 = 0. Система сумісна, тому півплощини як опуклі множини, перетинаючись, утворюють спільну частину, що є опуклою множиною і являє собою сукупність точок, координати кожної з яких є розв’язком даної системи (рис.3.1).

Рисунок 3.1

Сукупність цих точок (розв’язків) називають багатокутником розв’язків, або областю допустимих планів (розв’язків) задачі лінйного програмування. Це може бути точка (єдиний розв’язок), відрізок, промінь, багатокутник, необмежена багатокутна область.

Якщо в системі обмежень (3.7) буде три змінних, то кожна нерівність геометрично визначатиме півпростір тривимірного простору, граничними площинами котрого будуть ai1x1 + ai2x2 + ai3x3 = bi (i = 1, 2, ..., т), а умови невід’ємності – півпростори з граничними площинами хj=0 (j = 1, 2, 3), де і – номер обмеження, а j— номер змінної. Якщо система обмежень сумісна, то ці півпростори як опуклі множини, перетинаючись, утворять у тривимірному просторі спільну частину, що називається багатогранником розв’язків. Він може бути точкою, відрізком, променем, багатокутником, багатогранником, багатогранною необмеженою областю.

Нехай у системі обмежень (3.7) кількість змінних більша, ніж три: х1, х2,… хn; тоді кожна нерівність визначає півпростір n-вимірного простору з граничною гіперплощиною аi1x1 + ai2x2 + ai3x3 + … +ainxn = bi (i = 1, 2, ..., т). Кожному обмеженню виду (3.7) відповідають гіперплощина та напівпростір, який лежить з одного боку цієї гіперплощини, а умови невід’ємності — півпростори з граничними гіперплощинами хj = 0 (j=1, 2, 3, ..., n).

Якщо система обмежень сумісна, то за аналогією з тривимірним простором вона утворює спільну частину в n-вимірному просторі — опуклий багатогранник допустимих розв’язків.

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

Цільову функцію

в п-вимірному просторі основних змінних можна геометрично інтерпретувати як сім’ю паралельних гіперплощин, положення кожної з яких визначається значенням параметра Z.

Розглянемо геометричну інтерпретацію задачі лінійного програмування на прикладі. Нехай фермер прийняв рішення вирощувати озиму пшеницю і цукрові буряки на площі 20 га, відвівши під цукрові буряки не менше як 5 га. Техніко-економічні показники вирощування цих культур маємо у табл.3.1:

Таблиця 2.3 – Показники вирощування сільськогосподарських культур

Показник

(із розрахунку на 1 га)

Озима пшениця

Цукрові буряки

Наявний ресурс

Затрати праці, людино-днів

5

25

270

Затрати праці механізаторів, людино-днів

2

8

80

Урожайність, тонн

3,5

40

Прибуток, тис. грн

0,7

1

Критерієм оптимальності є максимізація прибутку.

Запишемо економіко-математичну модель структури виробництва озимої пшениці та цукрових буряків, ввівши такі позначення:

х1 — шукана площа посіву озимої пшениці, га;

х2 — шукана площа посіву цукрових буряків, га.

Задача лінійного програмування має такий вигляд:

 max Z = 0,7x1 + x2 (3.8)

за умов:

x1 + x2  20; (3.9)

 5x1 + 25x2  270; (3.10)

 2x1 + 8x2  80; (3.11)

x2  5; (3.12)

x1  0, x2  0. (3.13)

Геометричну інтерпретацію задачі зображено на рис.3.2.

Рисунок 3.2 – Область допустимих розв’язків задачі

Область допустимих розв’язків цієї задачі дістаємо так. Кожне обмеження, наприклад х1 + х2  20, задає півплощину з граничною прямою х1 + х2 = 20. Будуємо її і визначаємо півплощину, яка описується нерівністю х1 + х2  20. З цією метою в нерівність х1+х220 підставляємо координати характерної точки, скажімо, х1=0 і х2=0. Переконуємося, що ця точка належить півплощині х1+х220. Цей факт на рис.3.2 ілюструємо відповідною напрямленою стрілкою. Аналогічно будуємо півплощини, які відповідають нерівностям (3.10)—(3.13). У результаті перетину цих півплощин утворюється область допустимих розв’язків задачі (на рис.3.2 – чотирикутник ABCD). Цільова функція Z = 0,7x1 + x2 являє собою сім’ю паралельних прямих, кожна з яких відповідає певному значенню Z. Зокрема, якщо Z=0, то маємо 0,7х1 + х2 = 0. Ця пряма проходить через початок системи координат. Коли Z=3,5, то маємо пряму 0,7х1 + х2 = 3,5.

3.4 Основні властивості розв’язків задачі лінійного програмування

Властивості розв’язків задачі лінійного програмування формулюються у вигляді чотирьох теорем.

Властивість 1. (Теорема 3.1) Множина всіх планів задачі лінійного програмування опукла.

Властивість 2. (Теорема 3.2) Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин її багатогранника розв’язків. Якщо ж цільова функція набуває екстремального значення більш як в одній вершині цього багатогранника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією таких вершин.

Властивість 3. (Теорема 3.3) Якщо відомо, що система векторів A1, A2, …, Ak (k≤n) у розкладі A1x1 +A2x2 + … + Anxn = A0, X≥0 лінійно незалежна і така, що

A1x1 + A2x2 + … + Akxk = A0,

де всі xj ≥ 0, то точка X = (x1, x2, …, xk, 0, …, 0) є кутовою точкою багатогранника розв’язків.

Властивість 4. (Теорема 3.4) Якщо X = (x1, x2, …, xn) – кутова точка багатогранника розв’язків, то вектори в розкладі A1x1 + + A2x2 + … + Anxn = A0, X ≥ 0, що відповідають додатним xj, є лінійно незалежними.

Наслідок 1. Оскільки вектори  мають розмірність m, то кутова точка багатокутника розв’язків має не більше, ніж m додатних компонентів .

Наслідок 2. Кожній кутовій точці багатокутника розв’язків відповідає  лінійно незалежних векторів системи .

З наведених властивостей можна зробити висновок, що якщо функціонал задачі лінійного програмування обмежений на багатограннику розв’язків, то:

  1.  існує така кутова точка багатогранника розв’язків, в якій лінійний функціонал досягає свого оптимального значення;
  2.  кожний опорний план відповідає кутовій точці багатогранника розв’язків.

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

3.5 Графічний метод розв’язування задач лінійного програмування

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

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

Знайти

 (3.15)

за умов:

 (3.16)

. (3.17)

Припустимо, що система (3.15) за умов (3.16) сумісна і багатокутник її розв’язків обмежений.

Згідно з геометричною інтерпретацією задачі лінійного програмування (п.3.3) кожне і-те обмеження-нерівність у (3.16) визначає півплощину з граничною прямою  (і = 1, 2, …, т). Системою обмежень (3.16) графічно можна зобразити спільну частину, або переріз усіх зазначених півплощин, тобто множину точок, координати яких задовольняють всі обмеження задачі – багатокутник розв’язків.

Умова (3.17) невід’ємності змінних означає, що область допустимих розв’язків задачі належить першому квадранту системи координат двовимірного простору. Цільова функція задачі лінійного програмування геометрично інтерпретується як сім’я паралельних прямих с1х1+с2х2 = const.

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

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

Алгоритм графічного методу розв’язування задачі лінійного програмування складається з таких кроків:

1. Будуємо прямі, рівняння яких дістаємо заміною в обмеженнях задачі (3.16) знаків нерівностей на знаки рівностей.

2. Визначаємо півплощини, що відповідають кожному обмеженню задачі.

3. Знаходимо багатокутник розв’язків задачі лінійного програмування.

4. Будуємо вектор , що задає напрям зростання значення цільової функції задачі.

5. Будуємо пряму с1х1+с2х2=const, перпендикулярну до вектора .

6. Рухаючи пряму с1х1+с2х2=const в напрямку вектора
(для задачі максимізації) або в протилежному напрямі
(для задачі мінімізації), знаходимо вершину багатокутника розв’язків, де цільова функція набирає екстремального значення.

7. Визначаємо координати точки, в якій цільова функція набирає максимального (мінімального) значення, і обчислюємо екстремальне значення цільової функції в цій точці.

У разі застосування графічного методу для розв’язування задач лінійного програмування можливі такі випадки:

1. Цільова функція набирає максимального значення в єдиній вершині А багатокутника розв’язків (рис.3.3).

2. Максимального значення цільова функція досягає в будь-якій точці відрізка АВ (рис.3.4). Тоді задача лінійного програмування має альтернативні оптимальні плани.

3. Задача лінійного програмування не має оптимальних планів: якщо цільова функція необмежена згори (рис.3.5) або система обмежень задачі несумісна (рисунок 3.6).

                   Рисунок 3.3        Рисунок 3.4

                       Рисунок 3.5                   Рисунок 3.6

4. Задача лінійного програмування має оптимальний план за необмеженої області допустимих розв’язків (рис.3.7 і 3.8). На рис.3.7 у точці В маємо максимум, на рис.3.8 у точці А  мінімум, на рис.3.9 зображено, як у разі необмеженої області допустимих планів цільова функція може набирати максимального чи мінімального значення у будь-якій точці променя.

                    Рисунок 3.7              Рисунок 3.8

Рисунок 3.9

Розв’язувати графічним методом можна також задачі лінійного програмування n-вимірного простору, де , якщо при зведенні системи нерівностей задачі до системи рівнянь шляхом введення додаткових змінних кількість змінних n на дві більша, ніж число обмежень m, тобто .

Тоді, як відомо з курсу вищої математики, можна дві з n змінних, наприклад х1 та х2, вибрати як вільні, а інші m зробити базисними і виразити через вільні. Припустимо, що це зроблено. Отримаємо  рівнянь вигляду:

Оскільки всі значення , то мають виконуватись умови:

,

 (3.18))

Розглянемо, як можна зобразити ці умови геометрично. Візьмемо, наприклад, першу з них:

Узявши величину х3 рівною своєму крайньому значенню — нулю, отримаємо рівняння:

.

Це рівняння прямої. Для такої прямої , по одну сторону від неї , а по другу . Відмітимо ту сторону прямої , де .

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

У такий спосіб отримують n–2 прямі та дві осі координат (,). Кожна з них визначає півплощину, де виконується умова . Частина площини в  належить водночас всім півплощинам, утворюючи багатокутник допустимих розв’язків.

Припустимо, що в задачі необхідно знайти максимальне значення функціонала:

.

Підставивши вирази для , , , ...; з (3.18) у цей функціонал, зведемо подібні доданки і отримаємо вираз лінійної функції F всіх n змінних лише через дві вільні змінні  та :

,

де  — вільний член, якого в початковому вигляді функціонала не було.

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

(Самостійна робота)

Приклад 3.1. Розв’язати графічним методом задачу лінійного програмування

.

Розв’язання. Маємо n=7 – кількість змінних, m=5 – кількість обмежень. Виберемо як вільні змінні х1 та х2 і виразимо через них всі інші базисні змінні. З першого рівняння маємо:

 (3.19)

З третього рівняння:

, (3.20)

а з четвертого:

. (3.21)

Підставляючи (3.19) в друге рівняння системи і (3.21) в останнє, розв’язуємо їх відносно х4 та х7. Отримаємо:

;

.

Далі за алгоритмом беремо х1 = 0 та х2 = 0 координатні осі; інші обмежуючі прямі знаходимо, узявши х3 = 0, х4 = 0, х5=0, х6 = 0, х7 = 0. Багатокутник допустимих розв’язків зображено на рис. 3.10.

Рисунок 3.10

Знайдемо вигляд функціонала, вираженого через х1 та х2. Для цього знайдені щойно вирази для х3, х4, х5, х6 та х7 через вільні змінні х1 і х2 підставимо у функціонал і, звівши подібні члени, отримаємо: . Відкидаючи вільний член, маємо: . Будуємо вектор (–5, –2), перпендикулярно до нього — пряму F'. Рухаючи пряму F' в напрямку, протилежному  (необхідно знайти мінімальне значення функції F), отримаємо точку мінімуму А (рис.3.11).

Рисунок 3.11

У точці А перетинаються дві обмежуючі прямі: х6=0 та х7=0. Отже, для відшукання її координат необхідно розв’язати систему рівнянь:

Розв’язком системи є = 8,5;  = 5. Підставивши ці значення у відповідні вирази, знайдемо оптимальні значення базисних змінних:

= 0,5; = 16,5; = 17,5; = 0; = 0.

Підстановкою значень  та  в лінійну функцію F отримуємо значення цільової функції:

.


 

А также другие работы, которые могут Вас заинтересовать

29512. Означення поняття сексологія і сексопатологія 158.5 KB
  Сексологія вивчає закономірності психосексуального розвитку диференціації і детермінації статі формування сексуальної орієнтації та ідентичності статевовікові особливості психосексуального розвитку і сексуальної поведінки. Статеве дозрівання статевий розвиток це процес формування вторинних статевих ознак розвиток репродуктивних органів і здатність до народження дітей. Психосексуальний розвиток ПСР це формування статевої самосвідомості статевої ролі і психосексуальної орієнтації а саме формування векторів сексуального потягу...
29513. Формування сексуальної орієнтації і норми 43 KB
  Означення поняття сексуальної норми включає поведінку, відповідну віковим та статево-рольовим закономерностям даної популяції, яка здійснюється в результаті вільного вибору і не обмежує у вільному виборі партнера (А.А. Ткаченко). В сексології розрізняють поняття індивідуальної та партнерської норми.
29514. Формування сексуальної норми 98.5 KB
  запропонував робочу класифікацію ролей чоловіків і жінок в статевому циклі. Її сексуальність носить материнський характер опіка захист турбота до чоловіка що проявляється в її мові використання зменшених ласкавих слів поведінці достатньо активні але не агресивні пестощі з її боку смаки і симпатії віддають перевагу слабким невпевненим в собі інфантільним навіть хворим чоловікам яких годує лікує опікується ними тощо. Ідеальний партнер для тривожних боязких неуспішних чоловіків котрих вона “навчає коханню†підтримує....
29515. Формування сексуальної норми і орієнтації 104 KB
  При наявності високого еротичного показника 4 5 оргазм може виникнути без статевого акту. Пестощі бувають першого другого третього порядку це терміни які відображають послідовність пестощів необхідних для розвитку статевого збудження. Початок статевого акту повинен проходити на фоні значного сексуального збудження жінки включаючи як фізичні так і психічні зміни. Шкала статевого збудження жінки: вегетативносудинний рівень 10 20 ; моторномовленнєвий рівень 30 40 ; поведінковий рівень 40 50 ; психічні прояви ...
29516. Порушення статевої та психосексуальної диференціації та ідентичності, причини і форми 67.5 KB
  Психосексуальна диференціація ПСД як процес представляє собою явище механізми котрого визначаються взаємодією детермінант статі. Статева та сексуальна ідентифікація жіноча; Анарія порок розвитку внутрішньоутробне порушення зовнішніх органів яєчек недорозвиток статевого органу може бути заміна статі; Дісгенезія гонад гермофродитизм істиний і чоловічі і жіночі елементи внутрішніх статевих органів частіше як дівчинки в подальшому зміна статі. Питання зміни статі А.Бєлкін 1978 описує порушення індентифікації у...
29517. Сексологічне обстеження 164.5 KB
  Більшість спеціалістів розуміють що обстеження сексологічних пацієнтів має свої особливості: інтимність питання “закритість†пацієнтів їх невміння обговорювати своє сексуальне життя відсутність адекватної мови для обговорення цих порушень. 4 варіанти уявних порушень: зі ставленням до себе підвищених вимог; невротична тривога психотична; ненормальні уявлення про статеві стосунки пацієнта або пари розянень.2 наявність сексуальних порушень у партнера. Аналіз статевих порушень з позицій “психогенне особистісно ...
29518. Діагностика сексуальних розладів (тестування) 42 KB
  При психологічній діагностиці сексуальної патології повинен проводитись диференціальний діагноз з порушеннями. При психологічному обстеженні осіб з сексуальними порушеннями виявляється підвищення “невротичноїâ€ частини профілю “пікиâ€: статева дисфункція без органічної патології високий підйом за шкалою істерії; розлади сексуальної переваги психопатії. Келлі дозволяє виявити основні фактори які затримують досягнення гармонії в статевих відносинах а також індивідуальну систему життєвих цінностей і орієнтацій які...
29519. Конфликт: предотвращение и управление 84 KB
  Моргунов В этой теме вы узнаете: Все о конфликтах о типологии конфликтов а также их предотвращении; О причинах и фазах конфликта; О конфликте и эмоциях; О задачах и основных понятиях конфликтологии; О типичных ошибках конфликтологии и технологии разрешения конфликта; Необходимо сразу оговорить что безконфликтных организаций не существует. Поэтому понимать истоки конфликта и уметь управлять его течением и разрешением неотъемлемое умение руководителя. Если противоречие получает развитие говорят о возникновении конфликта....
29520. Организация как система 44.5 KB
  Общая теория систем это не столько научная теория в традиционном смысле слова сколько комплекс методологических подходов к обширному классу объектов объединенных названием сложные системы Шрейдер Ю. Определения и свойства системы Часть смысловых связей понятия система можно обнаружить в его противопоставлении с несколькими понятиями: система беспорядочное образование; система аморфность; система случайная совокупность; система случайность; система множество из элементов не связанных в целое.Блюменфельду системой...