ЗМІСТ:

Введення
1. Економічна постановка задачі ..
2. Математична постановка задачі ..
3. Вибір методу реалізації моделі. Обгрунтування вибору ..
4. Схема алгоритму і його опис.
5. Коротка характеристика ЕОМ та її програмного забезпечення.
6. Обгрунтування вибору мови програмування.
7. Рішення завдання-тесту для написання і налагодження програми.
8. Аналіз отриманих результатів.
9. Інструкції користувачеві і опис програми.
Висновок.
Література.

ВСТУП
Проникнення математики в економічну науку пов'язано з подоланням значних труднощів. У цьому частково була "повинна" математика, що розвивається протягом декількох століть в основному у зв'язку з потребами фізики і техніки. Але головні причини лежать все ж таки в природі економічних процесів, у специфіці економічної науки.
Більшість об'єктів, що вивчаються економічною наукою, може бути охарактеризований кібернетичним поняттям складна система.
Найбільш поширеним є розуміння системи як сукупності елементів, що перебувають у взаємодії і утворюють певну цілісність, єдність. Важливим якістю будь-якої системи є емерджентним - наявність таких властивостей, які не притаманні жодному з елементів, що входять в систему. Тому при вивченні систем недостатньо користуватися методом їх розчленування на елементи з подальшим вивченням цих елементів окремо. Одна з труднощів економічних досліджень - в тому, що майже не існує економічних об'єктів, які можна було б розглядати як окремі (позасистемні) елементи.
Складність системи визначається кількістю вхідних в неї елементів, зв'язками між цими елементами, а також взаємовідносинами між системою і середовищем. Економіка країни має всі ознаки дуже складної системи. Вона об'єднує величезне число елементів, відрізняється різноманіттям внутрішніх зв'язків та зв'язків з іншими системами (природне середовище, економіка інших країн і т.д.). У народному господарстві взаємодіють природні, технологічні, соціальні процеси, об'єктивні і суб'єктивні чинники.
Складність економіки іноді розглядалася як обгрунтування неможливості її моделювання, вивчення засобами математики. Але така точка зору в принципі неправильна. Моделювати можна об'єкт будь-якої природи і будь-якої складності. І як раз складні об'єкти становлять найбільший інтерес для моделювання; саме тут моделювання може дати результати, які не можна отримати іншими способами дослідження.
Потенційна можливість математичного моделювання будь-яких економічних об'єктів і процесів не означає, зрозуміло, її успішної здійсненності при даному рівні економічних та математичних знань, наявної конкретної інформації та обчислювальної техніки. І хоча не можна вказати абсолютні межі математичної формалiзуються, економічних проблем, завжди будуть існувати ще неформалізовані проблеми, а також ситуації, де математичне моделювання недостатньо ефективно.

2. ЕКОНОМІЧНА ПОСТАНОВКА ЗАВДАННЯ

Цеху, має в своєму розпорядженні трьома видами металорізального обладнання, планується виготовити протягом певного періоду часу два вироби, причому перший виріб комплектується на двох деталях А1 і А2, які повинні виготовлятися відповідно 2:1.
лось виріб також комплектується на двох деталях А3 і А4, що виготовляються відповідно у співвідношенні 4:1
Ефективні фонди часу роботи обладнання та норми штучно-калькуляційного часу, необхідні на виготовлення кожної деталі на відповідному обладнанні, наведені в таблиці 2.1:

3. Математична постановка задачі


Загальна модель:

m (i = 1,2 .. m) - групи обладнання на цеху.
Ai - ресурси з i-ої групи устаткування.
n (j = 1,2 .. n) - види деталей.
ai, j - норми трудомісткості витрачених на i-му вигляді обладнання на виготовлення одиниці j-го виду продукції.
Xj - випуск продукції j-го виду в оптимальному плані.
Kr - Співвідношення деталей у виробі.



Система обмежень:

1. Ресурсні обмеження:
  n
 ?? a i j * x j? A i (i = 1,2, .., m)
j = 1

2. Реальність плану випуску:
Xj?? 0

3. Обмеження за комплектності:
Xk Kl (k = 1,2, ..., l); (r = 1,2, ...., P)
Xr Kp

Цільовий функціонал:
n
     Fmax =?? Xj
j = 1


3. ВИБІР МЕТОДУ РЕАЛІЗАЦІЇ МОДЕЛІ.
ОБГРУНТУВАННЯ МЕТОДУ

