Лінійне програмування

Міністерство освіти РФ
Південно-Уральський державний університет
Кафедра Автоматики і управління
Реферат
з математичних основ теорії систем
на тему
Лінійне програмування
Виконав:
Група: ПС-263
Перевірив: різностатева О. А.
Челябінськ
2003

1. Введення
При постановці завдання організаційного управління, перш за все, важливо
1. Визначити мету, переслідувану суб'єктом управління.
2. Встановити, значеннями яких змінних досліджуваної системи можна варіювати.
Під метою будемо розуміти той кінцевий результат, який необхідно отримати шляхом вибору та реалізації тих чи інших управляючих впливів на досліджувану систему. У виробничо-комерційній сфері мета полягає в тому, щоб або максимізувати прибуток, або мінімізувати витрати.
Коли мета визначена, оптимальним вважається такий спосіб дій, який найбільшою мірою сприяє досягненню цієї мети. Однак «якість» реалізації процедури вибору залежить від того, наскільки повно відомі допустимі альтернативи керуючих впливів. Потрібно виявити повне безліч так званих керованих змінних. Важливим моментом при прийнятті управлінських рішень є ідентифікація некерованих змінних, тобто суб'єкта управління. Для побудови математичної моделі необхідно мати суворе уявлення про мету функціонування досліджуваної системи і мати інформацію про обмеження, які визначають область допустимих значень керованих змінних. Як мета, так і обмеження мають бути представлені у вигляді функцій від керованих змінних. Аналіз моделі повинен привести до визначення найкращого керуючого впливу на об'єкт управління при виконанні всіх установлених обмежень. При спрощеному описі реальних систем, на основі якого буде будуватися та чи інша модель, перш за все слід ідентифікувати домінуючі змінні, параметри і обмеження. Модель, будучи подальшим спрощенням образу системи-оригіналу, являє собою найбільш істотні для опису системи співвідношення у вигляді цільової функції і сукупності обмежень.
Найбільш важливим типом моделей є математичні моделі. В основі їх побудови лежить припущення про те, що всі релевантні змінні, параметри та обмеження, а також цільова фукцией кількісно вимірні. Тому якщо

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

(Цільова функція) при обмеженнях

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

2. Основні поняття теорії оптимізації
2.1. Загальна постановка задачі оптимізації
У загальній задачі потрібно знайти вектор

з допустимої області , Який звертає в мінімум цільову функцію q (x), тобто такий , Для якого
(1)
Якщо існує, то він визначає слабкий, глобальний (абсолютний) мінімум q * (x) у межах, дозволених . Слабкий, тому що задовольняє нестрогому нерівності. Глобальний, тому що нерівність справедливо для будь-яких x з області X. Мінімум при сильний, якщо для . Якщо поміняти знаки нерівностей - отримаємо сильний і слабкий максимуми. Мінімум в точці називається локальним (відносним), якщо знайдеться така околиця O (x *) точки , Що для всіх має місце . Якщо диференційовна, то завдання відшукання локальних мінімумів зводиться до знаходження стаціонарних точок, в яких звертаються в нуль приватні похідні q (x):
(2)
(2) - необхідна, але не достатня умова. Достатньою умовою існування в стаціонарній точці відносного мінімуму є позитивна визначеність квадратичної форми.

2.2. Обмеження на припустиме безліч
Теорема Вейєрштрасса: безперервна функція, визначена на непорожній замкнутому обмеженій множині, досягає мінімуму (максимуму) принаймні в одній з точок цієї множини.
2.3. Класична задача оптимізації
Полягає в знаходженні мінімуму цільової функції , Де - Точка в просторі при початкових обмеженнях типу рівностей
(3)
Якщо (3) мають місце, то мінімум q (x) називається умовним мінімумом. Якщо обмеження (3) відсутні, то говорять про безумовне мінімумі.
Класичний спосіб вирішення даної задачі полягає в тому, що (3) використовують для виключення з розгляду змінних. При цьому цільова функція приводиться до вигляду
(4)
, Де через позначені неісключаемие змінні. Завдання тепер полягає в знаходженні значень , Які звертають в мінімум q1 і на які не накладено обмежень (завдання на безумовний екстремум).
2.4. Функція Лагранж а
Введемо в розгляд вектор і досліджуємо властивості функції
(5)
- Функція Лагранжа, - Множники Лагранжа.
- Функція n + m змінних .
Розглянемо стаціонарні точки функції , Які одержимо, прирівнявши до нуля приватні похідні по і по :
(6)
(7)
Якщо в стаціонарній точці (x *, y *) функція досягає мінімуму, то забезпечує мінімум функції q (x) і при виконанні обмежень (3), тобто дає рішення задачі.
Завдання на умовний мінімум цільової функції q (x) при наявності обмежень типу рівностей зводиться до задачі на визначення стаціонарних точок функції Лагранжа .

3. Лінійне програмування: формулювання завдань та їх графічне рішення
3.1. Завдання ЛП
Розглянемо на прикладі задачі фірми Reddy Mikks. Невелика фабрик виготовляє два види фарб: для зовнішніх (E) і внутрішніх (I) робіт. Продукція надходить в оптову продаж. Для виробництва фарб використовуються два вихідних продукту - A і B. Максимально можливі добові запаси цих продуктів складають 6т і 8т відповідно. Витрати A і B на виробництво 1т відповідних фарб наведені в таблиці.

Вихідний продукт	Витрата на тонну фарби		Максимальний запас, т.
	фарба E	фарба I
A	1	2	6
B	2	1	8

Добовий попит на фарбу I ніколи не перевищує попиту на фарбу E більш ніж на 1т. Попит на I не перевищує 2т. Оптова ціна за 1т фарби E - 3000 $, I - 2000 $. Яка кількість фарби кожного виду фабрика повинна виробляти, щоб дохід від реалізації продуктів був максимальним?
Так як потрібно визначити обсяг виробництва кожного виду фарби, змінними в моделі є:
xE - добовий обсяг виробництва фарби E (у тоннах);
xI - добовий обсяг виробництва фарби I (у тоннах).
Позначивши дохід (в тис. $) через , Можна дати математичну формулювання цільової функції: визначити (допустимі) значення xE і xI, максимізує величину загального доходу
Обмеження на витрату вихідних продуктів:
(Для A)
(Для B)
Обмеження на величину попиту на продукцію:


Зажадаємо виконання умови невід'ємності змінних:

Отримали математичну модель:
Визначити добові обсяги виробництва (в т.) фарби I і E, при яких досягається
(Цільова функція)
при обмеженнях

3.2. Графічне рішення задачі ЛП
Побудуємо область допустимих рішень, в якій одночасно виконуються всі обмеження. Шукане простір рішень - багатокутник ABCDEF. Простір рішень містить нескінченну кількість точок, які є допустимими рішеннями, але, незважаючи на це, можна знайти оптимальне рішення, якщо з'ясувати, в якому напрямку зростає цільова функція моделі z = 3xE +2 xI. На графік наносять декілька паралельних ліній, відповідних рівнянню цільової функції при кількох довільно обраних і послідовно зростаючих значеннях , Що дозволяє визначити нахил цільової функції і напрям її збільшення. На видно, що оптимальному вирішенню відповідає точка C, що є перетином прямих

Вирішивши систему, одержимо

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

4. Алгебраїчний метод розв'язання задач
Використання графічного методу зручно при вирішенні завдань ЛЗ з цими двома змінними. При більшому їх числі необхідне застосування алгебраічского апарату.
Процес рішення задачі ЛП симплекс-методом носить ітераційний характер: однотипні обчислювальні процедури у певному послідовності виконуються до тих пір, поки не буде отримано оптимальне рішення.
4.1. Стандартна форма лінійних оптимізаційних моделей
1. Усі обмеження записуються як рівностей з неотрицательной правою частиною. Вихідний обмеження можна представити у вигляді рівності, додаючи залишкову зміну до лівої частини обмеження (віднімаючи надлишкову зміну з лівої частини).
Наприклад,

Введемо залишкову зміну s1> 0, тоді

Праву частина рівності можна зробити неотрицательной, помноживши обидві частини на -1.
2. Значення всіх змінних моделі ненегативні.
Будь-яку зміну yi, яка не має обмеження в знаку, можна представити як різниця двох невід'ємних змінних:

При будь-якому допустимому ухвалі тільки одне з цих змінних може приймати позитивне значення, тому що якщо , То , І навпаки. Це дозволяє розглядати як залишкову зміну, а - Як надлишкову.
3. Цільова функція підлягає максимізації або мінімізації.
Максимізація деякою функції еквівалентна мінімізації тієї ж функції, взятої з протилежним знаком, і навпаки.
Еквівалентність означає, що при одній і тій же сукупності обмежень оптимальні значення змінних у обох випадках будуть однакові.
4.2. Симплекс-метод
Загальну ідею симплекс-методу проілюструємо на прикладі моделі для задачі фірми Reddy Mikks. На вихідна точка алгоритму - початок координат (т. A) - початкова рішення. Від вихідної точки здійснюється перехід до деякою суміжною кутовий точці (т. B або т. F). Її вибір залежить від коефіцієнтів цільової функції. Оскільки коефіцієнт при xE більше коефіцієнта при xI, а цільова функція підлягає максимізації, у потрібному напрямку переходу відповідає збільшенню xE (т. B). Далі зазначений процес повторюється для з'ясування, чи існує інша екстремальна точка, відповідна краще допустимому рішенню.
Правила вибору екстремальної точки:
1. Кожна наступна кутова точка повинна бути суміжною з попереднім.
2. Зворотний перехід до попередньої екстремальній точці неспроможна здійснюватися.
Щоб описати розглянуті процедури формальними способами, необхідно визначити простір прийняття рішень та кутові точки алгебраїчно. Необхідні співвідношення встановлюються за таблицею:

Геометричне визначення (графічний метод)	Алгебраїчне визначення (симплекс-метод)
Простір рішень	Обмеження моделі стандартної форми
Кутові точки	Базисні розв'язання задачі у стандартному вигляді

4.2.1. Уявлення простору рішень стандартної задачі ЛП.
Модель:
максимізувати цільову функцію

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

На - простір рішень. Кожну точку можна визначити за допомогою

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

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

Екстра.	змінні
точка	нульові	ненульові
A
B
C
D
E
F

З таблиці виділимо закономірності:
1. Стандартна модель містить чотири рівняння і шість невідомих, у кожної з екстремальних точок (6-4) перемінні повинен мати нульові значення.
2. Суміжні екстремальні точки відрізняються лише однієї змінної в кожній групі (нульових і ненульових змінних).
Якщо лінійна модель стандартної форми містить рівнянь і невідомих, то всі допустимі екстремальні точки визначаються як усі однозначні невід'ємні рішення системи рівнянь, в яких mn змінних дорівнюють нулю. Однозначні рішення такої системи - базисні рішення. Якщо вони задовольняють вимогу неотрицательности правих частин, то це - допустимий базисне рішення. Змінні, рівні нулю - небазисних, решта - базисні. Кожну наступну екстремальну точку можна визначити визначити шляхом заміни однієї з поточних небазисних змінних поточної базисної змінної. У нашому прикладі при переході з т. A в т. B необхідно збільшувати небазисную змінну від вихідного нульового значення до значення, відповідного т. B. У т. B s2 звертається в нуль (стає небазисной). Т.ч., відбувається взаємообмін xE і s2 між небазисних і базисними змінними.
Включається змінна - небазисная в момент змінна, яка буде включена в безліч базисних змінних на наступній ітерації. Исключаемая змінна - базисна в даний момент змінна, яка на наступній ітерації підлягає виключенню з безлічі базисних змінних.
4.2.2 Обчислювальні процедури симплекс-методу
Симплекс-алгоритм:
Крок 0: Використовуючи лінійну модель стандартної форми, визначають НДБР шляхом прирівнювання до нуля nm (небазисних) змінних.
Крок 1: З-поміж поточних небазисних змінних вибирається включається в новий базис мінлива, збільшення якої забезпечує поліпшення значення цільової функції. Якщо її немає - поточний базисне рішення оптимально, інакше перехід до кроку 2.
Крок 2: З числа змінних поточного базису вибирається исключаемая змінна, яка повинна стати небазисной при введенні до складу базису нової змінної.
Крок 3: Знаходиться нове базисне рішення, відповідне нових складів базисних і небазисних змінних. Перехід до кроку 1.

Якщо xE = xI = 0, то

(Відповідає точці A Ha) - Початкове допустиме рішення.

								Рішення
		-3	-2
			2					6
		2						8
		-1
								2

Якщо в задачі максимізації все небазисних змінні в -Рівнянні мають невід'ємні коефіцієнти, отримане пробне рішення є оптимальним. Інакше як нової базисної змінної слід вибрати ту, яка має найбільший за абсолютною величиною від'ємний коефіцієнт. Застосовуючи цю умову до вихідної таблиці - змінна, що включається в базис.
Процедура вибору підключається перемінної передбачає перевірку умови допустимості, що вимагає, щоб в якості исключаемой змінної вибиралась та (з поточного базису), яка першою звертається в нуль при збільшенні включається змінної аж до значення, відповідного суміжною екстремальній точці.
Відношення, що її ідентифікує исключаемую зміну, можна визначити з симплекс-таблиці. Для цього в стовпці введеної перемінної викреслюються негативні і нульові елементи обмежень. Потім обчислюються відносини постійних з правих частин обмежень до інших елементам шпальти. Исключаемая змінна - та, для якої це відношення мінімально.
Стовпець, асоційований з введеної перемінної - провідний стовпець; рядок, відповідний исключаемой змінної - провідна рядок; на їх перетині - провідний елемент.
Пошук нового базисного рішення здійснюється методом виключення змінних (метод Жордана-Гаусса). Цей процес включає в себе обчислювальні процедури двох типів.
Тип 1. Формування ведучого рівняння
Нова ведуча рядок = попередня провідна рядок / провідний елемент
Тип 2. Формування решти рівнянь
Нове рівняння = попереднє рівняння - (коефіцієнт ведучого шпальти попереднього рівняння) * (нова ведуча рядок)
Нова симплекс-таблиця, отримана після проведення розглянутих операцій:

xI - вводиться змінна (тому що коефіцієнт у -Рівнянні -1 / 2). Исключаемая мінлива s1, (відношення 4 / 3 - мінімальний). Знову проведемо обчислення двох типів. Остання симплекс-таблиця відповідає оптимальному вирішенню завдання, тому що в -Рівнянні жодна з небазисних змінних не фігурує з негативними коефіцієнтами.
У випадку мінімізації цільової функції в цьому алгоритмі необхідно змінити тільки умова оптимальності: як нової базисної змінної слід вибирати зміну, що у -Рівнянні має найбільший позитивний коефіцієнт. Умови допустимості в обох випадках однакові.

4.2.3. Штучне початкова рішення
Для отримання початкового базисного рішення ми використовували залишкові змінні. Однак коли вихідне обмеження записано у вигляді рівності або має знак, не можна відразу ж отримати НДБР. Тому були розроблені два методи, в яких використовується «штрафування» штучних змінних.
1. Метод великих штрафів (М-метод)
Розглянемо лінійну модель, приведену до стандартної формі:
мінімізувати

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

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

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

Тепер якщо

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

отримаємо вираз для :

Рішення представлено у зведеній таблиці:
2. Оскільки цільова функція мінімізується, змінні, що включаються в базис, повинні мати найбільші позитивні коефіцієнти в -Рівнянні. Оптимум досягається, коли всі небазисних змінні мають коефіцієнти в -Рівнянні. Оптимального рішення відповідає точка .
Оскільки в оптимальному рішенні відсутні штучні змінні, що мають позитивне значення, то дане рішення - дозволене оптимальне рішення задачі в її стандартної постановці.
3. Двоетапний метод
Етап 1. Вводяться штучні змінні, необхідні для отримання стартової точки. Записується нова цільова функція, яка передбачає мінімізацію суми штучних змінних при вихідних обмеженнях, видозмінених за рахунок штучних змінних. Якщо мінімальне значення нової цільової функції дорівнює нулю (тобто всі штучні змінні в оптимумі дорівнюють нулю), то вихідна задача має допустиме рішення і переходимо до Етапу 2.
Етап 2. Оптимальне базисне рішення, отримане на Етапі 1, використовується в якості початкової умови вихідної задачі.
Розглянемо на прикладі.
Етап 1.
Мінімізація

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


Оскільки , Можна переходити до Етапу 2.
Етап 2. Вихідну завдання сформулюємо наступним чином:
мінімізувати

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

Тепер, прирівнявши x3 = 0, отримаємо НДБР

Для вирішення завдання необхідно підставити в цільову функцію висловлювання для базисних змінних x1 і x2:


5. Двоїстість.
Двоїста задача - допоміжна завдання ЛП, формулируемая за допомогою певних правил безпосередньо з вихідної, або прямої задачі.
Пряма задача ЛП у стандартній формі:
максимізувати (мінімізувати)

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

До складу включаються надлишкові і залишкові змінні.
Для формулювання двоїстої задачі розташуємо коефіцієнти прямої задачі згідно зі схемою:
· Кожному обмеження прямої задачі відповідає мінлива двоїстої задачі;
· Кожному змінної прямої задачі відповідає обмеження двоїстої задачі;
· Коефіцієнти при деякої змінної, що фігурують в обмеження прямої задачі, стають коефіцієнтами лівій частині відповідного обмеження двоїстої задачі, а коефіцієнт, що фігурує при тій же змінної у виразі для цільової функції прямої задачі, стає постійною правій частині цієї ж обмеження двоїстої задачі.
Інформація про інші умови двоїстої задачі (напрям оптимізації, обмеження і знаки двоїстих змінних) представлена ​​в таблиці:
Розглянемо приклад:
Пряма задача:
максимізувати

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

Пряма задача в стандартній формі:
максимізувати

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

Двоїста задача:
мінімізувати

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

(Означає, що y1> 0). y1, y2 не обмежені в знаку.