Лекції - Теорія систем і системний аналіз

Тема 1.Лекція 1_Вводная.doc (1 стор.)
Тема 2.Лекція 2_Основние понятія.doc (1 стор.)
Тема 3_Реалізація СА, показателі.doc (1 стор.)
Тема 4_Вибор.doc (1 стор.)
Тема 5.Лекція 5_ЛП.doc (1 стор.)
Тема 5.Лекція 6_НП.doc (1 стор.)
Тема 6_Лекція 7_ Багатокритеріальні задачі.doc (1 стор.)
Тема 7_Лекція 8_Вибор в умовах ріска.doc (1 стор.)
Тема 8-9_Лекція 10_Ігра з природою, СА істочніков.doc (1 стор.)
Тема 8_Лекція 9_Теорія ігр.doc (1 стор.)
Оригінал


Тема 5. Л екция 5.

умовна оптимізація.

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


  1. Приклад постановки задачі оптимізації

  2. Лінійне програмування (ЛП)

    1. Постановка задачі лінійного програмування

    2. Основні визначення та теореми

    3. Перехід від однієї форми завдання ЛП до іншої

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

1. Приклад постановки задачі оптимізації



Для виготовлення 3-х видів виробів А, В і С використовується токарне, фрезерне, зварювальне та шліфувальне обладнання. Витрати часу на обробку одного виробу наведені в таблиці.


Тип обладнання

Витрати часу (станко-ч.) на обробку одного виробу виду

Загальний фонд робочого часу

А

В

З

Фрезерне

2

4

5

120

Токарна

1

8

6

280

Зварювальне

7

4

5

240

Шліфувальне

4

6

7

360

Прибуток

10

14

12





Визначити, скільки виробів і якого виду слід виготовити підприємству, щоб прибуток від їх реалізації був максимальним. Скласти математичну модель задачі.

Рішення.

Нехай буде виготовлено Х 1 одиниць виробу А

Х 2 одиниць вироби В

Х 3 одиниць вироби С.

Тоді при використанні фрезерного устаткування буде потрібно затратити 2Х 1 + 4Х 2 + 5Х 3 верстато-годин.

Але по умові обмеження загального фонду часу

1 + 4Х 2 + 5Х 3  120.

Аналогічно для токарного, зварювального та шліфувального обладнання:

Х 1 + 8Х 2 + 6Х 3  280

1 + 4Х 2 + 5Х 3  240

1 + 6Х 2 + 7Х 3  360

При цьому, оскільки кількість виготовлених деталей не може бути негативним, то

Х 1  0, Х 2  0, Х 3  0.


Далі, якщо буде виготовлено Х 1 виробів А, Х 2 виробів В і Х 3 виробів С, то прибуток від їх реалізації складе


F = 10Х 1 + 14х 2 + 12Х 3


