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

Размещено на http://www.allbest.ru/

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

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

Кафедра алгебри і математичного аналізу

РЕФЕРАТ

з лінійної алгебри

СИМПЛЕКС-МЕТОД

ОТАМАСЬ ОЛЬГА ВОЛОДИМИРІВНА

ЧЕРКАСИ, 2011 РІК

Зміст

Вступ

1. Короткий огляд алгоритмів вирішення завдань даного типу

1.1 Математичне програмування

1.2 Табличний симплекс-метод

1.3 Метод штучного базису

1.4 Модифікований симплекс-метод

2. Змістовна постановка задачі

3. Розробка і опис алгоритму рішення задачі

3.1 Побудова математичної моделі завдання

3.2 Рішення задачі уручну

Вступ

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

Дана робота спрямована на те, щоб дослідити і усвідомити значення і сутність симплекс-методу, як одного із провідних методів вирішення задач лінійного програмування. Максимально розкрити дане питання і проаналізувати його структуру. Знайти плюси і мінуси у дану методі, показати його переваги у вирішенні завдань лінійного програмування.

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

1. Короткий огляд алгоритмів вирішення завдань даного типу

1.1 Математичне програмування

Математичне програмування займається вивченням екстремальних завдань і пошуком методів їх рішення.

Завдання математичного програмування формулюються таким чином: знайти екстремум деякої функції багатьох змінних (x1, x2, xn).

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

Знайти max:

За умови:

Ці обмеження називаються умовами додатності.

Якщо всі обмеження задані у вигляді строгої рівності, то дана форма називається канонічною.

У матричній формі завдання лінійного програмування записують таким чином. Знайти:

За умови:

Розв'язок х0 називається оптимальним, якщо для нього виконується умова:

Для вирішення завдань даного типу застосовуються методи:

1) графічний;

2) табличний (прямий, простий) симплекс-метод;

3) метод штучного базису;

4) модифікований симплекс-метод;

5) подвійний симплекс-метод.

1.2 Табличний симплекс-метод

Для його застосування необхідно, щоб знаки в обмеженнях були вигляду “менше або рівно”, а компоненти вектора b - додатні.

Алгоритм розв'язання зводиться до наступного:

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

Якщо в початковій системі обмежень були присутні знаки “рівно” або “більше - рівно”, то у вказані обмеження додаються штучні змінні, які так само вводяться і в цільову функцію із знаками, визначуваними типом оптимуму. Формується симплекс-таблиця. Розраховуються симплекс-різниці. Ухвалюється рішення про закінчення або продовження рахунку. При необхідності виконуються ітерації. На кожній ітерації визначається вектор, що вводиться в базис, і вектор, що виводиться з базису. Таблиця перераховується по методу Жордана-Гауса або яким-небудь іншим способом.

1.3 Метод штучного базису

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

Якщо в оптимальному рішенні - задача немає штучних змінних, це рішення є оптимальне рішення початкової задачі. Якщо ж в оптимальному рішенні - задачі хоч одна з штучних змінних буде відмінна від нуля, то система обмежень початкової задачі несумісна і початкова задача нерозв'язна.

1.4 Модифікований симплекс-метод

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

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

2. Змістовна постановка задачі

Для виробництва двох видів виробів А і В використовується три типи технологічного устаткування. На виробництво одиниці виробу А йде часу, годин: устаткуванням 1-го типу - а1, устаткуванням 2-го типу - а2, устаткуванням 3-го типу - а3. На виробництво одиниці виробу В йде часу, годин: устаткуванням 1-го типу - b1, устаткуванням 2-го типу - b2, устаткуванням 3-го типу - b3. На виготовлення всіх виробів адміністрація підприємства може надати устаткування 1-го типу не більш, ніж на t1, устаткування 2-го типу не більш, ніж на t2, устаткування 3-го типу не більш, ніж на t3 годин. Прибуток від реалізації одиниці готового виробу А складає N гривень, а вироби В гривень.

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

3. Розробка і опис алгоритму рішення задачі

3.1 Побудова математичної моделі завдання

Побудова математичної моделі здійснюється в три етапи:

1. Визначення змінних, для яких складатиметься математична модель.

Оскільки потрібно визначити план виробництва виробів А і В, то змінними моделі будуть:

- x1 - обсяг виробництва виробу А, в одиницях;

- x2 - обсяг виробництва виробу В, в одиницях.

2. Формування цільової функції. Оскільки прибуток від реалізації одиниці готових виробів А і В відома, то загальний дохід від їх реалізації складає 2x1 (гривень). Позначивши загальний дохід через F, можна дати наступне математичне формулювання цільової функції: визначити допустимі значення змінних x1 і x2, що максимізували цільову функцію F;

3. Формування системи обмежень. При визначенні плану виробництва продукції повинні бути враховані обмеження на якийсь час, яке адміністрація підприємства зможе виділити на виготовлення всіх виробів. Це приводить до наступних трьох обмежень:

Таким чином, математична модель завдання представлена у вигляді: визначити план x1, x2, що забезпечує максимальне значення функції:

За наявності обмежень:

3.2 Рішення задачі уручну

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

1. Приведення завдання до форми:

2. Канонізуємо систему обмежень:

3. Заповнюється початкова симплекс-таблиця і розраховуються симплекс-різниці по формулах:

- поточне значення цільової функції.

- розрахунок симплекс-різниць.

Де:

j = 1..6.

Оскільки при рішенні задачі на max не всі симплекс-різниці позитивні, то оптимальне рішення можна поліпшити.

4. Визначаєм направляючий стовпець j*. Для завдання на max він визначається мінімальною негативною симплекс-різницею. В даному випадку це вектор А2.

5. Вектор i*, який потрібно вивести з базису, визначається по відношенню:

В даному випадку спочатку це А3.

5. Заповнюється нова симплекс-таблиця по виключенню Жордана-Гауса:

а) направляючий рядок i* ділимо на направляючий елемент:

б) перетворення всієї частини матриці, що залишилася:

лінійний алгоритм математичний

В результаті перетворень отримуємо нову симплекс-таблицю:

Повторюючи пункти 3-5, отримаємо наступні таблиці:

Оскільки всі симплекс-різниці додатні, то оптимальне рішення знайдене:

X = (7/2, 3/4, 11/4, 0, 0) (одиниць).

max F = 9 1/4 (гривень).

Размещено на Allbest.ru