Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



«Рішення задач симплекс та двоїстим симплекс методом» варіант: «Вибір схеми розміщення бетонозмішувальних вузлів (18)»

Скачати 492.39 Kb.

«Рішення задач симплекс та двоїстим симплекс методом» варіант: «Вибір схеми розміщення бетонозмішувальних вузлів (18)»




Скачати 492.39 Kb.
Сторінка1/3
Дата конвертації27.10.2019
Розмір492.39 Kb.
  1   2   3

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ БУДІВНИЦТВА І АРХІТЕКТУРИ КАФЕДРА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ ПРОЕКТУВАННЯ ТА ПРИКЛАДНОЇ МАТЕМАТИКИ

КУРСОВИЙ ПРОЕКТ


(РОБОТА)
з дисципліни: «Дослідження операцій»
на тему: «Рішення задач симплекс та двоїстим симплекс методом»
варіант: «Вибір схеми розміщення бетонозмішувальних вузлів (18)»

Студента 3-го курсу групи ІТЕП-31 Спеціальності 122. «Комп’ютерні науки» Можарівського В. В.


Керівник: д.т.н., професор Терентьєв О.О.
Національна шкала _______________________ Кількість балів: _________ Оцінка: ECTS ___ Члени комісії____________________________ ________________________________________
(підпис) (прізвище та ініціали)

Київ – 2018



Зміст
Завдання


  1. Постановка задачі…………………………………………………………..3




  1. Розробка математичних моделей………………………………………….3




  1. Аналіз та вибір методів рішення задач…………………………………...5 3.1 Симплекс метод……………………………………………………4

3.4 Вибір методу……………………………………………………….7


  1. Розв’язання задач симплекс методом…………………………………….7 4.1 Алгоритм симплекс методу………………………………………..7 4.1.1 Схема алгоритму розв’язку симплекс методом…………8

4.1.2 Схема алгоритму роботи програми………………………9


4.2 Ітерації симплекс методу…………………………………………9
4.2.1 Ітерації задачі ………………………….…………..…….9
4.2.2 Ітерації задачі …….……………………………….…….10
5.3 Висновок…………………………………………………………..14


  1. Дослідження програми на чутливість моделі…………………………...15 6.1 Модель, заповнення даних……………………………………….16

6.2 Модель, результат програми……………………………………16


  1. Список використаної літератури………………………………………..17

2


  1. Постановка задачі

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



Можливість відмови від розширення будь-якого підприємства відповідає проекту з нульовими витратами. Необхідно вибрати проект по кожному з підприємств таким чином, щоб прибуток від інвестування в розмірі 8 млн грн був максимальним. Розглянути 24 можливість збільшення прибутку для третього підприємства на 50% для другого проекту.




  1. Розробка математичних моделей:

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


При обчисленнях значення Fc = 2 тимчасово не враховуємо.
Визначимо максимальне значення цільової функції
F (X) = 2x1 + 4x2 + x3 + 2.5x4 + 5x6 + 6x8 + 2 при наступних умовах-обмежень.
2x1 + 2.8x2 + x3 + 2x4≤0
4x3 + 7x4 + 2x5 + 2.5x6 + x7 + 1.5x8≤0
3

x1 + 2x2 + 4x3 + 3x4 + 5x6 + 4.5x5 + 6x7≤0


Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної формі).
У 1-му нерівності сенсу (≤) вводимо базисну змінну x9. У 2-му нерівності сенсу


  • вводимо базисну змінну x10. У 3-му нерівності сенсу (≤) вводимо базисну змінну x11.

2x1 + 2.8x2 + 1x3 + 2x4 + 0x5 + 0x6 + 0x7 + 0x8 + 1x9 + 0x10 + 0x11 = 0


0x1 + 0x2 + 4x3 + 7x4 + 2x5 + 1x7 + 2.5x6 + 1.5x8 + 0x9 + 1x10 + 0x11 = 0
1x1 + 2x2+ 4x3 + 3x4 + 4.5x5 + 5x6 + 6x7 + 0x8 + 0x9 + 0x10 +1x11 = 0
Вирішимо систему рівнянь щодо базисних змінних: x5, x6, x7
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,0,0,4.8,11,12)


  1. Аналіз та вибір методів рішення задач

Розглянемо методи, за допомогою яких можна розв’язати дану задачу, а також переваги та недоліки методів вирішення задач лінійного програмування.


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

4

Цей метод є універсальним, застосовним до будь-якого завдання лінійного програмування в канонічної формі. Система обмежень тут - система лінійних рівнянь, в якій кількість невідомих більша за кількість рівнянь. Якщо ранг системи дорівнює r, то ми можемо вибрати r невідомих, які висловимо через інші невідомі. Для визначеності припустимо, що обрані перші, що йдуть підряд, невідомі X1, X2, ..., Xr. Тоді наша система рівнянь може бути записана як.


До такого виду можна навести будь-яку спільну систему, наприклад, методом Гаусса. Правда, не завжди можна висловлювати через інші перші r невідомих (ми це зробили для визначеності записи). Однак такі r невідомих обов'язково знайдуться. Ці невідомі (змінні) називаються базисними, інші вільними.
Надаючи певні значення вільним змінним і обчислюючи значення базисних (виражених через вільні), ми будемо отримувати різні рішення нашої системи обмежень. Таким чином, можна отримати будь-яке її рішення. Нас будуть цікавити особливі рішення, одержувані в разі, коли вільні змінні дорівнюють нулю. Такі рішення називаються базисними, їх стільки ж, скільки різних базисних видів у даної системи обмежень. Базисне рішення називається допустимим базисним рішенням або опорним рішенням, якщо в ньому значення змінних невід'ємні. Якщо в якості базисних взяті змінні X1, X2, ..., Xr, то рішення {b1, b2, ..., br, 0, ..., 0} буде опорним за умови, що b1, b2, ... , br ≥ 0.
3.2 Сиплекс метод
Двоїстий симплекс-метод, як і симплекс-метод, використовується при знаходженні рішення задачі лінійного програмування, записаної в формі основного завдання, для якої серед векторів, складених з коефіцієнтів при невідомих у системі рівнянь, є m одиничних. Разом з тим двоїстий симплекс-метод можна застосовувати при вирішенні задачі лінійного програмування, вільні члени системи рівнянь якої можуть бути будь-якими числами (при вирішенні задачі симплексним методом ці числа передбачалися невід'ємними).
5

Таке завдання і розглянемо тепер, попередньо припустивши, що одиничними є вектори т. Е. Розглянемо задачу, яка полягає в визначенні максимального значення функції.


Кожній задачі лінійного програмування певним чином можна поставити у відповідність деяку іншу задачу, яка називається двоїстою задачею лінійного програмування. Двоїстою задачею лінійного програмування по відношенню до вихідної задачі називається задача, яка полягає у визначенні мінімального значення цільової функції.
Задача будується на основі таких правил:


  1. цільова функція вихідної задачі задається на максимум, а цільова функція двоїстої задачі задається на мінімум;




  1. матриця яка складається з коефіцієнтів при невідомих вихідної задачі переходить у AT;




  1. число невідомих двоїстої задачі дорівнює числу рівнянь системи обмежень , число рівнянь в системі обмежень двоїстої задачі дорівнює числу невідомих вихідної задачі;




  1. коефіцієнти при невідомих цільової функції двоїстої задачі дорівнюють стовпчику вільних членів вихідної задачі, вільні члени системи обмежень двоїстої задачі дорівнюють коефіцієнтам цільової функції прямої задачі;




  1. якщо деяка змінна xj може приймати тільки додатні значення, то j-та нерівність в системі обмежень двоїстої задачі задається у вигляді нерівності, якщо деяка змінна xj може приймати як додатні так і від'ємні значення, тоді рівності в системі обмежень двоїстої задачі задаються у вигляді рівностей.


3.4 Вибір методу
Для розв’язання даних задач, найдоцільніше буде використовувати симплекс метод.

6


  1. Розв’язання задач симплекс методом


4.1 Алгоритм симплекс методу
4.1.1 Схема алгоритму розв’язку симплекс методом

7

  1   2   3


Скачати 492.39 Kb.

  • Постановка задачі
  • Розробка математичних моделей
  • Аналіз та вибір методів рішення задач
  • 3 Симплекс метод
  • 3.2 Сиплекс метод
  • 3.4 Вибір методу Для розв’язання даних задач, найдоцільніше буде використовувати симплекс метод. 6 Розв’язання задач симплекс методом
  • 4.1 Алгоритм симплекс методу 4.1.1 Схема алгоритму розв’язку симплекс методом