WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Загальна задача лінійного програмування та деякі з методів її розв’язування. - Реферат

Загальна задача лінійного програмування та деякі з методів її розв’язування. - Реферат


Реферат на тему:
Загальна задача лінійного програмування та деякі з методів її розв'язування.
Економічна інтерпретація симплексного методу розв'язування задач ЛП.
Знайти максимальне значення функції при умовах
Розв'язання. Систему рівнянь задачі запишемо у векторній формі:
, де
Так як серед векторів є три одиничних вектори, то для даної задачі можна безпосередньо знайти опорний план Складаємо таблицю (табл. 1) і перевіряємо, чи являється даний опорний план є оптимальним.
Таблиця 1
і Базис Сб Р0 2 -6 0 0 5 0
Р1 Р2 Р3 Р4 Р5 Р6
1 Р3 0 20 - 2 1 1 0 1 0
2 Р4 0 24 -1 -2 0 1 3 0
3 Р6 0 18 3 -1 0 0 -12 1
4 0 -2 6 0 0 -5 0
Як видно з таблиці 1, вихідний опорний план не є оптимальним. Тому переходимо до нового опорного плану. Це можна зробити, так як в стовпцях векторів Р1 і Р5, 4-го рядка, який має від'ємні числа, є додатні елементи. Для переходу до нового опорного плану введемо в базис вектор Р5 і виключимо з базису вектор Р4. Складаємо таблицю 2 ітерації.
Таблиця 2
і Базис Сб Р0 2 -6 0 0 5 0
Р1 Р2 Р3 Р4 Р5 Р6
1 Р3 0 12 - 5/3 5/3 1 -1/3 0 0
2 Р4 5 8 -1/3 -2/3 0 1/3 1 0
3 Р6 0 114 -1 -9 0 4 0 1
4 40 -11/3 8/3 0 5/3 0 0
Як бачимо з таблиці 2, новий опорний план задачі є оптимальним, так як в четвертому рядку стовпця вектора Р1 стоїть від'ємне число -11/3. Оскільки в стовпці цього вектора немає додатних елементів, дана задача не має оптимального плану.
2. Знайти розв'язок задачі, який полягає у визначенні максимального значення функції при умовах
і дати геометричну інтерпретацію процесу розв'язання.
Розв'язання. Систему рівнянь задачі запишемо у векторній формі:
, де
Так як серед векторів , є три одиничних вектора то для даної задачі можна безпосередньо написати опорний план, а отже знайти її розв'язок можна симплексним методом (табл. 3)
Таблиця 3
і Базис Сб Р0 2 1 -1 1 -1
Р1 Р2 Р3 Р4 Р5
1 Р3 -1 5 1 1 1 0 0
2 Р4 1 9 2 1 0 1 0
3 Р5 -1 7 1 2 0 0 1
4 -3 -2 -3 0 0 0
1 Р3 -1 3/2 1/2 0 1 0 -1/2
2 Р4 1 11/2 3/2 0 0 1 -1/2
3 Р2 1 7/2 1/2 1 0 0 1/2
4 15/2 -1/2 0 0 0 3/2
1 Р1 2 3 1 0 2 0 -1
2 Р4 1 1 0 0 -3 1 1
3 Р2 1 2 0 1 -1 0 1
4 9 0 0 1 0 1
Із таблиці 3 видно, що є оптимальним планом вихідної задачі. При цьому плані значення лінійної форми рівняння .
Дамо геометричну інтерпретацію процесу знаходження розв'язку задачі. Для цього, насамперед, перейдемо від вихідної задачі, система границь яка має рівняння, до задачі, системи границь, яка включає лише нерівності. Це зробити неважко, так як вихідна задача записана у формі основної задачі, яка полягає в знаходженні максимального значення функції при умовах.
Цільова функція вихідної задачі перетворена за допомогою підстановки замість у відповідності з рівняннями системи обмежень.
Розв'язок останньої задачі можна знайти, використовуючи геометричну інтерпретацію задачі лінійного програмування (мал. 1.). Вихідний опорний план задачі відповідає на малюнку 1 точці О. Після ІІ ітерації буде оптимальний новий опорний план , якому відповідає точка А. На малюнку перехід від одного опорного плану до другого показано стрілкою, де вказаний напрям переходу. Після ІІІ ітерації, оптимальний опорний план , відповідає точці В, тобто здійснений перехід від точки А до точки В. Отриманий на даній ітерації опорний план є оптимальним.
Основна література.
1. Акулич М.Л.Математическое програмирование в примерах и зада-чах: Учебное пособие для студентов экономических специальних вузов.-Вища школа,1975.-319с., ст.36-47.
Додаткова література.
1. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/ Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С. - Чернівці: "Рута", 1998.- 168 с.
Loading...

 
 

Цікаве