Симплекс метод - універсальний метод для вирішення лінійної системи рівнянь або нерівностей і лінійного функціоналу.
Для привиди системи обмежень нерівностей до канонічного виду, необхідно в системі обмежень виділити одиничний базис.
I. Обмеження виду «?» - Ресурсні обмеження. Справа знаходиться те що ми використовуємо на виробництві, ліворуч - то що отримуємо. За таких обмеження вводять додаткові змінні з коефіцієнтом «1», що утворюють одиничний базис. У цільову функцію ці змінні увійдуть з коефіцієнтом «0».
II. Обмеження виду «=». Часто буває, що не дивлячись на те що обмеження мають вигляд рівності, одиничний базис не виділяється або важко виділяється. У цьому випадку вводяться штучні змінні для створення одиничного базису - Yi. До системи обмежень вони входять з коефіцієнтом «1», а в цільову функцію з коефіцієнтом «M», які прагнуть до нескінченності (при Fmin - «+ M», при Fmax - «-M»).
III. Обмеження виду «?» - Планові обмеження. Додаткові змінні (X), що несуть певний економічний зміст - перевитрата ресурсів або перевиконання плану, перевиробництво, додаються з коефіцієнтом «-1», в цільову функцію - з коефіцієнтом «0». А штучні змінні (Y) як у попередньому випадку.


Алгоритм симплекс методу.
(першу симплекс таблиця)

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

X1 + q1, m +1 Xm +1 + .... + Q1, m + n Xm + n = h1
X2 + q1, m +1 Xm +1 + .... + Q1, m + n Xm + n = h1
X3 + q1, m +1 Xm +1 + .... + Q1, m + n Xm + n = h1
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ....
Xm + qm, m +1 Xm +1 + .... + Qm, m + n Xm + n = hm

У ній m базисних змінних, k вільних змінних. m + k = n - всього змінних.
Fmin = C1X1 + C2X2 + C3X3 +....+ CnXn
Всі hi повинні бути більше або дорівнюють нулю, де i = 1,2 ... m. На першому кроці в якості допустимого рішення приймаємо всі Xj = 0 (j = m +1, m 2 ,..., m + k). При цьому всі базисні змінні Xi = Hi.
Для подальших міркувань обчислень будемо користуватися першим симплекс таблицею (таблиця 3.1).
Таблиця 3.1.
Симплекс таблиця.
C
Б
H
C1
C2
...
Cm
Cm 1
...
Cm + k



X1
X2
...
Xm
Xm +1
...
Xm + k
C1
C2
C3
:
:
Cm
X1
X2
X3
:
:
Xm
h1
h2
h3
:
:
hm
1
0
0
:
:
0
0
1
0
:
:
0
:
:
:
:
:
:
0
0
0
:
:
0
q1, m +1
q2, m +1
q3, m +1
:
:
qm, m +1
:
:
:
:
:
:
q1, m + k
q2, m + k
q3, m + k
:
:
qm, m + k

F =
F0
??
??
...
? m
? m +1
...
? m + k
Перший стовпець-коефіцієнти цільової функції при базисних змінних.
Другий стовпець - базисні змінні.
Третій стовпець - вільні члени (hi? 0).
Самая верхній рядок - коефіцієнти при цільовій функції.
Друга верхній рядок - самі змінні, що входять в цільову функцію і в систему обмежень.

Основне поле симплекс методу - система коефіцієнтів з рівняння.
Останній рядок - служить для того, щоб відповісти на питання: «оптимальний план чи ні».

Для першої ітерації F0 =?? Ci * hi.
????????????????? m - оцінки вони розраховуються за формулою:
?? j =? ciqij-cj.

Індексний рядок дозволяє нам судити про оптимальність плану:
1. При відшуканні Fmin в індексному рядку повинні бути негативні і нульові оцінки.
2. При відшуканні Fmax в індексному рядку повинні бути нульові і позитивні оцінки.

Перехід до другої ітерації:
Для цього знаходимо ключовий (головний) стовпець і ключову (головну) рядок.
Співпадіння стовпцем є той в якому знаходиться найбільший позитивний елемент індексного рядка при відшуканні Fmin або найменший негативний елемент при відшуканні Fmax.
Ключовий рядком називається та, в якій міститься найменше позитивне частка від розподілу елементів стовпця H на відповідні елементи ключового стовпця.
На перетині рядка і стовпця знаходиться дозволяє елемент.
На цьому етапі здійснюється до переходу до подальших ітерацій.

