Лекція 22

ЛІНІЙНЕ ПРОГРАМУВАННЯ

Чимало оптимізаційні завдання конструювання і виробництва радіоелектронних апаратів можна звести до моделей лінійного програмування. Вони характерні наявністю певних обмежень. Розглянемо насамперед задачу лінійного програмування з обмеженнями-рівностями - так звану основну задачу лінійного програмування (ОЗЛП). Надалі покажемо, як від завдання з обмеженнями-нерівностями перейти до ОЗЛП і назад.

ОЗЛП ставиться таким чином:

Є ряд змінних х₁, х₂, …, х_n. Потрібно знайти такі невід'ємні значення цих змінних, які задовольняли б системі лінійних рівнянь.

(22.1)

І, крім того, звертали б в мінімум лінійну функцію:

L = C₁x₁ + C₂x₂ + … + C_nx_n. (22.2)

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

L’ = -L = -C₁x₁ - C₂x₂ - … - C_nx_n. (22.3)

Домовимося називати допустимим рішенням ОЗЛП будь-яку сукупність змінних

x₁ ³ 0, x₂ ³ 0,x_n ³ 0, (22.4)

задовольняє рівнянням (22.1).

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

ОЗЛП необов'язково повинна мати рішення. Може виявитися, що рівняння (22.1) суперечать один одному, що вони мають рішення, але не в області невід'ємних значень х₁, х₂,..., х_n, може виявитися, що допустимі рішення існують, але серед них немає оптимального (функція L в області допустимих рішень не обмежена знизу).

Розглянемо перш за все питання про існування допустимих рішень ОЗЛП. При вирішенні цього питання ми можемо виключити з розгляду лінійну функцію L, яку потрібно мінімізувати - наявність допустимих рішень визначається тільки рівняннями (22.1).

Отже, нехай є система рівнянь (22.1). Чи існують невід'ємні значення

х₁, х₂,..., х_n задовольняють цій системі? Це питання розглядається в спеціальному розділі математики - лінійної алгебри. У лінійній алгебрі доводиться, що для сумісності системи лінійних рівнянь (22.1) необхідно і достатньо, щоб ранг матриці системи дорівнював рангу її розширеної матриці.

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

Отже, якщо система рівнянь-обмежень ОЗЛП сумісна, то матриця системи та її розширена матриця мають один і той же ранг. Цей загальний ранг r називається рангом системи. Він являє собою не що інше, як число лінійно незалежних рівнянь серед накладених обмежень. Очевидно, ранг не може бути більше числа рівнянь m (m ³ r).

Очевидно також, що ранг системи не може бути більше спільного числа змінних n.

Структура завдання лінійного програмування істотно залежить від рангу системи обмежень.

Розглянемо насамперед випадок, коли r = n, тобто коли число лінійно незалежних рівнянь, що входять в систему (22.1), дорівнює кількості змінних. З алгебри відомо, що в цьому випадку система має єдине рішення. Якщо в цьому рішенні хоча б одна з величин х₁, х₂,..., х_n негативна, це означає, що отримане рішення є допустимим. Воно ж є і оптимальним (так як інших немає).

Очевидно, цей найпростіший випадок нас мало цікавить. Тому надалі ми будемо розглядати тільки випадок, коли r < n, тобто коли число незалежних рівнянь, яким повинні задовольняти змінні х₁, х₂,..., х_n, менше числа самих змінних. Тоді, якщо система сумісна, у неї існує незліченна безліч рішень. При цьому n - r змінним ми можемо надавати довільні значення (так звані вільні змінні), а решта r змінних виразяться через них (ці r змінних будемо називати базисними). Отже, в даному випадку система має нескінченну безліч рішень. Якщо серед них існують невід'ємні рішення, то кожне з них допустимо. Виникає наступне завдання - знайти серед них оптимальне. Для того, щоб виразніше уявити собі особливості вирішення ОЗЛП, зручно скористатися геометричною інтерпретацією.

Геометрична інтерпретація ОЗЛП

