Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

3.7.2. Параметричні зміни вектора коефіцієнтів цільової функції

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

(3.80)

(3.81)

(3.82)

допустимо, що

. (3.83)

Усі ж інші коефіцієнти і вільні члени залишаються сталими величинами.

Запишемо параметричну задачу такого виду в загальній формі:

(3.84)

(3.85)

. (3.86)

За деякого фіксованого значення задача (3.84)—(3.86) перетворюється в звичайну задачу лінійного програмування. Зміни коефіцієнтів цільової функції в процесі реалізації симплексного методу впливатимуть на значення оцінкового ряду ().

Для оптимального плану задачі лінійного програмування в постановці (3.36)—(3.38), як відомо з § 2.7.4, оцінки векторів розраховують так:

.

Якщо цільова функція має вигляд (3.84), то оцінки векторів розраховуватимуться за формулою:

Позначимо перетворені методом повних виключень Жордана—Гаусса в процесі перерахунку початкової симплексної таблиці через , аналогічно — як . Остання симплексна таблиця набуде такого вигляду:

Таблиця 3.6

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

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

1. Слід зафіксувати деяке значення і розв’язати задачу (3.84)—(3.86) як звичайну задачу лінійного програмування симплексним методом.

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

.

3. Встановлюємо границі значень параметра t, для яких вектор залишатиметься оптимальним планом. Для цього з останньої симплексної таблиці складаємо систему нерівностей

. (3.87)

а) Якщо існують такі значення j, для яких , тоді розв’язками відповідних нерівностей будуть:

. (3.88)

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

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

б) Якщо існують такі значення і, для яких , то розв’язками відповідних нерівностей будуть:

. (3.89)

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

.

4. Система (3.74) визначає вектор, який необхідно вивести з базису. Припустимо, що за деякого , де , мінімальне значення в (3.89), яке визначає верхню границю інтервалу , досягається для . Отже, порушується k-та нерівність із (3.87), і з базису необхідно виводити вектор, що відповідає змінній . Тому при необхідно провести заміну базису, для чого виконують один крок двоїстого симплекс-методу, розглянутого в § 3.6, і визначають нове значення .

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

6. Процедуру повторюємо доти, поки не отримаємо значення верхньої границі чергового інтервалу, що дорівнює або перевищує верхню границю заданого інтервалу можливих значень t, тобто

. (3.90)

Співвідношення (3.90) і є ознакою того, що задачу розв’язано.

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

Розв’язати параметричну задачу

Нехай . Розв’яжемо задачу модифікованим симплексним методом, використовуючи таблицю з двома додатковими рядками.

Остання симплексна таблиця містить перший оптимальний план задачі

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

і при .

Оскільки при елемент m + 2 рядка та п’ятої колонки буде нульовим, беремо п’яту колонку за розв’язувальну і, відкинувши m + 2 рядок, здійснюємо одну ітерацію. Отримаємо таку таблицю:

В m + 3 рядку цієї таблиці немає від’ємних елементів, а тому згідно з формулою (3.89) знайдений план буде оптимальним для всіх значень t, що лежать на інтервалі . Оптимальне значення цільової функції є такою лінійною функцією параметра t:

.

При .

Отже, задача розв’язана повністю.