Розв’язання задач лінійного програмування - Курсовая работа

В даний час лінійне програмування є одним з найбільш популярних апаратів математичної теорії оптимального управління рішень, у тому числі і у фінансовій математиці. Для вирішення завдань лінійного програмування розроблено складне програмне забезпечення, що дає можливість ефективно і надійно вирішувати практичні завдання великих обємів. У класичній математиці методи пошуку оптимальних рішень розглядають у розділах класичної математики, звязаних з вивченням екстремумів функцій, у математичному програмуванні. Існує багато розділів в математичному програмуванні, серед них лінійне і нелінійне програмування, опукле і квадратичне, і багато інших. Розглянемо лінійне програмування та визначимо основні принципи і алгоритми даного розділу математичного програмування.Лінійне програмування розвязує велику кількість задач з різними типами обмежень.Методи лінійного програмування - чисельні методи вирішення оптимізаційних задач, що зводяться до формальних моделей лінійного програмування[1]. Як відомо, будь-яке завдання лінійного програмування може бути приведене до канонічної моделі мінімізації лінійної цільової функції з лінійними обмеженнями типу рівності. Оскільки число змінних в завданні лінійного програмування більше числа обмежень (), то можна отримати рішення, прирівнявши нулю () змінних, які називаються вільними. Решта m змінних, які називаються базисними, можна легко визначити з системи обмежень звичайними методами лінійної алгебри.Якщо модель містить тільки дві змінні, задачу можна розвязати графічно. Незважаючи на це, розгляд графічного методу дасть змогу зробити висновки, що послужать основою для розробки загального методу розвязання задач лінійного програмування[2]. Умови невідємності змінних обмежують область їх допустимих значень. Інші межі простору розвязків потрібно зобразити прямими лініями, побудованими по рівняннях, що отримані заміною знака «?» чи «?» знаком “=" в обмеженнях. Області, в яких відповідні обмеження виконуються як нерівності, указуються стрілками, спрямованими вбік допустимих значень змінних.Симплекс-метод застосовується до рішення будь-якої задачі лінійного програмування[3]. Симплекс метод в порівнянні з графічним методом забезпечує більш раціональне рішення задачі. Розпочинаючи з будь-якої вершини багатокутника, твореного обмеженнями, переходять до розрахунку тільки тієї вершини, в якій значення лінійної форми буде більшим, чим в попередніх. Таким чином, виконується впорядкований перебір вершин, при яких відбувається постійне збільшення лінійної форми. Тому симплекс-метод також називають методом послідовного покращення оптимального плану.Однак двоїстий симплекс-метод можна застосовувати при рішенні задач лінійного програмування, вільні члени системи рівнянь якої можуть бути будь-якими числами (при рішенні задачі симплексним методом ці числа передбачалися ненегативними). Нехай за умовою задачі потрібно визначити максимальне значення функції: .(1.4.1) Для того, щоб вирішити задачу двоїстим симплекс-методом потрібно виконати дві умови. Рішення системи лінійних рівнянь(1.4.2), приймаючи до уваги базис(одиничні вектори), називається псевдопланом задачі, якщо всі умови даної системи задоволені. Після цього, вибирають рядок, що дозволяє, за допомогою визначення найбільшого по абсолютній величині негативного числа стовпця вектора і результуючого стовпчика, знаходження найменшого по абсолютній величині відношення елементів () і рядка до відповідного негативним елементам результуючого рядка.В найпростішому варіанті транспортна задача формулюється наступним чином: є n постачальників із запасами однорідного штучного товару та m споживачів із потребами цього товару . Не порушуючи загальності, можна вважати транспортну задачу закритою, тобто, що сума всіх запасів дорівнює сумі всіх потреб, в противному разі задача є відкритою і простими відомими методами (введенням фіктивного постачальника чи фіктивного споживача) зводиться до закритої. Нехай матриця є матрицею цін перевезень, тобто кожен її елемент є ціною за перевезення одиниці продукції від i-го постачальника j-му споживачу, а матриця такої ж розмірності є планом перевезень, тобто кожне є цілим невідємним числом, що дорівнює кількості товару, що перевозиться від i-го постачальника j-му споживачу. Метою розвязку транспортної задачі є пошук такого плану перевезень Х, при якому загальна вартість перевезень була б найменшою з можливих за умови, що весь товар від постачальників перевозиться до споживачів.Так як симплекс-метод є універсальним, будь-яку задачу лінійного програмування можна з легкістю вирішити як за допомогою програмного забезпечення так і вручну, то для вирішення заданої задачі він підійде найкраще.Нехай у задачі представлено n видів виробничої діяльності, інтенсивності використання котрих (шукані величини) складають . У випадку максимізації величина являє собою прибуток від j-го виду виробничої діяльності на одиницю відповідної продукції, а у випадку мінімізації характеризує питомі витрати. Зауважимо, що «корисність» деякого виду ви

Зміст

Вступ

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 Інструкція користувачеві

Висновки

Література

Додаток А.

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