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

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

ЗМІСТ

Вступ

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

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

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

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

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

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

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

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

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

Список використаних джерел і літератури

ВСТУП

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

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

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



1. КОРОТКИЙ ОГЛЯД АЛГОРИТМІВ ВИРІШЕННЯ ЗАВДАНЬ ДАНОГО ТИПУ

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

симплекс метод лінійне програмування

Математичне програмування займається вивченням екстремальних завдань і пошуком методів їх рішення. Завдання математичного програмування формулюються таким чином : знайти екстремум деякої функції багатьох змінних f ( x1, x2 ..., xn ) при обмеженнях gi ( x1, x2 ..., xn ) bi, де gi - функція, що описує обмеження, - один з наступних знаків,,, а bi - дійсне число, i = 1 ..., m. ; f називається функцією мети ( цільова функція ).

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

Завдання лінійного програмування можна сформулювати так . Знайти

max

за умови : a11x1 + a12x2 + . . . + a1nxnb1 ;

a21x1 + a22x2 + . . . + a2nxnb2 ;

_{. . . . . . . . . . . . . . . . . . . . . . . . . . . .}

am1x1 + am2x2 + . . . + amnxnbm ;

x1 0, x2 0 _{. . .}, xn 0 _.

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

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

Знайти

maxc^тx

за умови

A x b ;

x 0

де А - матриця обмежень розміром ( mn), b^(m1) - вектор-стовпець вільних членів, x^{(n 1)} - вектор змінних, с^т = [c1, c2 ..., cn ] - вектор-рядок коефіцієнтів цільової функції.

Розв'язокх0 називається оптимальним, якщо для нього виконується умова с^тх0с^т х, для всіх х R(x).

Оскільки min f(x) еквівалентний max [ - f(x)], то завдання лінійного програмування завжди можна звести до еквівалентного завдання максимізації.

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

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 годин.

Прибуток від реалізації одиниці готового виробу А складає гривень, а вироби В - гривень.

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

а1 = 1 b1 = 5 t1 = 10 = 2

а2 = 3 b2 = 2 t2 = 12 = 3

а3 = 2 b3 = 4 t3 = 10



3. РОЗРОБКА І ОПИС АЛГОРИТМУ РІШЕННЯ ЗАДАЧІ

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

	На вироб-во виробів А, годин	На вироб-во виробів В, годин	Підприємство надасть, годин
Устат. 1-го типу	1	5	10
Устат. 2-го типу	3	2	12
Устат. 3-го типу	2	4	10
Прибуток від реалізації, за од. виробу	2	3

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

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

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

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

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

2. Формування цільової функції.

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

3. Формування системи обмежень.

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

x1 + 5x2 10; 3x1 + 2x2 12 ; 2x1 + 4x2 10 .



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

x1 0 ;x2 0 .

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

max F = max( 2x1 + 3x2 )

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

x1 + 5x2 10;

3x1 + 2x2 12 ;

2x1 + 4x2 10 .

x1 0 ;x2 0 .

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

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

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

x1 + 5x2 10;

3x1 + 2x2 12 ;

2x1 + 4x2 10 .

x1 0 ;x2 0 .

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



x1 + 5x2 + x3 =10;

3x1 + 2x2 +x4 = 12 ;

2x1 + 4x2 + x5 = 10 .

x1 0 ;x2 0 .

A1A2A3A4A5A0

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

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

_i = - розрахунок симплекс-різниць, де j = 1..6 .

		C	2	3	0	0	0
Би	Cб	A0	A1	A2	A3	A4	A5
A3	0	10	1	5	1	0	0
A4	0	12	3	2	0	1	0
A5	0	10	2	4	0	0	1
		0	-2	-3	0	0	0

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

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

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



min при аi_j> 0

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

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

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

а _{i j} = а _{i j} / а _{i j} , де j = 1..6

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

а _ij = aij - а _{i j}aij , де i i*, j j*

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

		C	2	3	0	0	0
Би	Cб	A0	A1	A2	A3	A4	A5
A2	3	2	1/5	1	1/5	0	0
A4	0	8	13/5	0	-2/5	1	0
A5	0	2	6/5	0	-4/5	0	1
		6	-7/5	0	3/5	0	0

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

		C	2	3	0	0	0
Би	Cб	A0	A1	A2	A3	A4	A5
A2	3	5/3	0	1	1/3	0	-1/6
A4	0	11/3	0	0	4/3	1	-13/6
A1	2	5/3	1	0	-2/3	0	5/6
		8 1/3	0	0	-1/3	0	7/6



		C	2	3	0	0	0
Би	Cб	A0	A1	A2	A3	A4	A5
A2	3	3/4	0	1	0	-1/4	3/8
A3	0	11/4	0	0	1	3/4	-13/8
A1	2	7/2	1	0	0	1/2	-1/4
		9 1/4	0	0	0	1/4	5/8

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

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

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



СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ І ЛІТЕРАТУРИ

1. ЕСПД ГОСТ 19.105-78, 19.104-78.

2. ЕСПД ГОСТ 19.502-78.

3. Венцель Е.С. Дослідження операцій.-М.:Советское радио. 1972 р.

4. Дектярев Ю.І. Дослідження операцій.-М.:Вища школа. 1986 р.

5. Зайченко Ю.П. Дослідження операцій.-К.:Вища школа. 1979 р.

6. Зайченко Ю.П., Шумілловас. А. Дослідження операцій ( збірка завдань ).-К.:Вища школа. 1990 р.

7. Акулич І.Л. Математичне програмування в прикладах і завданнях: Навч. посібник для студ. Вузів. - М.: Вищ. Шк., 1986. 8. Банді Б. Основи лінійного програмування / пров. з англ. Під ред. В.А. Волинського. - М.: Радіо і зв'язок, 1989. 9. Кузнєцов А.В., Сакович В.А., Холод Н.І. Вища математика: Математичне програмування. - Мінськ: Вища школа, 1994.

10. Стренг Г. Лінійна алгебра і її використання. -М.: Мир. 1980.

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