Розв’язання задач лінійного програмування

В найпростішому варіанті транспортна задача формулюється наступним чином: є n постачальників із запасами однорідного штучного товару та m споживачів

Розв’язання задач лінійного програмування

Курсовой проект

Компьютеры, программирование

Другие курсовые по предмету

Компьютеры, программирование

Сдать работу со 100% гаранией

Міністерство освіти та науки України

Вінницький національний технічний університет

Інститут автоматики та компютерних систем управління

Факультет автоматики та компютерних систем управління

 

 

 

 

 

 

 

 

 

 

Розвязання задач лінійного програмування(А)

Пояснювальна записка

з дисципліни «Математичне програмування та дослідження операцій»

до курсової роботи за спеціальністю

«Системи управління та автоматики»

08-01.МПДО.342.00.000-ПЗ

 

 

 

 

 

 

 

 

 

Вінниця, ВНТУ 2007

 

 

Анотація

 

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

Було розроблено математичну модель і програмне забезпечення. Дана задача вирішується симплекс методом, тому досліджується основний принцип метода, особливості і переваги в порівнянні з іншими методами.

Зміст

 

Вступ

1 Опис існуючих методів розвязку задач лінійного програмування

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

1.2 Графічний метод

1.3 Симплекс-метод

1.4 Двоїстий симплекс метод

1.5 Транспортна задача

1.6 Вибір методу розвязку задачі

2 Опис метода розвязку задачі

3 Розробка моделі розвязку задачі

4 Розробка програмного забезпечення

4.1 Призначення програми

4.2 Вибір середовища програмування

4.3 Опис вхідних та вихідних даних

4.4 Розробка структури програми

4.5 Розробка схеми алгоритму

4.6 Розробка тестів

4.7 Аналіз результатів тестування

4.8 Інструкція користувачеві

Висновки

Література

Додаток А.

Технічне завдання

Вступ

 

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

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

Існує багато розділів в математичному програмуванні, серед них лінійне і нелінійне програмування, опукле і квадратичне, і багато інших. Але всі вони зводяться до отримання оптимального рішення у великій кількості задач різних промислових і виробничих гілках суспільства. Розглянемо лінійне програмування та визначимо основні принципи і алгоритми даного розділу математичного програмування.

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

  1. раціональне використання сировини і матеріалів;
  2. завдання оптимального розкрою;

-оптимізації виробничої програми підприємств;

-оптимального розміщення і концентрації виробництва;

-складання оптимального плану перевезень, роботи транспорту;

-управління виробничими запасами і ін.

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

Першим дослідженням по лінійному програмуванню є робота Л. В. Кантфовіча “Математичні методи організації і планування виробництва”, яке було опубліковане в 1939 р. У ньому розміщена постановка завдань лінійного програмування, розроблений метод результуючих множників вирішення завдань лінійного програмування і дано його теоретичне обґрунтування.

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

1 Опис існуючих методів розвязку задач лінійного програмування

 

Лінійне програмування розвязує велику кількість задач з різними типами обмежень. Тому їх можна розвязати різними методами. Розглянемо їх принцип.

 

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

 

Методи лінійного програмування - чисельні методи вирішення оптимізаційних задач, що зводяться до формальних моделей лінійного програмування[1].

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

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

В загальному постановка задачі має вигляд:

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

(1.1.1)

В залежності від виду функції і області G розрізняють розділи математичного програмування: квадратичне програмування, випукле і ін.

Лінійне програмування характеризується тим, що функція і лінійною функцією змінних і область G визначається системою лінійних рівнянь чи нерівностей.

 

  1. Графічний метод

 

Якщо модель містить тільки дві змінні, задачу можна розвязати графічно.У випадку трьох змінних графічний розвязок стає менш наочним, а при більшому числі змінних - взагалі неможливим.Незважаючи на це, розгляд графічного методу дасть змогу зробити висновки, що послужать основою для розробки загального методу розвязання задач лінійного програмування[2].

Перший крок при використанні графічного методу полягає в поданні області допустимих розвязків, у якій водночас задовольняються всі обмеження моделі.Нехай шукана область (простір) розвязків задачі показана. Умови невідємності змінних обмежують область їх допустимих значень. Інші межі простору розвязків потрібно зобразити прямими лініями, побудованими по рівняннях, що отримані заміною знака «≤» чи «≥» знаком “=" в обмеженнях. Області, в яких відповідні обмеження виконуються якнерівності, указуються стрілками, спрямованими вбік допустимих значень змінних.Отримуємо простір розвязків задачі. У кожній точці, що належить внутрішній області або межам, всі обмеження виконуються, тому розвязки, що відповідають цим точкам, є допустимими. Серед безкінечного числа таких точок можна знайти точку оптимального розвязку, якщо з'ясувати, в якому напрямку зростає цільова функція. На графік наносять лінію рівня цільової функції , де - довільне значення . Будують вектор , що є нормаллю до ліній рівня цільової функції й визначаєнапрямок оптимізації .Лінію рівня зрушують паралельно самій собі вздовж вектора доти, поки вона не вийде за межі області допустимих розвязків.Остання точка цієї області й буде точкою оптимуму.

Значення та в розвязуючій точці визначаються шляхом розвязання системи рівнянь.

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

Графічний спосіб розв'язування ґрунтується на геометричній інтерпретації задачі лінійного програмування, тому він досить простий для розуміння. Недоліком є те, що графічним способом можна розвязати задачу, в якій в обмеженнях є лише дві змінні, потрібно намагатися малювати лінії з найбільшою точністю, в протилежному випадку можна отримати велику похибку, а в результаті неправильне рішення.

 

1.3 Симплекс-метод

 

Симплекс-метод застосовується до рішення будь-якої задачі лінійного програмування[3].

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

Похожие работы

1 2 3 4 > >>