Навігація
Головна
Симплексний метод розв'язання задачіМетоди інформаційного забезпечення розв'язання некоректних задачАлгоритми розв'язання задачМетоди рішення багатокритеріальних задачМетод динамічного програмування та оцінки для задач оптимального...
Симплекс-методу з природним базисомСимплекс-метод зі штучним базисом (М-метод)Симплекс-метод зі штучним базисом (М-метод)ЗЕМЛЯ - ПРИРОДНИЙ РЕСУРС І БАЗИС ГОСПОДАРЮВАННЯАлгоритм симплекс-методу
 
Головна arrow Економіка arrow Економіко-математичні методи і прикладні моделі
< Попередня   ЗМІСТ   Наступна >

Симплексний метод розв'язання задачі

Серед універсальних методів вирішення завдань лінійного програмування найбільш поширеним є симплексний метод (або симплекс-метод), розроблений американським вченим Дж. Данцигом. Суть цього методу полягає в тому, що спочатку отримують допустимий варіант, що задовольняє всім обмеженням, але необов'язково оптимальний (так зване початкове опорне рішення); оптимальність досягається послідовним поліпшенням початкового варіанту за певне число етапів (ітерацій). Знаходження початкового опорного рішення і перехід до наступного опорного рішенням проводяться на основі застосування розглянутого вище методу Жордана - Гаусса для системи лінійних рівнянь канонічної форми, в якій повинна бути попередньо записана вихідна ЗЛП; напрямок переходу від одного опорного рішення до іншого вибирається при цьому на основі критерію оптимальності (цільової функції) вихідної задачі. Симплекс-метод заснований на наступних властивостях ЗЛП:

1) не існує локального екстремуму, відмінного від глобального. Іншими словами, якщо екстремум є, то він єдиний;

2) безліч всіх допустимих рішень (планів) задачі лінійного програмування опукло;

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

4) кожної кутовій точці багатогранника рішень відповідає опорний план ЗЛП.

Розглянемо два різновиди симплексного методу: симплекс-метод з природним базисом і симплекс-метод зі штучним базисом (або М-метод).

Симплекс-методу з природним базисом

Для застосування цього методу ЗЛП повинна бути сформульована в канонічній формі (2.12) - (2.14), причому матриця системи рівнянь повинна містити одиничну підматрицю розміром т × т. У цьому випадку очевидний початковий опорний план (невід'ємне базисне рішення).

Для визначеності припустимо, що перші т векторів матриці системи рівнянь складають одиничну матрицю. Тоді первинний опорний план очевидний - ().

Перевірка на оптимальність опорного плану проходить за допомогою критерію (ознаки) оптимальності, перехід до іншого опорного плану - за допомогою перетворень Жордана - Гаусса і з використанням ознаки оптимальності.

Отриманий опорний план знову перевіряється на оптимальність і т.д. Процес закінчується за кінцеве число кроків, причому на останньому кроці або виявляється нерозв'язність завдання (кінцевого оптимуму немає), або виходить оптимальний опорний плану і відповідне йому оптимальне значення цільової функції.

data-override-format="true" data-page-url = "http://stud.com.ua">

Ознака оптимальності полягає в наступних двох теоремах.

Теорема 2.3. Якщо для деякого вектора, що не входить в базис, виконується умова

(2.22)

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

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

б) якщо є хоча б одна позитивна компонента у вектора, що підлягає введенню в базис, то можна отримати новий опорний план.

Теорема 2.4. Якщо для всіх векторів виконується умова

то отриманий опорний план є оптимальним.

На підставі ознаки оптимальності в базис вводиться вектор, довший мінімальну негативну величину симплекс-різниці:

Щоб виконувалася умова невід'ємності значень опорного плану, виводиться з базису вектор А г який дає мінімальне позитивне оцінне ставлення

(2.23)

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

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

data-override-format="true" data-page-url = "http://stud.com.ua">

Для використання наведеної вище процедури симплекс-методу до мінімізації лінійної функції слід шукати максимум функції, потім отриманий максимум взяти з протилежним знаком. Це і буде шуканий мінімум початкової ЗЛП.

Слід зауважити, що зациклення в симплекс-методі може мати місце також і у випадку так званого виродження. При т обмеженнях ЗЛП значення т базисних змінних, як правило, позитивні, а значення інших п - т вільних змінних завжди дорівнюють нулю. Проте можливо рівність нулю однієї або декількох базисних змінних; такий план називається виродженим.

Обчислюється за формулою (2.22) величини називаються симплексними різницями, або оцінками, відповідних змінних.

Так як в основі симплекс-методу лежить метод Жордана - Гаусса для системи лінійних рівнянь канонічної форми ЗЛП, то при розрахунках рекомендується візуально перевіряти виконання випливають з цього ознак: стовпці базисних векторів в симплексних таблицях мають вигляд відповідних стовпців одиничної матриці, а оцінки базисних змінних завжди дорівнюють нулю.

