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

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

Назва:
Загальна задача лінійного програмування і деякі з методів її розв’язування.
Тип:
Реферат
Мова:
Українська
Розмiр:
2,29 KB
Завантажень:
233
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2 
Реферат на тему:
Загальна задача лінійного програмування і деякі з методів її розв’язування.


План.
1. Економічна інтерпретація симплексного методу розв’язування задач лінійного програмування.
Використана література


Економічна інтерпретація симплексного методу розв’язування задач ЛП.
Знайти максимальне значення функції при умовах
Розв’язання. Систему рівнянь задачі запишемо у векторній формі:
, де
Так як серед векторів є три одиничних вектори, то для даної задачі можна безпосередньо знайти опорний план Складаємо таблицю (табл. 1.1) і перевіряємо, чи являється даний опорний план є оптимальним.
Табл. 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, вихідний опорний план не є оптимальним. Тому переходимо до нового опорного плану. Це можна зробити, так як в стовпцях векторів Р1 і Р5, 4-го рядка, який має від’ємні числа, є додатні елементи. Для переходу до нового опорного плану введемо в базис вектор Р5 і виключимо з базису вектор Р4. Складаємо таблицю ІІ ітерації.
Табл. 1.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
Як бачимо з таблиці 1.2, новий опорний план задачі є оптимальним, так як в четвертому рядку стовпця вектора Р1 стоїть від’ємне число –11/3. Оскільки в стовпці цього вектора немає додатних елементів, дана задача не має оптимального плану.
2. Знайти розв’язок задачі, який полягає у визначенні максимального значення функції при умовах
і дати геометричну інтерпретацію процесу розв’язання.
Розв’язання. Систему рівнянь задачі запишемо у векторній формі:
, де
Так як серед векторів , є три одиничних вектора то для даної задачі можна безпосередньо написати опорний план, а отже знайти її розв’язок можна симплексним методом (табл. 1.3)
Табл. 1.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
Із таблиці 1.3 видно, що є оптимальним планом вихідної задачі. При цьому плані значення лінійної форми рівняння .
Дамо геометричну інтерпретацію процесу знаходження розв’язку задачі. Для цього, насамперед, перейдемо від вихідної задачі, система границь яка має рівняння, до задачі, системи границь, яка включає лише нерівності. Це зробити неважко, так як вихідна задача записана у формі основної задачі, яка полягає в знаходженні максимального значення функції при умовах.
Цільова функція вихідної задачі перетворена за допомогою підстановки замість у відповідності з рівняннями системи обмежень.
Розв’язок останньої задачі можна знайти, використовуючи геометричну інтерпретацію задачі лінійного програмування (мал. 1.). Вихідний опорний план задачі відповідає на малюнку 1 точці О. Після ІІ ітерації буде оптимальний новий опорний план , якому відповідає точка А. На малюнку перехід від одного опорного плану до другого показано стрілкою, де вказаний напрям переходу. Після ІІІ ітерації, оптимальний опорний план , відповідає точці В, тобто здійснений перехід від точки А до точки В. Отриманий на даній ітерації опорний план є оптимальним.
Використана література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. – К.:
КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2 



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

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок