Лабораторная работа: Будування математичної моделі економічної задачі і розвязання її за допомогою графічного метода
Отже, ця недовизначена система має безліч розв'язків . Тому можна й далі таким же чином шукати різні розв'язки цієї системи, як завгодно "вручну" визначаючи будь-яку її змінну.
Завдання 4
1). Розв'язати симплекс-методом задачу лінійного програмування, яка представлена в завданні 2.
2). Побудувати двоїсту задачу до заданої задачі лінійного програмування.
3). Знайти розв'язок двоїстої задачі та дати економічну інтерпретацію отриманого розв'язку.
Розв'язок
Отже, наша вихідна система лінійного програмування (ЛП) із завдання 2 з n = 2 буде така:
Z = 3x1 + 2x2 → max
2х1 + х2 ≤ 4,
х1 + 2х2 ≤ 5, (1)
х1 ≥ 0, х2 ≥ 0.
1. Для застосування симплекс-методу потрібно привести вихідну систему (1) до канонічного (стандартного) вигляду шляхом введення двох m = 2 нових змінних х3 та х4 :
2х1 + х2 + х3 = 4,
х1 + 2х2 + х4 = 5, (2)
х1,2,3,4 ≥ 0.
Також треба знайти початкове базисне рішення , тобто будь-яке рішення, що не порушує обмежень задачі (2). (Виходячи із тривіальності заданої системи, можна було б відразу вказати таке рішення, яке одночасно було б й оптимальним:
х1 = 1 > 0, х2 = 2 > 0, х3 = х4 = 0.)
Формально початковий базисний розв’язок можна взяти, прийнявши до уваги, що x3 та х4 зустрічаються в кожному рівнянні системи (2) по одному разу:
х1,2 = 0, x3 = 4, х4 = 5.
Далi скористаємося алгоритмом симплекс-метода i заповнимо наступні таблиці за відомими формулами математичного програмування. Позначимо через Аk вектор, складений з коефіцієнтів аik при змінній хk в i-ому обмеженні, через СБ — вектор, складений з координат сбi , що відповідають базисним змінним (на цьому 1-му кроці методу це — x3 , х4 ). Тепер вирахуємо симплексні різниці Δk за формулою
Δk = Ak CБ - Zk = ∑αik , k = 1÷ n + m, і = 1 ÷ m (3)
де підсумовування ведеться по індексу і,
αik = аik сбi – сk . (4)
Отже, Δk дорівнює сумі добутків базисних сбi на аik мінус сk .
Таблиця 1. Перший крок симплекс-методу
|
i |
Б |
Сб |
сk |
3 |
К-во Просмотров: 417
Бесплатно скачать Лабораторная работа: Будування математичної моделі економічної задачі і розвязання її за допомогою графічного метода
|