Отже, ми отримуємо систему чотирьох лінійних нерівностей з трьома невідомими (X j (j = 1 ... 3):


1 + 4Х 2 + 5Х 3  120

Х 1 + 8Х 2 + 6Х 3  280

1 + 6Х 2 + 7Х 3  360

Х 1  0, Х 2  0, Х 3  0.


і лінійну функцію F = 10Х 1 + 14х 2 + 12Х 3 щодо цих же змінних.

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


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


2.1. Постановка задачі лінійного програмування


Знайти оптимум (найбільше або найменше значення) цільової функції (лінійної форми)

на області допустимих значень системи обмежень





при наявності додаткових умов невід'ємності змінних

х j  0, j = 1, ..., n.

Якщо в системі обмежень l = m, тобто вона складається тільки з рівнянь, то відповідна форма запису називається канонічної.

2.2. основні визначення та теореми


2.2.1. Визначення


  1. Функція F (X) (1) називається цільовою функцією, або лінійною формою завдання, а умови (2) - (4) - обмеженнями даного завдання.

  2. Стандартної (або симетричної) завданням ЛП є задача, яка полягає у визначенні максимального значення функції F (X) при виконанні умов (3), (4).

  3. Канонічної чи основним завданням ЛП називається задача, яка полягає у визначенні максимального значення функції F при виконанні умов (2), (4).

  4. Сукупність чисел Х (х 1 х 2,... х n), яка задовольняє обмеженням задачі (1) - (4) називається допустимим рішенням, або планом.

  5. План Х * (х * 1 х * 2,... х * n), при якому цільова функція задачі приймає максимальне значення, називається оптимальним.


Властивості основного завдання ЛП тісно пов'язані з властивостями так званих опуклих множин.

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


Визначення 1. Нехай х 1 х 2,... х n - довільні точки евклідового простору. Опуклою лінійною комбінацією цих точок називається сума

1 х 1 +  2 х 2 + ...  n х n,

де  - довільні невід'ємні числа, сума яких дорівнює 1.



Визначення 2. Безліч називається опуклим, якщо разом з будь-якими двома своїми точками воно містить і їх довільну опуклу лінійну комбінацію.

Визначення 3. Непорожнє безліч планів основної задачі ЛП називається багатогранником рішень, а всяка кутова точка багатогранника - вершиною.

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


2.2.2. Теореми

Тепер сформулюємо теореми про властивості основного завдання ЛП.

Теорема 1.

Безліч планів основної задачі ЛП є опуклим (якщо воно непорожній).

Теорема 2.

Якщо основна задача ЛП має оптимальний план, то максимальне значення цільова функція приймає в одній з вершин багатогранника рішень.

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


2.3.Переход від однієї форми завдання ЛП до іншої


Як вже було сказано вище, існують стандартна форма задачі лінійного програмування і канонічна форма. У будь-якому випадку шукається екстремум цільової функції, тобто або максимум, або мінімум. Таким чином, можна виділити завдання на максимум і завдання на мінімум. Існують правила переходу від однієї форми завдання ЛП до іншої, тобто перехід від задачі на пошук максимуму цільової функції до задачі пошуку мінімуму цільової функції цільової функції (Fmax  Fmin), а також перехід від стандартної задачі ЛП до канонічної і навпаки (стандартна  канонічна). Розглянемо ці правила.


2.3.1. Зведення задачі мінімізації до задачі максимізації:


F = c 1 x 1 + c 2 x 2 + ... c n x n  min зводиться до

F =-F = - c 1 x 1 - c 2 x 2 - ... c n x n  max;


2.3.2. Перехід від стандартної задачі до канонічної.


Обмеження - нерівність () вихідної задачі можна перетворити в обмеження - рівність додаванням до його лівої частини додаткової неотрицательной змінної, тобто

i 1 х 1 +  i 2 х 2 +  i 3 x 3 + ...  in х n  () b i перетвориться в

i1 х 1 +  i2 х 2 +  i3 x 3 +  in  х n + x n +1 = b i


Число вводяться додаткових невід'ємних змінних при перетворенні обмежень - нерівностей в обмеження - рівності дорівнює числу перетворюваних нерівностей.



2.3.3. Перехід від канонічної задачі до стандартної:

i 1 х 1 +  i 2 х 2 +  in х n = b i

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

i1 х 1 +  i2 х 2 + ...  in х n  b i

  i1 х 1   i2 х 2  ...  in х n   b i


3. Методи рішення задач нелінійного програмування.

Геометрична інтерпретація

3.1. Геометричний спосіб

3.1.1. Приклад геометричній інтерпретації задачі ЛП

3.1.2. Етапи рішення задачі


Існують два основні методи рішення задачі лінійного програмування: рішення на основі геометричної інтерпретації (геометричний спосіб) і так званий симплекс-метод.

3.1. Геометричний спосіб.

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


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


Таким чином, рішенням задачі буде та кутова точка ОДР, яка є крайньою в напрямку лінії рівня.
Непорожня множина задачі ЛП утворює опуклий багатогранник. Кожна вершина багатогранника являє собою опорний план. В одній з вершин багатокутника (тобто для одного з опорних планів значення цільової функції є максимальним (за умови, що функція обмежує зверху на безлічі планів.

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

Знаходження мінімального значення F відрізняється від знаходження максимального її значення при тих же обмеженнях лише тим, що ЛУ пересувається не в напрямку С, а в протилежному.

Відзначимо властивості цільової функції і обмежень

  1. Цільову функцію можна множити на будь-яку позитивну const.

  2. До цільової функції можна додавати будь-яку const.

  3. З обмеженнями можна як з системою рівностей або нерівностей проводити еквівалентні алгебраїчні перетворення.


Приклад: Знайти рішення задачі ЛП при наступних даних:


F = 2 X 1 + 3 X 2 ® max при

4 X 1 + 3 X 2  12 (1)

X 1 - X 2  1 (2)

- X 1 + 6 X 2  12 (3)


X 1, X 2  0 (4)

Область допустимих рішень задачі (ОДР), або безліч планів задачі являє собою багатокутник, обмежений прямими - геометричним вираженням рівнянь, перетворених з нерівностей (1) - (3). По черзі прирівнюючи в рівняннях (1) - (3) Х 1 і Х 2 до нуля, а також використовуючи умову (4), будуємо прямі, визначаємо півплощини, що відповідають кожному обмеженню задачі і отримуємо багатокутник ABCD (див. рис.1). Кожна вершина багатокутника являє собою опорний план.

Примітка: щоб правильно визначити допустиму полуплоскость, зручно орієнтуватися по знаку при змінній X 2. Якщо це мінус, а в нерівності знак , то допустимі рішення будуть лежати нижче прямої, якщо знак , полуплоскость будується вгору від прямої. Якщо знак при другій змінної плюс, то, відповідно, площини будуються в протилежних напрямках).

В одній з вершин багатокутника (тобто в одному з опорних планів) значення цільової функції є максимальним (за умови, що функція обмежена зверху на безлічі планів). Пункти 1-3 виконані. Будуємо спрямовує вектор. Початок його збігається з початком координат, а кінець має координати 1; С 2), відповідні коефіцієнтам в цільовій функції. У нашому випадку (2, 3).




Рис. 1
Вектор (2, 3) показує напрямок росту цільової функції. Для визначення вершини багатокутника побудуємо лінію рівня F = 2 X 1 + 3 X 2 = h, що проходить через багатокутник рішень. Спочатку покладемо h = 6. Неважко бачити, що лінія рівня перпендикулярна направляючому вектору. Задавши нове значення h, більше попереднього, ми пересуваємо лінію рівня у напрямку вектора . Точка, в якій лінія рівня покидає ОДР (в нашому випадку це точка С) і буде вирішенням завдання, тобто оптимальним планом. Однак, визначивши точку на кресленні, необхідно визначити точне значення її координат, тобто змінних X 1 і X 2. Оскільки точка С знаходиться на перетині прямих, відповідних рівняннях (1) і (3), вирішуючи спільно ці рівняння, отримаємо значення X 1 = 1,33 і X 2 = 2,22.

Рішення записується у вигляді X (1,33; 2,22).

Підставивши знайдені значення змінних у вираз для цільової функції, обчислюємо її максимальне значення: F = 9,33.


3.1.2. Етапи рішення задачі ЛП на основі її геометричної

інтерпретації


Підводячи підсумок розгляду процесу рішення задачі лінійного програмування геометричним способом, можна виділити наступні його етапи:


    1. будують прямі, рівняння яких виходять в результаті заміни в обмеженнях знаків нерівностей на знаки точних рівностей;

    2. знаходять півплощини, що визначаються кожним з обмежень задачі;

    3. знаходять багатокутник рішень;

    4. будують вектор С = (С 1, С 2);

    5. будують пряму З 1 Х 1 + С 2 Х 2 = h, що проходить через багатокутник рішень;

    6. пересувають пряму З 1 Х 1 + С 2 Х 2 = h в напрямку вектора З, в результаті чого знаходять або точку (точки), в якій цільова функція приймає максимальне значення, або встановлюють необмеженість зверху функції на множині планів;

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


Можливі випадки знаходження рішення геометричній інтерпретації ЛП

  1. Цільова функція не обмежена зверху на безлічі припустимих рішень;

  2. Випадок, коли система обмежень несумісна.
Навчальний матеріал
© uadoc.zavantag.com
При копіюванні вкажіть посилання.
звернутися до адміністрації