Головна

Знаходження оптимуму лінійної функції

  1.  C. Лінійної щільністю іонізації називається відношення кількості пар іонів, утворених зарядженою іонізуючою частинкою на елементарному шляху до цього шляху.
  2.  I. Метаморфози кореня, спеціалізовані на запасающей функції
  3.  I. Функції 1 сторінка
  4.  I. Функції 2 сторінка
  5.  I. Функції 3 сторінка
  6.  I. Функції 4 сторінка
  7.  II. Метаморфози кореня, службовці для посилення опорної функції (додаткові за походженням)

приклад:

Вирішимо симплексним методом задачу:

F = 2x1 + 3х2 a max  при обмеженнях:

х1 + 3х2 <= 18

2х1 + х2 <= 16

х2 <= 5

3x1 <= 21

Е
 х1, х2> = 0

 
 

 Перейдемо до канонічної формі за допомогою додаткових невід'ємних змінних:

х1 + 3х2 + х3 = 18

2х1 + х2 + х4 = 16

х2 + х5 = 5

3x1 + х6 = 21

Для знаходження початкового БР разоб'ем на основні (базові) і неосновні (вільні). Т. к. Визначник при змінних х3 - х6 НЕ дорівнює 0, то на першому кроці - основні. Не обов'язково складати визначник на першому кроці. Наступне правило:

В якості основних змінних на першому кроці слід вибрати (якщо можливо) такі m змінних, кожна з яких входить тільки в одне з m рівнянь системи обмежень, при цьому немає таких рівнянь системи, в які не входить жодна з цих змінних.

Якщо обрані змінні мають ті ж знаки, що і відповідні їм вільні члени, то отримане БР буде ДБР. Якщо отримано не ДБР, то М-метод. Буде розглянуто далі.

1 крок. Осн - х3, х4, х5, х6.

 Неосн - х1, х2.

Х3 = 18 - х1 - 3х2

Х4 = 16 - 2х1 - х2 (1)

Х5 = 5 - х2

Х6 = 21- 3х1

Неосновні = 0aХ1 = (0; 0; 18; 16; 5; 21) відповідає вершині про (0; 0).

Рішення - допустиме, м. Б. оптимальним. Перевіримо. Висловимо цільову функцію через неосновні змінні F = 2x1 + 3х2. При вирішенні Х1 значення функції F (X1) = 0. Функцію можна збільшити за рахунок збільшення будь-який з неосновних змінних, що входять в рівняння для функції з позитивним коефіцієнтом. Це можна здійснити перейшовши до такого нового ДБР, в якому ця змінна буде основною, т. Е. Приймати не нульове, а позитивне значення (якщо нове рішення буде виродилися, то функція мети збереже своє значення). Одна з змінних, при цьому з основних - в неосновні. Геометрично - до сусідньої вершини. В даному прикладі і х1 і х2 м можна. Виберемо х2 - більший коефіцієнт.

Система (1) накладає обмеження на зростання змінної х2. Т. к. Необхідно зберігати допустимість рішень, т. Е. Все змінні невід'ємні, то повинні виконуватися нерівності (х1 при цьому = 0 як неосновна):

 Х3 = 18 - 3х2> = 0Х4 = 16 - х2> = 0х5 = 5 - х2> = 0Х6 = 21> = 0  звідки  Х2 <= 18 / 3х2 <= 18 / 1Х2 <= 5/1

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

Кордон - ?:

§ Останнє рівняння системи не обмежує зростання змінної х2, т. К. Ця змінна не входить в нього (входить з 0 коефіцієнтом).

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

§ Чи не накладає обмежень на зростання змінної, що переводиться в основні, і таке рівняння, де вільний член = 0, а переказується змінна має знак +.

При вільному члені = 0, а переказується змінна має знак - рівняння обмежує зростання змінної 0.

В даному прикладі найбільше можливе значення для х 2 = min {18/3; 16/1; 5/1; ?} = 5. При х2 = 5 змінна х5 звертається в 0 і переходить в неосновні.

Рівняння, де досягається максимальне можливе значення змінної, що переводиться в основні (т. Е. Де оцінка мінімальна) називається що дозволяє. В даному випадку - 3. виділяється рамкою в системі обмежень.

2 крок. Осн - х2, х3, х4, х6.

Неосн - х1, х5.

 Х2 = 5 - х5

Х3 = 18 - х1 - 3 (5 - х5)

Х4 = 16 - 2х1 - (5 - х5) (2)

Х6 = 21- 3х1

або

 Х2 = 5 - х5

Х3 = 3 - х1 + 3 х5

Х4 = 11 - 2х1 + х5

Х6 = 21- 3х1

Неосновні = 0aХ2 = (0; 5; 3; 11; 0; 21) відповідає вершині а (0; 5).