Розглянемо випадок, коли число змінних n на два більше, ніж число незалежних рівнянь m, яким вони повинні задовольняти: n - m = 2. Тоді, як ми вже знаємо, можна дві з n змінних, скажімо х₁ і х₂ вибрати як вільних, а решта m зробити базисними і виразити їх через вільні. Отримаємо m = n - 2 рівнянь виду:

(22.5)

Дамо завданню ЛП геометричну інтерполяцію. По осях ОХ₁ і ОХ₂ будемо відкладати значення вільних змінних х₁ і х₂. Так як змінні х₁ і х₂ повинні бути невід'ємними, допустимі значення вільних змінних будуть знаходиться тільки в першому квадранті. Позначимо це штрихуванням, що позначає допустиму сторону кожної осі

Рис.22.1

Решта змінні х₃, х₄,..., х_n також повинні бути невід'ємними, тобто повинні виконуватися умови:

(22.6)

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

Покладемо величину х3 дорівнює крайнього своїм значенням - нулю. Отримаємо рівняння. Це рівняння прямої. На цій прямій х₃ = 0, по одну сторону від неї х₃> 0, по іншу х₃ <0. Аналогічним чином побудуємо і всі інші обмежуючі прямі. Таким чином, ми отримали n прямих: дві осі координат

(х₂ = 0, х₁ = 0) і n - 2 прямих (х₃ = 0..., х₄ = 0). Кожна з них визначає "допустиму півплощину", що лежить по одну її сторону. Частина площини, що належить одночасно всім цим півплощинам, утворює область допустимих рішень. ОДР - завжди являє собою опуклий багатокутник.

Можуть бути випадки, коли невід'ємних рішень системи не існує.

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

L = C₁x₁ + C₂x₂ + … + C_nx_n. (22.7)

Припустимо, що вільними змінними знову є х₁ і х₂, а базисними

х₃, х₄,..., х_n, виражені через вільні формули (22.6). Підставляючи вираз (22.6) в (22.7) наведемо подібні члени і висловимо лінійну функцію L всіх n змінних як лінійну функцію тільки двох вільних змінних х₁ і х₂:

L = g₀ + g₁x₁ + g₂x₂, (22.8)

Де g₀ - вільний член, який може з'являтися при переході до змінних

х₁, х₂.

Очевидно, що лінійна функція (22.8) досягає мінімуму при тих же значеннях х₁, х₂ що і функція L’ = g₁x₁ + g₂x₂ = L - g₀ без вільного члена.

Знайдемо ті значення де функція приймає мінімум, користуючись геометричною інтерпретацією. Додамо L 'деяке значення С: L’ = g₁x₁ + g₂x₂ = C отримаємо рівняння прямої на площині. Кутовий коефіцієнт цієї прямої дорівнює - g1/g2, а відрізок, що відсікається нею на осі ОХ₂ дорівнює С/g₂. Очевидно, якщо ми замінимо постійну С на С ' деяку іншу, кутовий коефіцієнт не зміниться. Пряма переміститься паралельно самій собі в нове положення. Таким чином, різним значенням С ' відповідають різні прямі на площині, але всі вони паралельні між собою. Очевидно, замість всіх цих прямих досить зобразити на площині одну основну пряму, наприклад L '= 0, а потім її можна подумки переміщати самій собі паралельно. При переміщенні цієї прямої в одну сторону L ' буде зростати, в іншу - убувати (це визначають коефіцієнти

g₁ іg₂).

При переміщенні основної прямої в напрямку, вказаному стрілками, лінійна форма L ' буде спадати. Очевидно найменшого значення вона досягне, коли пряма буде проходити через крайню точку ОДР, найбільш віддалену від початку координат в напрямку стрілок (в нашому випадку точка А). Координати цієї точки і визначають оптимальне рішення ОЗЛП. Знаючи оптимальне значення вільних змінних х₁, х₂, можна знайти, підставляючи їх у рівняння (22.6), і оптимальні значення базисних змінних, а також оптимальне значення цільової функції.

Незважаючи на те, що наведені побудови відносяться до окремого випадку, з нього випливають деякі загальні міркування, пов'язані взагалі до властивостей рішення ОЗЛП. Відзначимо ці закономірності:

1.Рішення ОЗЛП, якщо воно існує, не може лежати усередині області допустимих рішень, а тільки на її кордоні.

2.Решення ОЗЛП може бути і не єдиним. Дійсно, якщо основна пряма паралельна тій стороні багатокутника допустимих рішень, де досягається мінімум L ', то він досягається не на одній точці, а на всій цій стороні. В цьому випадку ОЗЛП має незліченну безліч оптимальних рішень.

3.ОЗЛП може не мати рішення, навіть у випадку, коли існує ОДР. Це буває тоді, коли в напрямку стрілок ОДР необмежена.

4.Рішення ОЗЛП, що мінімізує функцію L '(оптимальне рішення) завжди досягається в одній з вершин багатокутника допустимих рішень. Рішення, що лежать в одній з вершин ОДР, називається опорним рішенням, а сама вершина - опорною точкою.

5.Для того, щоб знайти оптимальне рішення, в принципі достатньо перебрати всі вершини ОДР і вибрати з них ту, де функція L досягає мінімуму.

6.Якщо число вільних змінних в ОЗЛП дорівнює 2, а число базисних m, і рішення ОЗЛП існує, то воно завжди досягається в точці, де принаймні дві з змінних х₁, х₂,..., хn звертаються в нуль.

Отметим, что для случая m = n –3, геометрическую интерпретацию задачи придется строить не на плоскости, а в пространстве, а это уже затруднительно и теряет свою наглядность.

Нам геометрическая интерпретация понадобилась для того, чтобы обосновать следующие свойства решения ОЗЛП при любых значениях числа переменных и числа уравнений m < n:

1.Оптимальное решение, если оно существует, лежит не внутри, а на границе ОДР, в одной из опорных точек, в каждой из которых по крайней мере k из переменных обращается в нуль (k = u – m).

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

Задача лінійного програмування з обмеженнями - нерівностями. Перехід від неї до ОЗЛП і назад.

На практиці обмеження в задачі ЛП часто задаються не рівняннями, а нерівностями. Покажемо, як можна перейти від завдання з обмеженнями-нерівностями до ОЗЛП. Нехай є задача лінійного програмування з n змінними х₁, х₂,..., х_n, в якій обмеження, накладені на змінні, мають вигляд лінійних нерівностей. У деяких з них знак нерівності може бути ³, а інших £ (другий вид зводиться до першого простий зміною знака обох частин). Тому поставимо всі обмеження-нерівності в стандартній формі:

(22.9)

Будемо вважати, що всі ці нерівності лінійно незалежні (тобто ніяке з них не можна уявити у вигляді лінійної комбінації інших). Потрібно знайти таку сукупність невід'ємних значень х₁, х₂,..., х_n, яка задовольняла б (21.9) і крім того, звертала б в мінімум цільову функцію: L = С₁х₁ + С₂х₂ + … + С_nх_n.

(22.10)

Де y₁, y₂,..., y_m - деякі нові змінні, які ми будемо називати "додатковими". Згідно з умовами (22.9), ці змінні так само як і х₁, х₂,..., х_n, повинні бути невід'ємними. Таким чином перед нами постає завдання лінійного програмування в такій постановці: знайти такі невід'ємні значення n + m змінних х₁, х₂,..., х_n; y₁, y₂,..., y_m, щоб вони задовольняли системі рівнянь (22.10) і одночасно звертали в мінімум цільову функцію. Як бачимо, перед нами в чистому вигляді ОЗЛП. Загальна кількість змінних одно m + n,

з них n - первинних і m - додаткових. Функція L виражена тільки через початкові коефіцієнти (додаткові в ній дорівнюють нулю).

Завдання ЛП з обмеженнями-нерівностями зведена нами до ОЗЛП але з великим числом змінних, ніж спочатку було в задачі.

Дата добавления: 2014-01-07