Рядок А r називається спрямовуючої, стовпець і елемент - напрямними (останній називають також дозволяючим елементом і в сіплекс-таблицях виділяють рамкою).

Елементи вводиться рядка, відповідної направляючої рядку, в повий симплекс-таблице обчислюються за формулами

(2.24)

а елементи будь-який інший i- го рядка перераховуються за формулами

(2.25)

Відповідно до (2.24) і (2.25) значення базисних змінних нового опорного плану (показники графи "план") розраховуються але формулами

Таким чином, перерахунок симплексних таблиць за формулами (2.24) і (2.25) проводиться за допомогою двох обчислювальних процедур.

Процедура 1. Елементи знову вводиться рядка виходять шляхом ділення елементів рядка, що виводиться попередньої таблиці на дозволяючий (виділений рамкою) елемент.

Процедура 2. Елементи інших рядків розраховуються на базі перетворень Жордана - Гаусса, при цьому доцільно використовувати так зване правило прямокутного трикутника. Суть цього правила полягає в тому, що для розрахунку деякого елемента нової таблиці (крім елементів знову вводиться рядка) потрібно виділити три числа:

1) відповідний елемент (тобто стоїть на тому ж місці) попередньої таблиці;

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

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

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

Розглянемо алгоритм симплекс-методу на конкретному завданні.

Приклад 2.7. Для виробництва продукції типу П1 і П2 підприємство використовує два види сировини: С1 і С2 Дані про умови виробництва продукції наведено в табл. 2.1.

Таблиця 2.1

Дані про умови виробництва

Продукція / Сировина

Норми витрати сировини, кг / од.

Обсяги запасів сировини, кг

П1

П2

З 1

1

3

300

С2

1

1

150

Прибуток, у.о. / од. прод.

2

3

Скласти план виробництва за критерієм "максимум прибутку".

Рішення. Введемо необхідні позначення. Позначимо обсяг виробництва продукції через, продукції через Таким чином, формально (математично) план виробництва (виробнича програма) - це вектор '.

З урахуванням введених позначень математична модель задачі за критерієм "максимум прибутку" має вигляд

при обмеженнях

Наведемо цю ЗЛП до канонічного виду, ввівши додаткові змінні і:

або

КЗЛП має необхідне число одиничних стовпців, тобто має очевидною початковим опорним планом (0, 0, 300, 150). Рішення здійснюється симплекс-методом з природним базисом з оформленням розрахунків у симплекс-таблицях (табл. 2.2).

У вихідній симплекс-таблице з номером 0 рядок оцінок визначається за наведеною вище формулою (2.22):

Вихідний опорний план (0, 0, 300, 150) не є оптимальним, оскільки серед оцінок є негативні. Перехід до нового опорного плану здійснимо, ввівши в базис вектор, що має мінімальну негативну оцінку. Визначаємо вектор, що виходить з базису:

тобто вектор слід вивести з базису. Дозволяє елементом є (виділено рамкою). Перехід до наступної

симплекс-таблице здійснюємо за допомогою перетворень Жордана - Гаусса, при цьому рекомендується користуватися двома описаними вище обчислювальними процедурами симплексного методу, включаючи правило прямокутного трикутника.

Таблиця 2.2

Рішення ЗЛП в симплекс-таблицях

Номер

симплекс-

таблиці

Базис

План

2

3

0

0

Q

У

0

300

1

3

1

0

100

0

0

150

1

1

0

1

150

-

0

-2

-3

0

0

-

3

100

1/3

1

1/3

0

300

I

0

50

2/3

0

-1/3

1

75

-

300

-1

0

1

0

-

3

75

0

1

1/2

-1/2

II

2

75

1

0

-1/2

3/2

-

375

0

0

1/2

3/2

-

Другий опорний план (0, 100, 0, 50) не оптимальні; перехід до наступного опорного плану здійснимо, вводячи в базис вектор і виводячи вектор

У симплекс-таблице II отриманий оптимальний опорний план, оскільки всі симплекс-різниці (оцінки). Оптимальні значення змінних рівні: (основні змінні), (додаткові змінні).

Максимальне значення цільової функції дорівнює 375.

Таким чином, у розглянутій завданню про оптимальне використання обмежених ресурсів, оптимальна виробнича програма складається у випуску 75 од. продукції першого виду і 75 од. продукції другого виду. З цією програмою пов'язана максимальна прибуток від реалізації готової продукції - 375 у.о.

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >

Cхожі теми

Симплексний метод розв'язання задачі
Методи інформаційного забезпечення розв'язання некоректних задач
Алгоритми розв'язання задач
Методи рішення багатокритеріальних задач
Метод динамічного програмування та оцінки для задач оптимального керування
Симплекс-методу з природним базисом
Симплекс-метод зі штучним базисом (М-метод)
Симплекс-метод зі штучним базисом (М-метод)
ЗЕМЛЯ - ПРИРОДНИЙ РЕСУРС І БАЗИС ГОСПОДАРЮВАННЯ
Алгоритм симплекс-методу
 
Дисципліни
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук