Рішення задачі лінійного
програмування симплекс-методом
Ладовіра Тетяна Михайлівна
Новоросійський коледж будівництва та економіки
Відмінною особливістю ЗЛП, що утворюють підмножину задач математичного програмування, є те, що мета завдання записується у вигляді лінійної функції f (X) і обмеження її також лінійні.
Основним завданням лінійного програмування являетсянахожденіе
таких значень змінних Х = (х1. х2. х3. ..., хn), які призводять цільову
функцію f (X) до екстремального значенням.
Загальний вигляд запису моделі ЗЛП:
xi ≥ 0, i = 1 ÷ n - шукані величини,
aij. bj. ci - задані постійні величини,
bj - запаси сировини, енергії і т.д. j = 1 ÷ m.
Сукупність чисел Х = (х1. Х2. Х3. Хn), що задовольняють обмеженням
завдання, називається допустимим рішенням або планом або областю допустимих
рішень (ОДР).
Допустиме рішення, максимізуючи або мінімізує цільову функцію, називається оптимальним рішенням або оптимальним планом.
Вирішити ЗЛП в окремому випадку при наявності двох змінних можна графічним методом.
Якщо в ЗЛП більше двох змінних, то найпоширенішим методом рішення є симплекс-метод.
Симплексом називається вираз виду
c1 x1 + c2 x2 + ... + cn xn
або сума парних добутків векторів
Методика рішення задач з f (x) → min відрізняється від методики вирішення завдань c f (x) → max. Для зручності вирішення завдань обох типів за єдиним алгоритмом їх моделі необхідно привести до т.зв. канонічної формі (КФ).
Вважається, що ЗЛП записана в канонічної формі, якщо:
a) її цільова функція максимизируется;
b) обмеження завдання мають вигляд рівності з неотрицательной правою частиною (bj ≥ 0);
c) всі змінні в моделі завдання невід'ємні (≥ 0).
Таким чином, канонічна форма моделі ЗЛП має вигляд:
Розглянемо два типи математичних моделей ЗЛП.
I.
Наведемо до КФ ЗЛП, задану моделлю, в якій всі обмеження виду ≤:
У всіх нерівностях системи обмежень ліва частина менше або дорівнює правій (≤). Для того щоб зрівняти їх (як того вимагає канонічна форма), необхідно до лівої частини кожного обмеження додати. відповідно, невід'ємні цілі змінні xn + 1, xn + 2, ..., xn + m. Щоб не змінилося значення цільової функції, ці змінні вводяться в неї з нульовими коефіцієнтами.
Т.ч. після приведення до канонічної формі наша
задача матиме вигляд:
Якщо обмеження в вихідної математичної моделі задачі задано знаком строго рівності (=), то в нього не вводять додаткову змінну, а тільки штучну (див.нижче).
Нехай економічне завдання описується наступною моделлю
Наведемо цю математичну модель до КФ:
II.
Розглянемо другий окремий випадок: f (x) → min і хоча б одне з обмежень виду ≥ (або навіть всі). Модель цього завдання має вигляд:
Визначення мінімального значення функції f (x) можна звести до знаходження максимального значення функції -f (x).
Т.ч. в подібних випадках коефіцієнти при невідомих в f (x) → min треба помножити на (-1).
Щоб привести до суворого рівності обмеження виду ≥, треба з лівої частини кожного обмеження такого виду відняти. відповідно, невід'ємні цілі змінні xn + 1, xn + 2, .... xn + m.
Тоді після приведення до КФ завдання (**) матиме вигляд:
Всі змінні в математичної моделі діляться на два типи:
- базисні (залежні), які можуть бути виражені через всі інші
змінні. Змінна є базисної, якщо вона входить
тільки в одне з рівнянь системи з коефіцієнтом рівним 1 (так в системі (*) базисними є змінні х3. х4. х5).
- всі інші змінні є небазисними (незалежними).
Приватне рішення, тобто знаходження базисних змінних при прирівнювання небазисних змінних нулю (хi = 0), називається базисним. Базисне рішення називається виродженим, якщо хоча б одна з базисних змінних = 0, таке завдання називається виродження. В іншому випадку - завдання називається невироджених.
Вище ми розглянули два окремих випадки I і II.
У разі I базисне рішення є допустимим рішенням:
і не є допустимим, тому що суперечить умові незаперечності змінних (xi ≥ 0).
У таких випадках для виділення базисних змінних і знаходження допустимого рішення використовують метод штучного базису, що полягає в наступному:
1) в кожне обмеження виду ≥ або = вводять штучну неотрицательную змінну в1. у2, ... уm;
2) в цільову функцію штучні змінні входять з коефіцієнтом (-М), де М - дуже велике позитивне число (звідси і назва - М-метод).
Після введення штучних змінних КФ завдання (**) матиме вигляд:
Набір штучних змінних у1. у2, ..., уm в М-методі утворює штучний базис. Штучні змінні вводяться тільки для отримання вихідного базисного плану при вирішенні задач ЛП симплекс-методом. Рішення ЗЛП зручно проводити в т.зв. симплекс-таблицях наступного виду:
Значення цільової функції f (x) обчислюють як суму парних добутків елементів стовпа С і елементів стовпця В. Відносні оцінки - як суму парних добутків елементів стовпа С і елементів відповідного i-го стовпця.
Алгоритм рішення ЗЛП симплекс-методом
1. Привести математичну
модель до канонічної формі. Заповнити симплекс-таблицю і обчислити значення
цільової функції і відносних оцінок.
2. - якщо все відносні
оцінки невід'ємні і серед базисних змінних немає штучних, то план
оптимальний, тобто задача вирішена. Рішення знаходимо в стовпці В:
- якщо все відносні оцінки невід'ємні і серед них є рівні нулю, а серед базисних змінних немає штучних, то задача вирішена і має безліч рішень, одне з яких вийшло в базис (знаходиться в стовпці В);
- якщо все відносні оцінки невід'ємні, але серед базисних змінних є штучні, то завдання рішень не має;
- якщо серед відносних
оцінок є негативні, то рішення задачі неоптимально, необхідний перехід до
наступного базисного плану (до пункту 3).
3. З усіх негативних відносних оцінок вибирається найбільша за модулем. Відповідний їй стовпець називається головним. Для визначення главнойстрокі треба поелементно розділити стовпець В на головний стовпець
(На нулі і негативні числа головного стовпчика не ділять). найменша частка
відповідає головній рядку. На перетині головною рядки і головного стовпчика
знаходиться головний елемент симплекс-таблиці. Це число може бути тільки
позитивним.
Далі необхідно провести перерахунок таблиці.
4. У новій таблиці змінні головною рядки і головного стовпчика (разом зі своїми коефіцієнтами) міняються місцями. Решта змінні і їх коефіцієнти переписуються без змін.
Замість головного елемента записується зворотне йому число: 1 / головний елемент.
Елементи головного стовпчика старої таблиці ділять на (- головний елемент).
Елементи головної рядки старої таблиці ділять на (головний елемент).
Всі інші елементи перераховують за правилом прямокутника:
з твору елементів головної діагоналі, що проходить через головний елемент, віднімають твір елементів побічної діагоналі і результат ділять на головний елемент; число, записують у відповідну клітку нової симплекс-таблиці. Якщо в головній рядку або головному стовпці є нулі, то
елементи відповідних цим нулях шпальти і рядки переписуються без
зміни в нову таблицю.
5. У новій таблиці обчислюються значення цільової функції і відносних
оцінок. Перехід до пункту 2.
Приклад 2.
Вирішимо наступне завдання симплекс-методом.
Майстер робить мельхіорові ложки двох видів: без карбування (Л1) за ціною 2 євро і з карбуванням (Л2) за ціною 3 євро. За день майстер робить не менше однієї ложки. Денний запас сировини не більше 12 дм 3. при цьому на ложку виду Л1 йде 3 дм 3. а на ложку виду Л2 - 2 дм 3 мельхіору.
На який максимальний дохід в день може розраховувати майстер при дотриманні зазначених норм?
позначимо:
x1 - кількість ложок виду Л1,
x2 - кількість ложок виду Л2.
За умовою завдання складемо її математичну модель:
дохід від продажу ложок виду Л1 складе 2 * x1 (євро);
дохід від продажу ложок виду Л2 складе 3 * x1 (євро). Сума цих чисел дорівнює доходу майстра - цільова функція.
На виробництво ложок виду Л1 витрачається 3 * x1 дм 3 м мельхіору, а на виробництво ложок виду Л2 витрачається 2 * x1 дм 3 м. Причому майстер не може використовувати в день більше 12 дм 3 м - це перше обмеження. З умови, що майстер в день робить не менше однієї ложки, запишемо друге обмеження і отримаємо модель задачі:
Для вирішення завдання симплекс-методом наведемо математичну модель до канонічної формі:
На підставі канонічної форми побудуємо початковий базисний план завдання:
Завдання не вирішена, тому що в базисі є штучні змінні, а серед відносних оцінок - негативні. Серед негативних відносних оценокmso-fareast-font-family: Calibri; mso-ansi-language: RU; mso-fareast-language: EN-US;
вибираємо найбільшу по модулю (-М-3) - їй відповідає головний стовпець; знаходимо головний рядок (друга, т.к.1 / 1 Негативна відносна оцінка одна (-3), їй відповідає головний стовпець; головна рядок - перша, відповідно, головний елемент дорівнює двом (комірка виділена блакитним кольором). Виконавши перерахунок таблиці, перейдемо до нового базисного плану.
Всі відносні оцінки невід'ємні, в базисі немає штучних змінних, отже, завдання виконане.
Рішення:
X1 = 0 (тому що ця змінна не вийшла в базис), в базис вийшла X2 = 6, максимальний дохід при такому плані випуску виробів дорівнює
f (X) = 2 * 0 + 3 * 6 = 18 (євро).
2 Малик Г.С. Основи економіки та математичні методи в плануванні / - М. Вища школа, 1988.-
279 с.