План читання лекцій з навчальної дисципліни «Математичні методы»

Юридичний техникум.

Розглянуто і схвалено ПЦК р. Кропоткіна программирования.

Голова ПЦК.

Покалицына О.В.

План читання лекцій з навчальної дисциплине.

«Математичні методи» Розділ № 2. Лінійне програмування. Тема № 2.2. Основне завдання лінійного програмування. Заняття №.

Місце проведення: аудиторія. Література: 1. Венцель Е. С. Дослідження операцій. Завдань, принципи, методологія. — М.: Наука, 1980. 2. Шелобаев С.І. Математичні методи лікування й моделі у економіці, фінансах, бізнесі. — М.:ЮНИТИДАНА, 2001.

Навчальні і питання розрахунок часу |№п/п |Навчальні питання |Час, мин|Методические | | | | |вказівки | |1. |Основне завдання ЛЗ (ОЗЛП). | | | |2. |Існування рішення. | | |.

Вступна частина. Організаційний момент. План заняття. Найвища вимога. Більшість. 1. Основне завдання ЛЗ (ОЗЛП).

Будь-яку завдання лінійного програмування можна зводити до стандартної формі, так званої «основний завданню лінійного програмування» (ОЗЛП), що формується так: знайти неотрицательные значення перемінні x1, x2, …, xn, які відповідали б умовам — равенствам: a11×1 + a12×2 + … +a1n xn = b1, a21×1 + a22×2 + … +a2n xn = b2, (6.1.).

… am1 x1 +am2 x2 + … +amn xn = bm. і звертали в максимум лінійну функцію цих переменных:

[pic] (6.2.).