Перехід до ітерація:
1. Виводиться базис ключовою рядки, поступаючись місцем змінної з ключового стовпця зі своїм коефіцієнтом.
2. Заповнюється рядок знову введеного базису шляхом ділення відповідних елементів виділеної рядки попередньої ітерації на дозволяє елемент.
3. Якщо у головній рядку міститься нульовий елемент, то стовпець, в якому знаходиться цей елемент переноситься в наступну ітерацію без зміни.
4. Якщо в головному стовпці є нульовий елемент, то рядок, у якому він знаходитися переноситися без зміни в подальшу ітерацію.
5. Інші елементи переносяться за формулою:


Метод штучного базису.
(Друга симплекс таблиця)

При використанні штучного базису необхідно домагатися виходу штучних змінних з базису і введення в нього незалежних змінних. Для цієї мети можна також використовувати симплекс метод, причому рішення розпадається на дві фази:
I. Побудова штучного базису та оптимізація функції суми штучних змінних, тобто F0 = Y1 + Y2 + ... + Yn = 0 (F? Min). Якщо при цьому F0 = 0, то штучний базис ми вивели зі складу змінних, переходимо до другої фази - вирішуємо задачу по перше симплекс таблиці з дійсними змінними. Якщо ж F0? 0, тобто штучний базис не виведений зі складу змінних - ОЗЛП рішень не має.
II. Рішення перетвореної системи обмежень із заданою цільовою функцією і дійсними змінними. При цьому стовпцями штучних змінних в симплекс методі нехтуємо.

Зауваження:
1. При рішенні задач на max з штучним базисом слід переходити до вирішення на min, змінюючи лише тільки цільову функцію:
Fmax = - Fmin.
2. При вирішенні ОЗЛП з штучним базисом особливу увагу слід звернути на обчислення елементів індексних рядків.
a) Для стовпців X обчислення елементів йде за формулами:
?? j =? qij.
   ? yi = y1 + y2 + ... + yR.
   ? Hi = F0.
    
    Примітка: тільки для рядків Y.
    
б) Для стовпців Y працює стара формула:
?? j =? ciqij-cj.

1.
Схема алгоритму ТА ЇЇ ОПИС

  1. Початок програми
  2. Процедура введення даних
  3. Процедура приведення до канонічного вигляду
  4. Процедура побудови симплекс таблиці
  5. Функція пошуку ключового стовпця
  6. Функція пошуку ключовою рядків
  7. Перевірка умови: Якщо в головній рядку нульовий елемент.
  8. Процедура переносу в наступну ітерацію головною рядка.
  9. Перевірка умови: Якщо в головному стовпці нульові елементи.
  10. Процедура переносу стовпця в наступну ітерацію.
11, 12. Процедура розрахунку інших елементів за формулою.
13, 14. Функція дослідження на max.
15, 16. Функція дослідження на min.
17. Процедура виведення оптимального рішення.
18. Кінець програми.




 

5. СУЧАСНИЙ СТАН ЕОМ ТА ЇЇ
ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ


Загальні відомості про IBM PC

  Коли вимовляють слова "персональний комп'ютер", звичайно мається на увазі не що інше, як комп'ютер типу IBM PC. Саме американська компанія IBM в серпні 1981 року оголосила про випуск самого першого комп'ютера, що отримав назву Personal Computer, або просто PC.

  Втім, ще до створення IBM PC безліччю різних фірм ви пускалися комп'ютери, які було б цілком доречно називати персональними. Навіть дуже далека від електроніки фірма Coca - Cola намагалася випускати власну модель персонального комп'ютера!

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

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

  Ось яскравий тому приклад. Комп'ютер IBM PC майже з самого початку працював під керуванням дискової операційної системи DOS, яку розробила для IBM маленька і нікому тоді не відома фірма Microsoft. Сьогодні Microsoft - безперечний флагман індустрії програмного забезпечення, одна з найбагатших фірм світу, що випускає не тільки операційні засоби MS - DOS і Windows для керування комп'ютерами, але й різні прикладні пакети. А засновник і керівник Microsoft Білл Гейтс, не дивлячись на молодість, одна з найбагатших людей.
  Зрозуміло, персоналки IBM PC виявилася лише першим кроком у правильному напрямку. Потім фірма IBM випустила безліч моделей персональних комп'ютерів XT, AT, PS/2 і PS/1 на різних процесорах Intel 80286, 80386, 80486, Pentium. Всі ці комп'ютери призначені для роботи під управлінням операційних систем DOS, WINDOW'95, OS/2.

Основний постачальник процесорів для IBM-сумісних комп'ютерів є фірма INTEL. Останнім часом багато хто інші фірми, такі як AMD, CYREX стали випускати власні процесори, які повністю сумісні з процесорами фірми INTEL.

Фірма AMD випускає більше дешеві, але не поступаються за якістю, а іноді й перевершують процесори (наприклад процесори серії K6). І багато фірм, які випускають персональні комп'ютери, почали переходити з процесорів фірми INTEL на процесори фірми AMD.

Операційна система MS DOS та інші

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

  Операційна система здійснює завантаження в оперативну пам'ять всіх програм, передає їм керування на початку їх роботи, виконує різні дії за запитом виконуваних програм і звільняє займану програмами оперативну пам'ять при їх завершення.
В даний час існують більш сучасні операційні системи, з набагато більшим набором можливостей. Це WINDOWS '95, OS/2. Але оскільки ці операційні системи диктують користувачеві «свої умови», такі як працювати у вікні, програми повинні мати стандартні меню і загальний вигляд, багато програмісти роблять свої програми з DOS, тому що вона дозволяє більш гнучко використовувати можливості комп'ютера.



Рекомендована конфігурація для програми SIMPLEX METHOD:

Даною програмі потрібна мінімальна конфігурація:

Процесор 386 (рекомендується 486 or high)
1М оперативної пам'яті.
2М жорсткого диска.
VGA monitor

6. ОБГРУНТУВАННЯ ВИБОРУ МОВИ ПРОГРАМУВАННЯ


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



7. РІШЕННЯ ЗАДАЧІ ТЕСТУ ДЛЯ
     Написання і налагодження ПРОГРАМИ



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

   1.2X1 + 1.8X2 + 2.4X3? 768
   2.4X1 + 1.2X3 + 2.4X4? 600
   1.2X2 + 1.2X3 + 1.2X4? 480
   
   
   Обмеження щодо комплектності:
A1 2
A2 1
A1 = 2A2
A34
A41
A3 = 4A4
   
   Звідси складаємо систему рівнянь:
   
   X1-2X2 = 0
   X3 - 4X4 = 0


   Отже, система обмежень задачі складається з 5 рівнянь і цільової функції:
   Fmax = X1 + X2 + X3 + X4

Наводимо систему до канонічного вигляду:

   1.2X1 + 1.8X2 + 2.4X3 + X5? 768
   2.4X1 + 1.2X3 + 2.4X4 + X6? 600
   1.2X2 + 1.2X3 + 1.2X4 + X7? 480
 X1-2X2 + Y1 = 0
   X3 - 4X4 + Y2 = 0

Наводимо цільову функцію до канонічного вигляду:
Fmax = X1 + X2 + X3 + X4 + 0X5 0 X6 0 X7-My1-My2

Оскільки введені штучні змінні - досліджуємо на мінімум.
Fmin =-X1-X2-X3-X4 - 0X5-0X6-0X7 + My1 + My2



Таблиця 7.1
Симплекс таблиця



-1
-1
-1
-1
0
0
0
M
M
C
Б
H
X1
X2
X3
X4
X5
X6
X7
Y1
Y2
0
0
0
M
M
X5
X6
X7
Y1
Y2
768
600
480
0
0
1.2
2.4
0
1
0
1.8
0
1.2
-2
0
2.4
1.2
1.2
0
1
0
2.4
1.2
0
-4
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1


0
1
-2
1
-4
0
0
0
0
0
0
0
0
M
-1
X5
X6
X7
Y1
X3
768
600
480
0
0
1.2
2.4
0
1
0
1.8
0
1.2
-2
0
0
0
0
0
1
9.6
7.2
6.0
0
-4
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0



0
1
-2
0
0
0
0
0
0

0
0
0
-1
-1
X5
X6
X7
X1
X3
768
600
480
0
0
0
0
0
1
0
4.2
4.8
1.2
-2
0
0
0
0
0
1
9.6
7.2
6.0
0
-4
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0




0
0
3
0
5
0
0
0


0
0
-1
-1
-1
X5
X6
X4
X1
X3
0
24
80
0
320
0
0
0
1
0
2.28
3.36
0.2
-2
0.8
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
-1.6
-1.2
0.16
0
0.66




-400
0
2
0
0
0
0
-0.83


-1
0
-1
-1
-1
X2
X6
X4
X1
X3
0
24
80
0
320
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0.43
-1.47
-0.08
0.87
-0.35
0
1
0
0
0
-0.7
1.15
0.3
-1.4
1.22




-400
0
0
0
0
-0.87
0
0.57


-1
0
-1
-1
-1
X2
X7
X4
X1
X3
14.54
20.72
73.63
29.08
294.5
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
-0.45
-1.27
0.3
-0.9
1.21
0.6
0.86
-0.26
1.21
-1.06
0
1
0
0
0




-410
0
0
0
0
-0.15
-0.49
0


Індексний рядок при дослідженні на мінімум не містить позитивних елементів, значить, отримано оптимальне рішення:

Fmax = - Fmin = 410 - максимально можливий випуск продукції (шт).
X1 = 29, 08 - Деталі А1 (шт).
X2 = 14, 54 - Деталі А2 (шт).
X3 = 294, 52 - Деталі А3 (шт).
X4 = 73, 63 - Деталі А4 (шт).
X7 = 20, 72 - Відсутні ресурси (верстато-години).



8. АНАЛІЗ ОДЕРЖАНИХ РЕЗУЛЬТАТІВ
     

Вирішуючи задачу симплекс методом ми отримали:

Деталі A1 так ставляться до деталей A2, як 2:1, тобто деталей A1 - 30 штук, а деталей A2 - 15 штук. Співвідношення, поставлене умовою завдання, виконано.
Співвідношення між деталями A3 і A4 теж виконано. Деталі A3 повинні ставитися до деталей A4 як 4:1. Це вірно, тому що деталей A3 - 292 штуки, а деталей A4 - 73 штуки.

Але на третій групі устаткування йде недовикористання ресурсів на 20 верстато-годин.

Максимально можлива завантаження наявного обладнання - 410 деталей.


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


9. ІНСТРУКЦІЇ КОРИСТУВАЧУ І ОПИС
ПРОГРАМИ

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

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

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

У будь-якому випадку ви запускаєте ТІЛЬКИ файл KoSer.EXE. У вас запуститься графічна оболонка.
   У цій оболонці будуть наступні іконки:
   
- Simplex Method, це сама програма для вирішення рівнянь.
- Перегляд результатів, щоб переглянути результат після рішення.
- Tetris, звичайна гра для розваги.
- MsDos, Тимчасовий вихід у DOS
- Exit, вихід з оболонки KoSer.

У програмі «Simplex Method» є кнопки «Додати рядок», «Додати стовпець», «Видалити рядок», «Видалити стовпець», «Розрахувати», «Вирішити на MAX або MIN», «Рішення Цілочисельне або НЕ Цілочисельне».
Перехід до цих кнопок здійснюється клавішею «TAB» або (бажано) за допомогою мишки.
Рух по числовим значенням рівняння здійснюється стрілками. Введення чисел проводиться просто набором цифр, нашому осередку.
Зміна знака здійснюється клавішею «пробіл».
Вихід - хрестик у верхньому кутку екрану або клавіша «ESC».



ВИСНОВОК

Дана дипломна робота включає в себе два предмети: «мови програмування» і «математичні методи в економіці».

У курсовій роботі були розглянуті наступні питання:
- Розглянуто і проаналізовано алгоритм симплекс методу.
- Дана коротка характеристика ЕОМ, включаючи історію появи і опис операційної системи MSDOS.
- Розглянуто вибір мови програмування.
- Написана програма для вирішення даної і багатьох інших завдань.
- Дані інструкції користувачеві.

   Дана програма була протестована на дуже багатьох прикладах і скрізь вона видавала правильні результати.
   
   Єдине обмеження, кількість стовпців не повинно перевищувати 7 і рядків не повинно перевищувати 10.
   
   Програма вважає з точністю 2 знака після коми.
   


Список використовуваної літератури:

1. Ліщенко «Лінійне і нелінійне програмування», 1987

2. А.Н. Карасьов, Н.Ш. Кремер, Т.Н. Савельєва
«Математичні методи в економіці», 1987


   
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
 ПРОГРАМИ



- 1 -

КР 2203 - 81 11