Рішення - допустиме, м. Б. оптимальним. Перевіримо. Висловимо цільову функцію через неосновні змінні F = 2x1 + 3х2 = 2х1 + 3 (5 - х5) = 15 + 2х1 - 3х5. При вирішенні Х2 значення функції F (X2) = 15. Зміна значення лінійної функції можна визначити заздалегідь як твір найбільшого можливого значення змінної, що переводиться в основні, на її коефіцієнт в цільової функції (зміна F = 5 * 3 = 15.

Значення F2 не є макс, т. К., Повторюючи міркування кроку 1, можна виявити можливість подальшого збільшення лин функції за рахунок змінної х1, що входить у вираз для F з позитивним коефіцієнтом.

Система (2) визначає найбільше можливе значення для х1 = min {?; 3/1; 11/2; 21/3} = 3. друге рівняння - дозволяє, змінна х3 звертається в 0 і переходить в неосновні, при цьому приріст цільової функції = 3 * 2 = 6.

3 крок. Осн - х1, х2, х4, х6.

Неосн - х3, х5.

Висловлюємо нові основні змінні через нові неосновні, починаючи з дозволяючого рівняння. Після перетворення отримуємо:

 Х1 = 3 - х3 + 3 х5

Х2 = 5 - х5

Х4 = 5 + 2х3 - 5х5 (3)

Х6 = 12 + 3х3 - 9х5

Неосновні = 0aХ3 = (3; 5; 0; 5; 0; 12) відповідає вершині в (3; 5).

Рішення - допустиме, м. Б. оптимальним. Перевіримо. Висловимо цільову функцію через неосновні змінні F = 2x1 + 3х2 = 2 (3 - х3 + 3х5) + 3 (5 - х5) = 21- 2х3 + 3х5. При вирішенні Х3 значення функції F (X3) = 21.

Значення F3 не є оптим, т. К. Можна виявити можливість подальшого збільшення лин функції за рахунок змінної х5, що входить у вираз для F з позитивним коефіцієнтом.

При визначенні найбільшого можливого значення для х5, яку переводимо в основні, звернути увагу, що перше рівняння системи (3) не дає обмеження на зростання х5, т. К. Вільний член і коефіцієнт при х5 мають однакові знаки. Система (3) визначає найбільше можливе значення для х5 = min {?; 5; 1; 12/9} = 1. Третє рівняння - дозволяє, змінна х4 звертається в 0 і переходить в неосновні, при цьому приріст цільової функції = 1 * 3 = 3.

4 крок. Осн - х1, х2, х5, х6.

Неосн - х3, х4.

 Висловлюємо нові основні змінні через нові неосновні, починаючи з дозволяючого рівняння. Після перетворення отримуємо:

Х1 = 6 + 1 / 5х3 - 3 / 5х4

Х2 = 4 - 2 / 5х3 + 1 / 5х4

Х5 = 1 + 2 / 5х3 - 1 / 5х4 (3)

Х6 = 3 - 3 / 5х3 + 9 / 5х4

Неосновні = 0aХ4 = (6; 4; 0; 0; 1; 3) відповідає вершині з (6; 4).

Рішення - допустиме, м. Б. оптимальним. Перевіримо. Висловимо цільову функцію через неосновні змінні F = 2x1 + 3х2 = 24 - 4 / 5х3 - 3 / 5х4. При вирішенні Х4 значення функції F (X4) = 24.

Значення F4 є оптим, т. К. Немає позитивних коефіцієнтів при неосновних змінних.

Згадуючи економічний сенс всіх змінних, можна зробити наступні висновки:

§ Прибуток підприємства прийме макс значення 24 руб. при реалізації 6 од. продукції першого виду (х1 = 6) і 4 од. продукції другого виду (х2 = 4).

§ Додаткові змінні х3, х4, х5 і х6 показують різницю між запасами ресурсів кожного виду і їх споживанням, т. Е. Залишки ресурсів. При оптим плані виробництва х3 = х4 = 0, т. Е. Залишки першого і другого ресурсів рівні 0, а залишки третього і четвертого ресурсів дорівнюють відповідно 1 і 3 одиницям.

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

При знаходженні хв лин функції Z можливі два шляхи:

1) відшукати макс лин функції F, вважаючи, що F = - Z і враховуючи, що Zmin = - Fmax;

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

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

зауваження. На кожному кроці симплексного методу будь-яка неосновна змінна перекладається в основні, при цьому кожне рівняння системи обмеження визначає кінцеве або нескінченне найбільше можливе значення цієї змінної - оцінне ставлення. Можуть зустрічатися різні випадки оцінки зростання неосновної змінної, які залежать від знаків і значень вільного члена і коефіцієнтів при перекладної змінної. Введемо позначення:

Xi - перекладається неосновна змінна;

Bj- вільний член;

Aij - коефіцієнт при Xi;

Сформулюємо всі можливі випадки оцінки зростання Xi в рівнянні Xj = Bj + ... + AijXi + ...:

1) Хi = ?Bj / Aij?, якщо Bj і Aij різного знака і Aij НЕ = 0, Bj НЕ = 0.

2) Хi = ?, якщо Bj і Aij одного знака і Aij НЕ = 0, Bj НЕ = 0.

3) Хi = 0, якщо Bj = 0 і Aij> 0.

4) Хi = ?, якщо Bj = 0 і Aij <0.

5) Хi = ?, якщо Aij = 0.




 лінійне програмування |  Поняття економіко-математичної моделі |  Завдання про розкрої матеріалів. |  Система m лінійних рівнянь з n змінними |  Геометричний сенс рішень нерівностей, рівнянь і їх систем |  Є опуклим багатокутником (або опуклою багатокутної областю). |  Властивості задач ЛП |  Геометричний метод розв'язання задач ЛП |  сімплексні таблиці |

© um.co.ua - учбові матеріали та реферати