Випадок, коли L слід звернути над максимум, а мінімум, легко зводиться до простого: змінити знак L на зворотний (максимізувати не L, а L`=-L). З іншого боку, від будь-яких умов — нерівностей можна можливість перейти до умовам — равенствам ціною запровадження деяких нових «додаткових» змінних. Нехай потрібно знайти неотрицательные значення змінних x1, x2,x3, задовольняють обмеженням — неравенствам.

[pic] (6.3.).

[pic] і обертаючі в максимум лінійну функцію від результатів цих переменных:

[pic] (6.4.).

Почнемо сіло, що наведемо умови (6.3.) до стандартної формі, так, щоб знак нерівності був (, а справа стояв нуль. Получим:

[pic] (6.5.).

[pic].

Нині ж позначимо ліві частини нерівностей (6.5.) відповідно через y1 і y2:

[pic] (6.6.).

[pic].

З умов (6.5.) і (6.6.) видно, нові перемінні y1, y2 також би мало бути неотрицательными.

Яка ж тепер маємо поставлено завдання? Знайти неотрицательные значення змінних x1, x2,x3,y1,y2 такі, що вони задовольняли умовам — равенствам (6.6.) і звертали в максимум лінійну функцію цих змінних (те що L не входить додаткові перемінні y1, y2, неважливо: можна вважати, що вони входять, але з нульовими коефіцієнтами). Перед нами — основне завдання лінійного програмування (ОЗЛП). Перехід до неї від початкової завдання з обмеженнями — неравенствами (6.3.) «куплений» ціною збільшення кількості змінних на два (число нерівностей). 2. Існування рішення ОЗЛП та засоби її нахождения.

Розглянемо основне завдання лінійного програмування (ОЗЛП): знайти неотрицательные значення змінних x1, x2, …, xn, задовольняють m умовам — равенствам: a11×1+a12×2+…+a1n xn=b1, a21×1+a22×2+…+a2n xn=b2, (7.1.).

… am1 x1+am2 x2+…+amn xn=bm.

и обертаючі в максимум лінійну функцію цих переменных:

[pic] (7.2.).

Для простоти припустимо, що умови (7.1.) лінійно незалежні (r=m), і вести міркування у тому предположении.

Назвемо ДОПУСТИМИМ рішенням ОЗЛП будь-яку сукупність неотрицательных значень x1, x2, …, xn, що б умовам (7.1.). ОПТИМАЛЬНЫМ назвемо те з допустимих рішень, яке звертає в максимум функцію (7.2.). Потрібна знайти оптимальне рішення. Чи завжди це завдання має рішення? Ні, який завжди. 1. Може бути, що рівняння (7.1.) взагалі несумісні (суперечать одна одній). 2. Може бути й дуже, що вони сумісні, але не області неотрицательных рішень, тобто. немає жодної сукупності чисел x1(0, x2(0, …, xn (0, задовольняє умовам (7.1.). 3. Нарешті, може бути отже допустимі рішення ОЗЛП існують, але у тому числі немає оптимального: функція L у сфері допустимих рішень не обмежена сверху.

[pic].

Щоб краще уявити собі принципову бік ОЗЛП, звернімося геометричній інтерпретації. Нехай число рівнянь m на два менше ніж змінних n (n-m=k=2). Такий окреме питання дає можливість геометричній інтерпретації ОЗЛП на плоскости.

Ми знаємо, що n лінійно незалежних рівнянь (7.1.) можна дозволити щодо якихось m базисних змінних, висловивши їх крізь інші, вільні, кількість яких одно n-m=k (у разі k=2). Припустимо, що вільні перемінні - це x1 і x2 (якщо тут інше, то можна наново перенумерувати перемінні), інші ж: x3, x4, …, xn — базисні. Тоді замість m рівнянь (7.1.) ми матимемо теж m рівнянь, але записаних на другий формі, дозволених щодо x3, x4, …; x3=a31×1+a32×2+(3, x4=a41×1+a42×2+(4, (7.3.).

… xn=an1 x1+an2 x2+(n.

Будемо зображати пару значень вільних змінних точкою з координатами x1, x2 (рис. 9.1.). Оскільки перемінні x1, x2 мали бути зацікавленими неотрицательными, то допустимі значення вільних змінних лежать лише вище осі Ox1 (де x2=0) і правіше осі Ox2 (де x1=0). Це відзначимо штрихуванням, що означає «допустиму» бік кожної оси.

Тепер побудуємо на площині x1Ox2 область допустимих рішень або ж переконаємося, що її існує. Базисні перемінні x3, x4, …, xn теж повинні прагнути бути неотрицательными і задовольняти рівнянням (7.3.). Кожне таке рівняння обмежує область допустимих рішень. [pic].

Справді, між іншим у першому рівнянні (7.3.) x3=0; одержимо рівняння прямий линии:

[pic].

І на цій прямий x3=0; з одного боку від неї x3>0, з іншого — x30 (рис. 7.2.). Нехай цей бік виявилася правіше і від прямий x3=0. Отже, вся область допустимих рішень (ТДР) лежать у першому координатном вугіллі, правіше і від прямий x3=0. Аналогічно вчинимо і всіма іншими умовами (7.3.). І з них зобразиться прямий зі штрихуванням, що б «допустиму» полуплоскость, де і може лежати рішення (рис. 7.3.).

[pic].

Отже, ми побудували n прямих: дві осі координат (Ox1 і Ox2) і n-2 прямих x3=0, x4=0, …, xn=0. Кожна їх визначає «допустиму» полуплоскость, де може лежати рішення. Частина першого координатного кута, що належить одночасно всього цього полуплоскостям, це і є ТДР. На рис. 7.3. показаний випадок, коли ТДР існує, тобто. система рівнянь (7.3.) має неотрицательные рішення. Зауважимо, цих рішень — нескінченне безліч, оскільки будь-яка пара значень вільних змінних, узяте з ТДР, «годиться», та якщо з x1 і x2 можуть визначити і базисні перемінні. [pic].

Може бути, що область допустимих рішень немає, і отже, рівняння (7.3.) несумісні у сфері неотрицательных значень. Такий випадок показаний на рис. 7.4., де не існує сфери, лежачої одночасно по «потрібну» кращий бік від всіх прямих. Отже, ОЗЛП немає решения.

Припустимо, що область допустимих рішень існує, і ми її побудували. Які ж знайти у тому числі оптимальное?

І тому дамо геометричну інтерпретацію умові (7.2.) L (max. Підставивши висловлювання (7.3.) в формулу (7.2.), висловимо L через вільні перемінні x1, x2. після виконання подібних членів получим:

[pic] (7.4.).

де (1, (2 — якісь коефіцієнти, (0 — вільний член, що його початковому вигляді у функції L був; тепер, за переходу до змінним x1, x2, міг і з’явиться. Але ми її одразу і відкинемо: адже максимум лінійної функції L характеризується тієї ж значеннях x1, x2, як і максимум однорідної лінійної функції (без вільного члена):

[pic] (7.5.).

Подивимося, як зобразити геометрично умова L'(max. Поклавши спочатку L'=0, тобто. [pic]и побудуємо на площині x1Ox2 пряму з такою рівнянням; очевидно, вона просто проходить через початок координат (рис. 7.5.) [pic] Назвемо її «опорною прямий». Якщо ми надавати L' якісь значення C1, C2, C3, …, пряма переміщатиметься паралельно сама собі; при переміщенні до однієї бік L' зростатиме, до іншої - убувати. Зазначимо на рис. 7.5. стрілками, поставленими у опорною рамою, то напрям, в якому L' зростає. На рис. 7.5. це напрям «направо — вгору», але може бути й навпаки: все залежить від коефіцієнтів (1, (2. тепер зобразимо опорну пряму і ТДР однією кресленні (7.6.). Давайте будемо подумки рухати опорну пряму паралельно сама собі у бік стрілок (зростання L'). Коли L' досягне максимуму? Вочевидь, у точці A (крайній точці ТДР у бік стрілок). У цьому точці вільні перемінні приймають оптимальні значення x1*, x2*, та можна за формулам (7.3.) знайти й оптимальні значення решти (базисних) змінних x3*, x4*, …, xn*. Зауважимо, що максимум L' буває у однієї з вершин ТДР, де, по крайнього заходу, дві з базисних змінних (у нашій разі це x3 і x5) звертаються до нуль. Могло б звертатися до нуль і більше базисних змінних, якби через точку, А проходило більше двох прямих xi=0. [pic].

Чи, можливо чи виявитися, що оптимального рішення немає? Так, може, тоді як ТДР функція L' (отже, і L) не обмежена згори. Приклад такого ненормального випадку показаний на рис. 7.7. (в розумно поставлених завданнях зазвичай такої непорозуміння немає). [pic].

На рис. 7.6. оптимальне рішення існувало й був єдиним. А зараз розглянемо випадок, коли оптимальне рішення існує, але з єдино (їхнє нескінченне безліч). Це випадок, коли максимум L' досягається над одній точці А, але в цілому відрізку АВ, паралельному опорною прямий (рис. 7.8.). [pic].

Отже, ми розглянули в геометричній інтерпретації випадок n-m=k=2 і переконались у наступному: оптимальне рішення (коли вона існує) завжди буває у одній з змінних x1, x2, …, xn рівні нулю.

Виявляється, аналогічне правило справедливе й у разі n-m=k>2 (лише геометрична інтерпретація втрачає у разі свою наочність). Обійдемося без докази, просто сформулюємо це правило.

Оптимальний рішення ОЗЛП (коли вона існує) характеризується такий сукупності значень змінних x1, x2, …, xn, де, по крайнього заходу, k з них звертаються до нуль, інші ж неотрицательны.

При k=2 така сукупність значень змальовується точкою на площині, що у одній з вершин багатокутника допустимих рішень (ТДР). При k=3 ТДР є не багатокутник, а багатогранник, та оптимальну рішення буває у одній з його вершин. При k>3 геометрична інтерпретація втрачає наочність, та все ж геометрична термінологія залишається зручною. Ми продовжуватимемо казати про «многограннике допустимих рішень» в k-мерном просторі, а оптимальне рішення (коли вона існує) досягатиметься водної з вершин цього багатогранника, де, по крайнього заходу, k змінних рівні нулю, інші ж — неотрицательны. Будемо для стислості називати таку вершину «опорною точкою», а випливає з неї рішення «опорним решением».

Звідси випливає ідея, що у основі більшості робочих методів рішення ОЗЛП, — ідея «послідовних проб». Справді, спробуємо дозволити рівняння (7.1.) щодо каких-нибудь m базисних змінних і висловимо їх крізь інші k вільних. Спробуємо покласти ці вільні перемінні рівними нулю — може повезе, наткнёмся на опорну точку. Обчислимо базисні перемінні при нульових значеннях вільних. Якщо всі вони виявилися неотрицательными, отже, нам пощастило, відразу ж одержимо дозволене (опорне) рішення, та її залишається тільки оптимізувати. Якщо ж немає? Отже, даний вибір вільних і базисних змінних припустимого рішення не дає; точка лежить не так на кордоні, а поза ТДР. Що робити? Треба «пере дозволити» рівняння щодо якихось інших базисних змінних, але як потрапило, а те щоб це наближало нас до області допустимих рішень (при цьому в лінійному програмуванні існують спеціальні прийоми, у яких ми думати). Нехай, нарешті, кілька разів повторивши таку процедуру, ми знайшли опорне рішення ОЗЛП. Але це не все. Тут треба порушити питання: а чи це рішення оптимальним? Висловимо функцію L через останні утворені вільні перемінні і спробуємо збільшити їх понад нуля. Якщо від імені цієї значення L лише зменшується, отже, нам пощастило, і ми знайшли оптимальне рішення, ОЗЛП вирішена. Якщо ж немає? Знову «пере дозволяємо» систему рівнянь щодо інших базисних змінних, і знову абияк, а так щоб, виходячи межі допустимих рішень, наблизитися до оптимальному. І зновутаки при цьому в лінійному програмуванні існують спеціальні прийоми, гарантують, що з кожну нову «пере вирішенні» ми наближатися оптимального рішенню, а чи не віддалятися від нього. Цими прийомах ми теж не зупинятимемося. Після кінцевого числа таких кроків мета буде досягнуто — оптимальне рішення знайдено. Якщо ж не існує? Алгоритм рішення ОЗЛП сам покаже вам, що рішення нет.

Для простих завдань, де число змінних невелика, такий «сліпий перебір» можуть призвести до вирішення, і досить швидко. Але практично часто зустрічаються завдання, у яких число змінних (і накладених умов) дуже велике, порядку сотень і навіть тисяч. Для завдань простий перебір стає практично неможливим: дуже велика число комбінацій вільних і базисних змінних. Приклад: лише за n=30 і m=10 число можливих комбінацій вільних змінних з засадничими одно, [pic]т.е. понад 30 мільйонів! а ця завдання — далеко ще не з сложных.

Розробленим у теорії лінійного програмування обчислювальні методи («симплекс-метод», «двоїстий симплекс-метод» та інші) дозволяють знаходити оптимальне рішення не «сліпим» перебором, а «цілеспрямованим», з постійним наближенням рішенню. Додамо, що сумісні ЕОМ, як правило, обладнані подпрограммами вирішення завдань лінійного програмування, отже особі, бажаючому розв’язати, немає особливої потреби навчатися рішенню завдань «вручну» — працю вкрай неприємний і изнурительный.