Міністерство освіти України
Севастопольський Державний Технічний
Університет
-
Департамент ІС
ВИКОРИСТАННЯ табличного симплекс - методу для РІШЕННЯ ЗАДАЧ
Лінійне програмування
ДЛЯ
ОПТИМІЗАЦІЇ ЕКОНОМІЧНИХ завдань
Пояснювальна записка до курсової роботи з дисципліни "Методи дослідження операцій "
Гнучкий магнітний диск
59 листів
Виконав: ст. гр. І-22 д
Крильцовим Т.В.
Прийняв:
Старобінская Л.П.
Севастополь
1997
- 3 -
ЗМІСТ
ВСТУП. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . 5
1. КОРОТКИЙ ОГЛЯД АЛГОРИТМІВ РІШЕННЯ ЗАДАЧ
ЦІЄЇ ТИПУ. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 6
1.1 Математичне програмування. . . . . . . . . . . . . . . .
. . . 6
1.2 Табличний симплекс - метод. . . . . . . . . . . . . . . . . . .
. . . . . . . 7
1.3 Метод штучного базису. . . . . . . . . . . . . . . . . .
. . . . . . . 8
1.4 Модифікований симплекс - метод. . . . . . . . . . . . . . .
. . 8
2. Змістовні ПОСТАНОВКА ЗАВДАННЯ. . . . . . . . . . . . 10
3. РОЗРОБКА І ОПИС алгоритм вирішення
ЗАВДАННЯ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . 11
3.1 Побудова математичної моделі задачі. . . . . . . . . . . .
. . 11
3.2 Рішення завдання вручну. . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 12
4. АНАЛІЗ МОДЕЛІ на чутливість. . . . . . . . . . . . 16
4.1 Побудова двоїстої задачі та її чисельне рішення. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . 16
4.2 Визначення статусу ресурсів. . . . . . . . . . . . . . . . . .
. . . . . . . 16
4.3 Визначення значимості ресурсів. . . . . . . . . . . . . . . .
. . . . . . 17
4.4 Визначення допустимого інтервалу зміни запасу ресурсів. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . 17
4.5 Дослідження залежності оптимального рішення від змін запасів ресурсів. . . . . . . . . . . . . . . . . .
. . . . . . . . . 19
- 4 -
5. ГРАФІЧНЕ ПОДАННЯ ОТРИМАНИХ
РЕЗУЛЬТАТІВ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . 20
6. ВИСНОВКИ ТА РЕКОМЕНДАЦІЇ ЩОДО ПРАКТИЧНОГО
використанню. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 22
ДОДАТОК. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . 23
ЛІТЕРАТУРА. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . 11
- 5 -
ВСТУП
Мета даного курсового проекту - скласти план виробництванеобхідних виробів, що забезпечує максимальний прибуток від їх реалізації,звести цю задачу до задачі лінійного програмування, вирішити її симплекс - методом і скласти програму для вирішення завдання цимметодом на ЕОМ.
- 6 -
1. КОРОТКИЙ ОГЛЯД АЛГОРИТМІВ РІШЕННЯ ЗАДАЧ
ЦІЄЇ ТИПУ
1.1 Математичне програмування
Математичне програмування займається вивчення екстремальних завданьі пошуком методів їх вирішення. Задачі математичного програмуванняформулюються наступним чином: знайти екстремум деякої функції багатьохзмінних f (x1, x2, ..., xn) при обмеженнях gi (x1,x2, ... , Xn) (bi, де gi - функція, що описує обмеження, (--один з наступних знаків (, (, (, а bi - дійсне число, i = 1,
... , M. f називається функцією цілі (цільовафункція).
Лінійне програмування - це розділ математичногопрограмування, в якому розглядаються методи вирішення екстремальнихзавдань з лінійним функціоналом і лінійними обмеженнями, яким повиннізадовольняти шукані змінні.
Задачу лінійного програмування можна сформулювати так. Знайти max
за умови: a11 x1 + a12 x2 +. . . + A1n xn (b1; a21 x1 + a22 x2 +.
. . + A2n xn (b2;
.......
..................... Am1 x1 + am2 x2 + ... + amn xn (bm; x1 (0, x2 (0,..., xn (0.
Ці обмеження називаються умовами точність. Якщо всеобмеження задані у вигляді строгих рівностей, то дана форма називаєтьсяканонічної.
- 7 -
У матричній формі задачі лінійного програмування записуютьнаступним чином. Знайти max cT x за умови
A x (b; x (0, де А - матриця обмежень розміром (m (n), b (m (1) - вектор-стовпецьвільних членів, x (n (1) - вектор змінних, ст = [c1, c2, ..., cn]
- Вектор-рядок коефіцієнтів цільової функції.
Рішення х0 називається оптимальним, якщо для нього виконується умова ст х0 (ст х, для всіх х (R (x).
Оскільки min f (x) еквівалентний max [- f (x)], то завдання лінійногопрограмування завжди можна звести до еквівалентної задачі максимізації.
Для вирішення завдань даного типу застосовуються методи:
1) графічний;
2) табличний (прямий, простий) симплекс - метод;
3) метод штучного базису;
4) модифікований симплекс - метод;
5) двоїстий симплекс - метод. < p> 1.2 Табличний симплекс - метод
Для його застосування необхідно, щоб знаки в обмеженнях були виду
"менше або дорівнює", а компоненти вектора b - позитивні.
Алгоритм рішення зводиться до наступного:
1. Приведення системи обмежень до канонічного виду шляхом введення додаткових змінних для приведення нерівностей до рівності.
2. Якщо у вихідній системі обмежень були присутні знаки "одно"
- 8 -
або "більше або дорівнює", то в зазначені обмеження додаються штучні змінні, які так само вводяться і в цільову функцію зі знаками, що визначаються типом оптимуму.
3. Формується симплекс-таблиця.
4. Розраховуються симплекс-різниці.
5. Приймається рішення про закінчення або продовження рахунку.
6. При необхідності виконуються ітерації.
7. На кожній ітерації визначається вектор, що вводиться в базис, і вектор, що виводиться з базису. Таблиця перераховується за методом Жордана-Гаусса або яким-небудь іншим способом.
1.3 Метод штучного базису
Даний метод рішення застосовується за наявності в обмеженні знаків
"одно", "більше або дорівнює "," менше або дорівнює "і ємодифікацією табличного методу. Рішення системи здійснюється шляхом введенняштучних змінних зі знаком, що залежать від типу оптимуму, тобто длявиключення з базису цих змінних останні вводяться в цільову функцію звеликими негативними коефіцієнтами (, а в задачі мінімізації - зпозитивними (. Таким чином з початкової виходить нова (- завдання.
Якщо в оптимальному рішенні (- завдання немає штучних змінних, церішення є оптимальне рішення вихідної задачі. Якщо ж в оптимальномурішенні (- завдання хоч одна з штучних змінних буде відмінна віднуля, то система обмежень вихідної задачі несумісні і початкова завданнянерозв'язна.
1.4 Модифікований симплекс - метод
В основу даного різновиду симплекс-методу покладені такі особ -
- 9 -
ності лінійної алгебри, які дозволяють в ході рішення задачіпрацювати з частиною матриці обмежень. Іноді метод називають методомоберненої матриці.
У процесі роботи алгоритму відбувається спонтанне звернення матриціобмежень по частинах, відповідними поточними базисних векторах. Вказаназдатність робить вельми привабливою машинну реалізацію обчисленьвнаслідок економії пам'яті під проміжні змінні і значногоскорочення часу рахунку. Хороший для ситуацій, коли число змінних nзначно перевищує число обмежень m.
У цілому, метод відображає традиційні риси загального підходу до вирішеннязадач лінійного програмування, що включає в себе канонізацію умовзадачі, розрахунок симплекс-різниць, перевірку умов оптимальності, прийняттярішень про корекцію базису і виключення Жордана-Гаусса.
Особливості полягають у наявності двох таблиць - основний ідопоміжний, порядок їх заповнення і певної специфічності розрахунковихформул.
- 10 -
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
- 11 -
3. РОЗРОБКА І ОПИС алгоритм розв'язання задачі
3.1 Побудова математичної моделі задачі
| | На вироб-во | На вироб-во | підпр-е |
| | Виробу А, годин | вироби B, годин | надасть, годин |
| Обладнання-е 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. Формування системи обмежень.
При визначенні плану виробництва продукції повинні бути враховані обмеження на час, що адміністрація підприємства зможе пре -
- 12 -
доставити на виготовлення всіх виробів. Це призводить до наступних трьох обмежень: 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. < p> 2. Канонізіруем систему обмежень:
- 13 -
x1 + 5x2 + x3 = 10;
3x1 + 2x2 + x4 = 12;
2x1 + 4x2 + x5 = 10. x1 (0; x2 (0.
A1 A2 A3 A4 A5 A0
3. Заповнюється вихідна симплекс-таблиця і розраховуються симплекс-різниці за формулами:
(0 = - поточне значення цільової функції
(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
- 14 -
У даному випадку спочатку це А3.
5. Заповнюється нова симплекс-таблиця з виключення Жордана - Гаусса: а). направляючу рядок i * ділимо на напрямний елемент: aij = aij/aij, де j = 1 .. 6 б). перетворення всієї решти матриці: a ij = aij - aij (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 |
- 15 -
Так як всі симплекс-різниці позитивні, то оптимальне рішеннязнайдено:
X = (7/2, 3/4, 11/4, 0, 0) (одиниць) max F = 9 1/4 (рублів)
- 16 -
4. АНАЛІЗ МОДЕЛІ На чутливість
4.1 Побудова двоїстої задачі та її чисельне рішення
Проведення аналізу на чутливість пов'язане з теорієюподвійності, тому в курсовій роботі необхідно побудувати двоїстузадачу і знайти її чисельне рішення.
Для даної моделі двоїста задача має вигляд: min T (y) = min (10y1 + 12y2 + 10y3) за умов y1 + 3y2 + 2y3 (2 < p> А1
5y1 + 2y2 + 4y3 (3 А2 y1 (0, y2 (0, y3
(0. А3, А4, А5
Оптимальне рішення двоїстої задачі виходить при вирішенні прямоїзавдання з останньої симплекс-таблиці. У результаті одержуємо оптимальнерішення двоїстої задачі:
Yопт = (0, 1/4, 5/8, 0, 0), для якого Т (yопт) = 9 1/4.
Оптимальне значення цільової функції двоїстої задачі співпадає зоптимумом цільової функції прямої задачі, в чому не важко переконатися.
4.2 Визначення статусу ресурсів
Ресурси відносяться до дефіцитним, якщо оптимальний план передбачаєїх повне використання, при частковому використанні ресурсів, вонивважаються не дефіцитними. Статус ресурсів для будь-якої моделі лінійногопрограмування можна встановити безпосередньо з оптимальною симплекс -таблиці вихідної за значенням додаткових змінних. Позитивнезначення до -
- 17 -
полнітельной змінної вказує на неповне використанняоб'єкта, тобто на його недефіцитних, нульове значеннядодаткової змінної вказує на дефіцитність ресурсу.
Для даного прикладу додаткові змінні х4 і х5 дорівнюють нулю,отже, обладнання другого і третього типів є
"Дефіцитними", а першого типу - "недефіцитних" (х3 = 2,75). Такий жевисновок можна зробити з рішення двоїстої задачі.
4.3 Визначення значимості ресурсів
Значимість ресурсу характеризується величиною поліпшення оптимальногозначення цільової функції F, що припадає на одиницю приросту даногоресурсу. Значимість ресурсів завжди можна визначити за значеннямподвійних змінних в оптимальному вирішенні двоїстої задачі.
У даному випадку Yопт = (0, 1/4, 5/8, 0, 0). Таким чином, з двох
"Дефіцитних" ресурсів обладнання другого типу має велику значимість ізбільшення інтервалу роботи на цьому обладнанні більш вигідно з точкизору впливу на значення цільової функції.
4.4 Визначення допустимого інтервалу зміни запасу ресурсів
Зміна відведеного адміністрацією підприємства часу (тобто правихчастин обмежень) може призвести до неприпустимість поточного рішення.
Тому важливо визначити діапазон змін компонент вектора обмежень,в якому допустимість рішень не порушується.
Обладнання другого типу, що використовується для виготовленнявиробів, є "дефіцитним і має велику значимість. Визначимодіапазон припустимих змін інтервалу роботи на цьому обладнанні.
Оптимальна
- 18 -
симплекс-таблиця задачі має вигляд:
| | | 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 |
Так як початковими базисними змінними були x1, x2, x3 воптимальної симплексного таблиці у відповідних стовпцях розташованаматриця А-1 Змінимо час роботи на обладнання другого типу на величину
(2, тоді час роботи буде 12 + (2.
Знайдемо базисна рішення, що відповідає зміненим часу роботи наобладнанні другого типу:
0.75 - (2/4 (0, (2 = 3;
2.75 + 3 (2/4 (0, ( 2 = -3.66;
3.5 + (2/2 (0, (2 = -7.
Звідси видно, що -3.66 ((2 (3, тобто 8.34 (b2 (15.
Таким чином початковий інтервал роботи на обладнанні другоготипу можетбить збільшений до 15 годин або зменшений до 8.34 години без порушеннядопустимого рішення. Зменшення часу тягне за собою зменшення одиницьвироблюваної продукції, тому є не доцільним.
- 19 -
4.5 Дослідження залежності оптимального рішення від змін запасів ресурсів
Зміна вільного члена обмеження вихідної задачі на величину ( 2викликає зміну цільової функції на (F = (i (yj. Якщо прирістчасу роботи Берта з інтервалу допустимих змін, значеньподвійних оцінок залишаються незмінними. Таким чином, зміна цільовоїфункції лінійно буде залежати від зміни часу роботи.
У даному прикладі (F = (i (12 = 12 ((i. Шукається залежністьзначень цільової функції від зміни часу роботи на обладнаннідругого типу. Для цього змінюється час роботи починаючи від 0 годин з крокомh = 0.5 до 3 часов.Результати вимірювань наведені в таблиці 1.
Таблиця 1
| (2, годин | 0 | 0.5 | 1 | 1.5 | 2 | 2.5 | 3 |
| b2, годин | 12 | 12.5 | 13 | 13.5 | 14 | 14.5 | 15 |
| (F, руб. | 0 | 6.25 | 13 | 20.25 | 28 | 36.25 | 45 |
| F, руб. | 9.25 | (| (| (| (| (| |
Оскільки залежність F (b2) - лінійна, то достатньо підрахувати значенняфункції в двох крайніх точках інтервалу.
Cледовательно, зі збільшенням часу роботи на обладнанні другоготипу на 2 години збільшується і обсяг виробів на загальною вартістю 28рублів.
- 20 -
5. ГРАФІЧНЕ ПОДАННЯ ОТРИМАНИХ
РЕЗУЛЬТАТІВ
Графічний метод застосовується лише для двох і менш змінних х, щопідходить до даного заданію.Лініі, відповідні обмеження, будуються наосях Ох. Заштрихована область - область допустимих стратегій. x1 + 5x2 (10;
3x1 + 2x2 (12;
2x1 + 4x2 (10. x1 (0; x2 (0.
1). x1 + 5x2 (10; x1 = 0, x2 = 2; x1 = 10, x2 = 0.
2). 3x1 + 2x2 (12; x1 = 0, x2 = 6; x1 = 4, x2 = 0.
3). 2x1 + 4x2 (10; x1 = 0, x2 = 2.5; x1 = 5, x2 = 0.
4). Знайдемо екстремум функції:
F = 2x1 + 3x2,
Графічно область допустимих рішень показано на малюнку 1.
- 21 -
Малюнок 1 - Область допустимих рішень даної системи.
- 22 -
6. ВИСНОВКИ ТА РЕКОМЕНДАЦІЇ ЩОДО ПРАКТИЧНОГО
ВИКОРИСТАННЯ
Складання математичної моделі і рішення систем лінійних нерівностейчасто має місце в реальному житті. Приклади таких завдань:
Приклад 1. Розглядається робота промислового підприємства під кутомзору його рентабельності, причому приводиться ряд заходів з метою підвищення цієїрентабельності. Показник ефективності - прибуток (або середній прибуток),принесена підприємством за господарський рік.
Приклад 2. Група винищувачів піднімається в повітря для перехопленняодиночного літака супротивника. Мета операції - збити літак. Показникефективності - імовірність ураження цілі.
Приклад 3. Ремонтна майстерня займається обслуговуванням машин; їїрентабельність визначається кількістю машин, обслужених протягом дня.
Показник ефективності - середня кількість машин, обслугованих за день.
Приклад 4. Група радіолокаційних станцій в певному районі ведеспостереження за повітряним простором. Завдання групи - знайти будь-якийлітак, якщо він з'явиться в районі. Показник ефективності - ймовірністьвиявлення будь-якого літака, що з'явився в районі.
Приклад 5. Предпрінемается ряд заходів щодо підвищення надійності електронноїцифрової обчислювальної техніки (ЕЦВТ). Мета операції - зменшити частотупояви несправностей ( "збоїв") ЕЦВТ, або, що рівносильно, збільшитисередній проміжок часу між сдоямі ( "напрацювання на відмову").
Показник ефективності - середній час безвідмовної роботи ЕЦВТ.
Приклад 6. Проводиться боротьба за економію коштів при виробництвіпевного виду товару. Показник ефективності - кількістьсикономленних коштів.
За допомогою аналізу моделі на чутливість визначити параметр, відякого результат залежить більше і вирішити, яким способом можливозбільшення ефективності і на скільки, а також багато чого іншого.
- 23 -
ДОДАТОК
- 24 -
ЗМІСТ
ВСТУП. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . 25
1. ПРИЗНАЧЕННЯ ПРОГРАМИ. . . . . . . . . . . . . . . . . . . . . . . . . .
. . 26
2. УМОВИ ЗАСТОСУВАННЯ. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . 26
1.1 Обмеження й область застосування. . . . . . . . . . . . . . . .
. . . . . 6
1.2 Вимоги до технічних засобів. . . . . . . . . . . . . . .
. . . . . 7
3. ВХІДНІ І ВИХІДНІ ДАНІ. . . . . . . . . . . . . . . . . . . . . .
5
4. ІНСТРУКЦІЯ КОРИСТУВАЧУ. . . . . . . . . . . . . . . . . . . . . . . .
. 11
5. ТЕКСТ вихідних модулів. . . . . . . . . . . . . . . . . . . . . . . . .
. . 11
6. ОПИС ЛОГІКИ СТРУКТУРНОЇ СХЕМИ. . . . . . . . . . . . 11
7. ТЕСТОВИЙ ПРИКЛАД. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 25
- 25 -
ВСТУП
У цій частині пояснювальної записки до курсової роботи представлена іописана програма, реліз рішення систем лінійних нерівностей табличнимметодом.
- 26 -
1. ПРИЗНАЧЕННЯ ПРОГРАМИ
Програма передбачена для розв'язання систем лінійних нерівностейтабличним методом, а так само для спроби оптимізації різнихекономічних, соціальних тощо проблем.
Метод, описаний у програмі, може застосовуватись на державних іприватних підприємствах для поліпшення ефективності виробництва.
- 27 -
2. УМОВИ ЗАСТОСУВАННЯ
1.1 Обмеження й область застосування
Із програмних коштів потрібно операційна система MS DOS версії 5.0, програмна середа NORTON COMMANDER, мова програмування
Borland Pascal 7.0. Крім того НГМД повинен містити файли в директорії
KURSOVIK:
1. Файл вхідних даних - KURS97.DAT
2. Програмний файл - KURS97.EXE
1.2 Вимоги до технічних засобів
IBM PC або IBM PC - сумісний комп'ютер з дисководом 3.25 "ємністю
1.2 Мб.
- 28 -
3. ВХІДНІ І ВИХІДНІ ДАНІ
Вхідні та вихідні дані заносяться у файли KURS97.DAT і KURS97.RESвідповідно. Вхідні дані записуються в певному порядку.
Вихідні дані записуються у вигляді симплекс-таблиць.
- 29 -
4. ІНСТРУКЦІЯ КОРИСТУВАЧУ
Вхідні дані вносяться в файл KURS 97.DAT в такій черговості: сначача вводяться коефіцієнти при невідомих у цільовій функції, потім вводяться елементи вектора обмежень, а потім - елементи матриціобмежень по стовпцях.
Результати обчислень ви знайдете у файлі KURS 97.REZ.
- 30 -
5. ТЕКСТ вихідних модулів
Повний текст програми KURS97.PAS виглядає наступним чином:
. program Kurs97;
uses crt;
const n = 2; m = 3;
Epsilon = 0.000001;
var
VectorA: array [1 .. m, 0 .. m + n] of real;
TargetVector: array [1 .. m + n] of real; < p> SimplexVector: array [0 .. m + n] of real;
DigitOfBasisVector: array [1 .. m] of real;
BasisVector: array [1 .. m ] of integer;
IndexOfEnterVector: integer;
IndexOfOutputString: integer;
MinimumBuffer: real;
key: char;
FileOfOutput: text;
(Опис процедур)
procedure ReadDates; (зчитування даних з файлу) var
DateFile: text;
procedure ReadDatesTargetVector; (зчитування даних цільового вектора
) Var i: integer; begin for i: = 1 to n do Readln (DateFile, TargetVector [i]); end;
procedure ReadDatesVectorA; (зчитування вектора А і заповненняодиницями діагоналі) var i, j: integer; begin for j: = 0 to n do for i: = 1 to m do
Readln (DateFile, VectorA [i, j]); i: = 1 ; for j: = n +1 to n + m do
- 31 -
begin
VectorA [i, j]: = 1; inc ( i) end; end;
procedure ReadDatesBasisVector; var i: integer; begin for i: = 1 to m do BasisVector [i]: = n + i; end;
begin
Assign (DateFile, 'kurs97.dat');
Reset (DateFile);
ReadDatesTargetVector;
ReadDatesVectorA;
ReadDatesBasisVector;
Close (DateFile); end;
procedure CountSimplexVector; (розрахунок сімплек-вектора) var i, j: integer;
Summa: real;
Simplex: real; begin
SimplexVector [0]: = 0; for i: = 1 to m do
SimplexVector [0 ]: = SimplexVector [0] +
DigitOfBasisVector [i] * VectorA [i, 0]; for j: = 1 to m + n do begin
Summa: = 0; for i: = 1 to m do Summa: = Summa + DigitOfBasisVector [ i] * VectorA [i,j];
SimplexVector [j]: = Summa - TargetVector [j]; if abs (SimplexVector [j]) SimplexVector [i] then
- 32 -
begin
GetEnterVector: = i;
Min: = SimplexVector [i]; end; end;
function GetOutputString: integer; (пошук виводиться рядка) var i: integer;
Temp: real; begin
GetOutputString: = 1; if VectorA [1, IndexOfEnterVector]> 0 then MinimumBuffer: = VectorA [1,
0]/VectorA [1, IndexOfEnterVector]; for i: = 2 to m do begin
Temp: = VectorA [i, 0]/VectorA [i, IndexOfEnterVector]; if Temp> 0 then if MinimumBuffer > = Temp then begin
MinimumBuffer: = Temp;
GetOutputString: = i; end; end; end;
procedure ReCountOutputString; (перерахунок коефіцієнтів що виводитьсярядка) var i, j: integer;
Buffer: real;
procedure ReCountDigitOfBasisVector; begin
DigitOfBasisVector [IndexOfOutputString]: = TargetVector [IndexOfEnterVector]; end ;
procedure ReCountBasisVector; begin
BasisVector [IndexOfOutputString]: = IndexOfEnterVector; end;
begin
ReCountDigitOfBasisVector;
ReCountBasisVector;
Buffer: = VectorA [IndexOfOutputString, IndexOfEnterVector]; for i: = 0 to m + n do begin
VectorA [IndexOfOutputString, i]: = VectorA [ IndexOfOutputString, i]/
Buffer; end; end;
- 33 -
procedure ReCountVectorA; var i, j: integer; begin for j: = 0 to m + n do begin for i: = 1 to m do begin if i IndexOfOutputString then if j IndexOfEnterVector then VectorA [i, j]: = VectorA [i, j] - VectorA [i,
IndexOfEnterVector] * VectorA [IndexOfOutputString, j]; end; end; for i: = 1 to m do if i IndexOfOutputString then VectorA [i, IndexOfEnterVector]: = 0; end;
function AllIsPositiv: boolean; var i: integer; begin
AllIsPositiv: = True; for i: = 1 to m + n do if SimplexVector [i] <0 then AllIsPositiv: = False; end;
function ToStr (const D: real): string; var S: string; begin str (D: 6:2, S);
ToStr: = '' + S + ''; end;
procedure WriteMatrixs;
procedure WriteTargetMatrix; var i: integer; begin writeln ( '+---------------------- -----------------< br>--------------+'); Write ( '| Target |'); for i: = 1 to n + m do write (ToStr (TargetVector [i ]),'|' ); writeln; end;
procedure WriteMatrixA; var i, j: integer; begin writeln ( '+-----------------+---- ----+--------+--------+--------+---< br>-----+--------|'); Writeln ( '| Basis | D. Basis | A 0 | A 1 | A 2 | A 3 |
A 4 | A 5 | '); writeln (' +--------+--------+--------+--------+- -------+--------+---< br>-----+--------|'); For i: = 1 to m do
- 34 -
begin write ( '| A' , BasisVector [i], '
| ', ToStr (DigitOfBasisVector [i ]),'|'); for j: = 0 to m + n do write (ToStr (VectorA [i, j ]),'|'); writeln; if i = m then writeln ( '+--------+--------+--------+--------+-----< br>---+--------+--------+--------|') Else writeln ( '+--------+--- -----+--------+--------+-----< br>---+--------+--------+--------|'); End; end;
procedure WriteMatrixSimplex; var i : integer; begin write ( '| Simplex |'); for i: = 0 to m + n do write (ToStr (SimplexVector [i ]),'|'); writeln; writeln ( '+------ ------------------------------------------< br>--------------+'); End;
begin clrscr;
WriteTargetMatrix;
WriteMatrixA;
WriteMatrixSimplex; end;
procedure WriteMatrixsInFile;
procedure WriteTargetMatrix; var i: integer; begin writeln (FileOfOutput, '+--------- ----------------< br>----------------------------+'); Write (FileOfOutput, '| Target |'); for i: = 1 to n + m do write (FileOfOutput, ToStr (TargetVector [i ]),'|'); writeln (FileOfOutput); end;
procedure WriteMatrixA; var i, j: integer; begin writeln (FileOfOutput, ' +-----------------+--------+--------+-------< br>-+--------+--------+--------|'); Writeln (FileOfOutput, '| Basis | D. Basis | A 0 | A 1 | A 2
| A 3 | A 4 | A 5 | '); writeln (FileOfOutput,' +--------+--------+-------- +--------+-------< br>-+--------+--------+--------|'); For i: = 1 to m do begin write (FileOfOutput, '| A', BasisVector [i], '
| ', ToStr (DigitOfBasisVector [i ]),'|'); for j: = 0 to m + n do write (FileOfOutput, ToStr (VectorA [i, j ]),'|'); writeln (FileOfOutput); if i = m then writeln (FileOfOutput, '+--------+--------+--------< br>+--------+--------+--------+--------+--------|') Else writeln (FileOfOutput, '+--------+--------+--------< br>+--------+--------+--------+--------+--------|'); End ; end;
- 35 -
procedure WriteMatrixSimplex; var i: integer; begin write (FileOfOutput, '| Simplex |'); for i: = 0 to m + n do write (FileOfOutput,
ToStr (SimplexVector [i ]),'|'); writeln (FileOfOutput); writeln (FileOfOutput, '+-------------------------- --------< br>----------------------------+'); End;
begin clrscr;
WriteTargetMatrix;
WriteMatrixA;
WriteMatrixSimplex; end;
(Головний програма)
BEGIN
ClrScr ;
ReadDates;
Assign (FileOfOutput, 'kurs97.res');
Rewrite (FileOfOutput);
CountSimplexVector;
WriteMatrixs; while not AllIsPositiv do begin
IndexOfEnterVector: = GetEnterVector;
IndexOfOutputString: = GetOutputString;
ReCountOutputString;
ReCountVectorA;
CountSimplexVector;
WriteMatrixsInFile;
WriteMatrixs; if key = # 0 then key: = readkey; key: = # 0; end ;
Close (FileOfOutput);
END.
- 36 -
6. ОПИС ЛОГІКИ СТРУКТУРНОЇ СХЕМИ
У програмі реалізовані наступні процедури:
1. Процедура ReadDates - зчитує дані з файлу.
2. Процедура ReadDatesTargetVector - зчитує коефіцієнти приневідомих у цільовій функції з файлу.
3. Процедура ReadDatesVector - читання їх вхідного файлу матриці А ізаповнення діагональної матриці.
4. Процедура CountSimplexVector - розрахунок симплекс-різниць.
5. Процедура GetEnterVector - пошук вводиться в базис стовпця.
6. Процедура GetOutputString - пошук що виводиться з базису рядка.
7. Процедура ReCountOutputString-пересчее що виводиться рядка.
8. Процедура ReCountVectorA - перерахунок решті матриці обмежень.
9. Процедури WriteMatrixA, WriteTargetMatrix, WriteMatrixSimplex --друк результуючих таблиць на екран і в файл.
- 37 -
7. ТЕСТОВИЙ ПРИКЛАД
Тестовий приклад програми KURS 97.EXE представлений на малюнку 2 у виглядівихідної та результуючих симплекс-таблиць даного завдання.
- 39 -
ЛІТЕРАТУРА
1. Еурд ГОСТ 19.105-78, 19.104-78.
2. Еурд ГОСТ 19.502-78.
3. Венцель Е.С. Дослідження операцій.-М.: Радянське радіо. 1972
4. Дектярев Ю.І. Дослідження операцій.-М.: Вища школа. 1986
5. Зайченко Ю.П. Дослідження операцій.-К.: Вища школа. 1979
6. Зайченко Ю.П., Шуміллова С.А. Дослідження операцій (збірник завдань) .-
К.: Вища школа. 1990
