2.1 Постановка задачи

Используя метод множителей Лагранжа, найти точки условного экстремума следующей задачи нелинейного программирования, определить характер экстремума:

, (2.1)

2.2 Решение и выводы

Метод множителей Лагранжа позволяет отыскивать максимум ли минимума функции при ограничениях-равенствах.

Общий вид функции Лагранжа:

(2.2)

где – целевая функция вектора ;

– ограничения в неявном виде.

В качестве целевой функции, подлежащей оптимизации, в этой задаче выступает функция:

(2.3)

Перепишем ограничения в неявном виде:

(2.4)

Составим вспомогательную функцию Лагранжа:

(2.5)

Необходимым условием экстремума функции Лагранжа является равенство нулю ее частных производных по переменным х_i и по неопределенному множителю λ.

Составим систему уравнений:

(2.6)

Выражая из первого уравнения х₁ , из второго х₂ и подставляя эти значения в третье уравнение, получаем уравнение вида:

(2.7)

Решим его:

(2.8)

Тогда , а .

Найдем значение исходной функции при данных значениях:

(2.9)

2.2.1 Знаходження першого опорного плану задачі

Перевіримо правильність рішення задачі за допомогою MS Excel (див.рис.2.5-2.6).

Рисунок 2.5 – Вигляд сторінки Excel при визначенні максимального значення

Рисунок 2.6 – Визначення параметрів пошуку рішень

Висновки по завданню …

ЗАДАЧА 3

3.1 Постановка задачі

Побудувати двоїсту задачу до заданої та знайти її розв’язок. Використовуючи теореми двоїстості знайти розв’язок прямої задачі. Задана пряма задача має вигляд:

max Z = – 5x₁ + 2x₂; (3.1)

(3.2)

3.2 Розв’язання та висновки

Двоїста задача утворюється за такими правилами:

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

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

3. якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі – на визначення найменшого значення (min), і навпаки;

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

Двоїстою до задачі

max Z=c₀ + (c, x), (3.3)

Ax=b, x³0, (3.4)

(записаній у векторно-матричній формі) є

, (3.5)

, y³0, (3.6)

де  – матриця, транспонована до А; (с, x), (b, y) – скалярні добутки відповідних векторів.

Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція Z максимізується і в системі обмежень є нерівності, то їх слід звести до виду « ». Тому перше обмеження задачі помножимо на (–1). Після цього знак нерівності зміниться на протилежний. Отримаємо:

max Z = – 5x₁ + 2x₂; (3.7)

(3.8)

За наведеними вище правилами складемо двоїсту задачу:

min F = – y₁ + 5y₂; (3.9)

(3.10)

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

а) max Z = – 5x₁ + 2x₂ + 0x₃ + 0x₄; (3.11)

(3.12)

б) Векторна форма запису системи обмежень має вигляд:

, (3.13)

де , , , , .

У системі векторів для утворення початкового одиничного базису відсутній один вектор. Тому введемо штучну змінну в перше обмеження.

в) Розширена задача лінійного програмування буде такою:

max Z = – 5x₁ + 2x₂ + 0x₃ + 0x₄ – Мx₅; (3.14)

(3.15)

У цій задачі х₄ та х₅ – базисні змінні, а х₁, х₂, х₃ – вільні. Нехай х₁=х₂=х₃=0, тоді х₄=5; х₅=1.

Перший опорний план задачі:

X₀ = (0; 0; 0; 5; 1), Z₀ = – M. (3.16)

г) Подальше розв’язування прямої задачі подано у вигляді симплексної таблиці:

Рисунок 3.1 – Розв’язання прямої задачі у вигляді симплексної таблиці

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

Х*=(0; 5/3; 2/3; 0), Z_max = 10/3. (3.17)

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

min F = max Z = 10/3. (3.18)

Компоненти вектора Y^* (оптимальний план двоїстої задачі) визначимо за формулою:

, (3.19)

де та міститься в стовпчику «с_баз» останньої симплекс-таблиці;

. (3.20)

Матриця D^{– 1} також міститься в останній симплекс-таблиці у стовпчиках змінних «x₅» та «x₄», які утворювали початковий базис.

Отже,

, (3.21)

min F = – 1×0 + 5×2/3 = 10/3. (3.22)

Застосувавши для розв’язування прямої задачі симплекс-метод, ми знайшли її оптимальний план, а потім визначили оптимальний розв’язок двоїстої задачі за допомогою співвідношень першої теореми двоїстості.

Перевіримо правильність рішення прямої задачі за допомогою MS Excel (див. рис.3.2-3.4).

Рисунок 3.2 – Вигляд сторінки MS Excel при визначенні максимального значення

Рисунок 3.3

Перевіримо правильність рішення двоїстої задачі за допомогою MS Excel (див.рис.3.4-3.6).

Рисунок 3.4 – Вигляд сторінки MS Excel при вирішенні двоїстої задачі

Рисунок 3.5

Висновки по завданню …

ЗАДАЧА 4