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

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

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

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


Реферат на тему:
Загальна задача лінійного програмування і деякі з методів її розв'язування.
План.
1. Економічна інтерпретація симплексного методу розв'язування задач лінійного програмування.
2. Використана література
Економічна інтерпретація симплексного методу розв'язування задач ЛП.
Знайти максимальне значення функції при умовах
Розв'язання. Систему рівнянь задачі запишемо у векторній формі:
, де
Так як серед векторів є три одиничних вектори, то для даної задачі можна безпосередньо знайти опорний план Складаємо таблицю (табл. 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. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка" (Інформаційно-видавничий центр "Інтелект+" Інститут післядипломної освіти)
"Інтелект - Захід", 2004. - 448 с.
3. Акулич М.Л.Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.36-47.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: "Рута", 1998.-168 с
Loading...

 
 

Цікаве