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

max F = –5x1 + 2x2;

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

max F = –5x1 + 2x2;

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

;

Або схематично (використовуючи компоненти векторів та матриць) зв’язок між парою цих задач можна зобразити так:

До заданої задачі лінійного програмування записати двоїсту.

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

Двоїста задача:

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

3. Основні теореми двоїстості та їх економічний зміст

Зв’язок між оптимальними розв’язками прямої та двоїстої задач встановлюють леми та теореми двоїстості. Розглянемо задачі (3.1) – (3.3) та (3.4) – (3.6) з економічною інтерпретацією.

Якщо та – допустимі розв’язки відповідно прямої та двоїстої задач, то виконується нерівність

або . (3.7)

Доведення. Помножимо кожне рівняння системи (3.2) на відповідну змінну двоїстої задачі:

Підсумувавши праві і ліві частини нерівностей, отримаємо:

. (3.8)

Аналогічно перетворимо систему обмежень (3.5) двоїстої задачі: