Рішення транспортних задач

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.


Нажми чтобы узнать.
скачати

ЗМІСТ
ВСТУП 5
1. ЗАГАЛЬНА ЧАСТИНА 8
1.1 Математична постановка завдання 8
1.2 Алгоритм рішення задачі 11
1.3 Блок-схема (алгоритм розв'язання) 25
2. Форми вхідний інформації 27
3. Форми вихідний інформації 28
4. Інструкція для користувача 29
5. Інструкція для програміста 30
ВИСНОВОК 33
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 34
ДОДАТОК А 35

ВСТУП
Математика необхідна у повсякденному житті, отже певні математичні навички потрібні кожній людині. Нам доводиться в житті вважати (наприклад, гроші), ми постійно використовуємо (часто не помічаючи цього) знання про величини, що характеризують протяжності, площі, обсяги, проміжки часу, швидкості і багато чого іншого. Все це прийшло до нас на уроках арифметики і геометрії і стало в нагоді для орієнтації в навколишньому світі.
Математичні знання та навички потрібні практично в усіх професіях, перш за все, звичайно, в тих, що пов'язані з природничими науками, технікою та економікою. Математика є мовою природознавства і техніки і тому професія натураліста й інженера вимагає серйозного опанування багатьма професійними відомостями, заснованими на математиці.
Добре сказав про це Галілей:
«Філософія (на нашій мові-фізика) написана в найбільшій книзі, яка постійно відкрита вашому погляду, але зрозуміти її може лише той, хто спочатку навчиться розуміти її мову і тлумачити знаки, якими вона написана. Написано ж вона на мові математики ».
Сьогодні безсумнівна необхідність застосування математичних знань і математичного мислення лікаря, лінгвістові, історику, і людям інших спеціальностей. Але особливо знання математики необхідні людям точних професій - фінансистам, економістам.
Професійний рівень економіста багато в чому залежить від того, освоїв чи він сучасний математичний апарат і чи вміє використовувати його при аналізі складних економічних процесів і ухвалення рішень. Тому в підготовці економістів широкого профілю вивчення математики займає значне місце. Математична підготовка економіста має свої особливості, пов'язані зі специфікою економічних завдань, а також з широким розмаїттям підходів до їх вирішення.
Завдання практичної і теоретичної економіки дуже різнобічні. До них відносяться, в першу чергу, методи збору й обробки статистичної інформації, а також оцінка стану та перспективи розвитку економічних процесів. Застосовуються різні способи використання отриманої інформації - від простого логічного аналізу до складання складних економіко-математичних моделей і розробки математичного апарату їх дослідження.
Невизначеність економічних процесів, значний випадковий розкид і великий обсяг одержуваної інформації зумовлюють необхідність залучення до дослідження економічних задач теорії ймовірностей та математичної статистики.
Поряд з моделюванням економістам необхідно вивчати теорію оптимізації, яка представлена ​​математичними методами дослідження операцій, у тому числі лінійним програмуванням.
Зазначені напрямки вимагають знання основоположного математичного апарату: основ лінійної алгебри та математичного аналізу, теорії ймовірностей і математичного програмування.
Таким чином, математика і математична освіта потрібні для підготовки до майбутньої професії.
Один з класів математичних моделей-завдання лінійного програмування. Одним із завдань лінійного програмування є транспортна задача-завдання складання оптимального плану перевезень, що дозволяє мінімізувати сумарний кілометраж. Транспортна задача, як і завдання лінійного програмування була вперше поставлена ​​радянським економістом А. Н. Толстим у 1930 році. Розробка загальних методів розв'язання задачі лінійного програмування та їх математичне дослідження пов'язане з ім'ям радянського вченого Л. В. Канторовича. У 1939 році методам вирішення задачі лінійного програмування присвячено також велика кількість робіт зарубіжних вчених. Основний метод розв'язання задачі лінійного програмування-симплекс метод-був опублікований в 1949 році Дандігом. Симплекс метод дає рішення будь-якої задачі лінійного програмування, але якщо змінних дуже багато, то рішення дуже важко і для більш складних завдань симплекс метод стали модифікувати.
Транспортна задача ділиться на два види: транспортна задача за критерієм вартості-визначення плану перевезень, при якому вартість вантажу була б мінімальна; транспортна задача за критерієм часу-більш важливим є виграш за часом.
Транспортна задача за критерієм вартості є окремим випадком задачі лінійного програмування і може бути вирішена симплексним методом. Однак у силу особливостей задачі, вона вирішується набагато простіше.

1. ОСНОВНА ЧАСТИНА
1.1 МАТЕМАТИЧНА ПОСТАНОВКА ЗАВДАННЯ
Транспортна задача-
Однорідний вантаж зосереджений у т постачальників в обсягах .
Цей вантаж необхідно доставити п споживачам в обсягах .
Відомі (I = 1,2, ..., m; j = 1,2, ..., n) - вартості перевезення одиниці вантажу від кожного i-го постачальника кожному j-му споживачеві. Потрібно скласти такий план перевезень, при якому запаси всіх постачальників вивозяться повністю, запити всіх споживачів задовольняються повністю і сумарні витрати на перевезення всіх вантажів мінімальні.
Вихідні дані транспортної задачі записуються у таблиці виду
Таблиця 1


...




...




...

...
...
...
...
...



...

Змінними (невідомими) транспортної задачі є (I = 1, ..., m; i = 1,2, ..., n) - обсяги перевезень від кожного i-го постачальника кожному j-му споживачеві. Ці змінні можуть бути записані в матриці перевезень
Математична модель транспортної задачі в загальному випадку має вигляд
(1.1)
i = 1,2, ..., m, (1.2)
j = 1,2, ..., n, (1.3)
i = 1,2, ..., m; j = 1,2, ..., n. (1.4)
Цільова функція задачі (1.1) виражає вимоги забезпечити мінімум сумарних витрат на перевезення всіх вантажів. Перша група з т рівнянь (1.2) описує той факт, що запаси всіх т постачальників вивозяться повністю. Друга група з n рівнянь (1.3) виражає вимоги повністю задовольнити запити всіх n споживачів. Нерівності (1.4) є умовами неотрицательности всіх змінних завдання.
Таким чином, математична формулювання транспортної задачі полягає в наступному: знайти змінні завдання
i = 1,2, ..., m; j = 1,2, ..., n,
задовольняє системі обмежень (1.2), (1.3), умовам неотрицательности (1.4) і забезпечує мінімум цільової функції (1.1).
У розглянутій моделі транспортної завдання передбачається, що сумарні запаси постачальників рівні сумарним запитам споживачів, тобто
.
Така задача називається задачею з правильним балансом, а її модель-закритою. Якщо ж ця нерівність не виконується, то задача називається задачею з неправильним балансом, а її модель-відкритою.
Для того щоб транспортна задача лінійного програмування мала рішення, необхідно і достатньо, щоб сумарні запаси постачальників дорівнювали сумарним запитам споживачів, тобто завдання має бути з правильним балансом.
Приклад 1:
Скласти математичну модель транспортної задачі перевезення вантажу з двох складів у 3 магазини:
Таблиця 2


50
70
80
90
9
5
3
110
4
6
8
Рішення. Введемо змінні завдання (матрицю перевезень)

Запишемо матрицю вартостей
.
Цільова функція задачі дорівнює сумі добутків всіх відповідних елементів матриць С і Х:

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

Це означає, що запаси постачальників вивозяться повністю.
Суми перевезень, що стоять у кожному стовпці матриці Ч, повинні бути рівні запитам відповідних споживачів:

Це означає, що запити споживачів задовольняються повністю.
Необхідно також враховувати, що перевезення не можуть бути негативними:
i = 1,2, ..., m; j = 1,1, ..., n.
Відповідь: математична модель задачі формулюється наступним чином: знайти змінні завдання, щоб забезпечити мінімум функції

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

та умовам неотрицательности
i = 1,2, ..., mj = 1,2, ..., n.

1.2 АЛГОРИТМ РІШЕННЯ ТРАНСПОРТНОЇ ЗАВДАННЯ
1.2.1 Збалансованість ТРАНСПОРТНОЇ ЗАВДАННЯ
Транспортна задача є збалансованою, якщо сумарні запаси постачальників рівні сумарним запитам споживачів, тобто
.
Якщо транспортна задача не збалансована, то виникають особливо в її вирішенні.
Особливості вирішення транспортних завдань з неправильним балансом:
1.Якщо сумарні запаси постачальників перевершують сумарні запити споживачів, тобто

то необхідно ввести фіктивного (n +1)-го споживача з запитами рівними різниці сумарних запасів постачальників і запитів споживачів, і нульовими вартостями перевезень одиниць вантажу
2. Якщо сумарні запити споживачів перевершують сумарні запаси постачальників, тобто

то необхідно ввести фіктивного (m +1)-го постачальника з запасами рівні різниці сумарних запитів споживачів і запасів постачальників, і нульовими вартостями перевезень одиниць вантажу
3. При складанні початкового опорного рішення в останню чергу слід розподіляти запаси фіктивного постачальника і задовольняти запити фіктивного споживача, незважаючи на те, що їм відповідає найменша вартість перевезень, що дорівнює нулю.
1.2.2 ОПОРНО РІШЕННЯ ТРАНСПОРТНОЇ ЗАВДАННЯ
Опорним вирішенням транспортної задачі називається будь-яке допустиме рішення, для якого вектори умов, відповідні позитивним координатами, лінійно незалежні.
З огляду на те, що ранг системи векторів умов транспортної задачі дорівнює N = m + n-1, опорне рішення не може мати відмінних від нуля координат більше, ніж N.
Для перевірки лінійної незалежності векторів умов, відповідних координатах допустимого рішення, використовують цикли.
Циклом називається така послідовність клітин таблиці транспортної задачі в якій дві і лише сусідні клітини розташовані в одному рядку або стовпці, причому перша і остання також знаходяться в одному рядку або стовпці.
Система векторів умов транспортної задачі лінійно незалежна тоді і тільки тоді, коли з відповідних їм клітин таблиці не можна утворити жодного циклу. Отже, допустиме рішення транспортної задачі , I = 1,2, ..., m; j = 1,2, ..., n є опорним тільки в тому випадку, коли з зайнятих ним клітин таблиці не можна утворити жодного циклу.
Метод викреслювання. Для перевірки можливості утворення циклу використовується так званий метод викреслювання, який полягає в наступному.
Якщо в рядку або стовпці таблиці одна зайнята клітина, то вона не може входити до будь-якої цикл, оскільки цикл має дві і тільки дві клітини в кожному стовпці. Отже, можна викреслити всі рядки таблиці, що містять по одній зайнятої клітці, потім викреслити всі стовпці, що містять по одній зайнятої клітці, далі повернутися до рядків і продовжити викреслення рядків і стовпців. Якщо в результаті викреслювання всі рядки і стовпці будуть викреслені, значить, із зайнятих клітин таблиці не можна виділити частину, що утворить цикл, і система відповідних векторів умов є лінійно незалежною, а рішення опорним. Якщо ж після викреслювань залишиться частина клітин, то ці клітини утворюють цикл, система відповідних векторів умов лінійно залежна, а рішення не є опорним.
Метод мінімальної вартості. Даний метод дозволяє побудувати опорне рішення, яке досить близько до оптимального, оскільки використовує матрицю вартостей транспортної задачі , I = 1,2, ..., m; j = 1,2 ..., n. Даний метод складається з низки однотипних кроків, на кожному з яких заповнюється тільки одна клітина таблиці, відповідна мінімальної вартості , І виключається з розгляду тільки один рядок (постачальник) або один стовпець (споживач). Чергову клітку, відповідну , Заповнюють також. Постачальник виключається з розгляду, якщо його запаси закінчуються. Споживач виключається з розгляду, якщо його запити задоволені повністю. На кожному кроці виключається або один постачальник, або один споживач. При цьому якщо постачальник не виключений, але його запаси дорівнюють нулю, то на тому кроці, коли від нього вимагається поставити вантаж, у відповідну клітину таблиці заноситься базисний нуль і лише потім постачальник виключається з розгляду. Аналогічно поступають зі споживачем.
Приклад 2:
Використовуючи метод мінімальної вартості, побудувати початкову опорне рішення транспортної задачі, доставки ліків з трьох складів в чотири аптеки.
Таблиця 3


80
120
160
120
120
1
3
4
2
160
4
5
8
3
200
2
3
6
7
Рішення. Запишемо окремо матрицю вартостей для того, щоб зручніше було вибирати вартості, викреслювати рядки і стовпці:

1 4 6 3
серед елементів матриці вартостей вибираємо найменшу вартість . Це вартість перевезення вантажу від першого постачальника перший споживачеві. У відповідну клітину (1,1) записуємо максимально можливу перевезення (Табл 4). Запаси першого постачальника зменшуємо на 80, . Виключаємо з розгляду першого споживача, так як його запити задоволені. У матриці З викреслюємо перший стовпець.
Таблиця 4


80
120
160
120
120
1
80
3
4
2
40
160
4
5
8
80
3
80
200
2
3
120
6
80
7
У решти матриці С найменшою є вартість , Максимально можлива перевезення, яку можна здійснити від першого постачальника до четвертого споживачеві, дорівнює . У відповідну льотку таблиці записуємо перевезення . Запаси першого постачальника вичерпані, виключаємо його з розгляду. У матриці З викреслюємо перший рядок. Запити четвертого споживача зменшуємо на 40
У частині матриці С мінімальна вартість . Заповнюємо одну з двох клітин таблиці (2,4) або (3,2). Нехай у клітку (2,4) запишемо . Запити четвертого споживача задоволені повністю, виключаємо його з розгляду, викреслюємо четвертий стовпець у матриці С. Зменшуємо запаси другого постачальника
У частині матриці С мінімальна вартість . Запишемо в клітину таблиці (3,2) перевезення Виключаємо з розгляду другого споживача, а з матриці С другий стовпчик. Обчислюємо
У частині матриці С найменша вартість Запишемо в клітину таблиці (3,3) перевезення Виключаємо з розгляду третього постачальника, а з матриці З третій рядок. Визначаємо .
У матриці З залишився єдиний елемент . Записуємо в клітину таблиці (2,3) перевезення .
Перевіряємо правильність побудови опорного рішення. Число зайнятих клітин таблиці дорівнює N = m + n-1 = 3 +4-1 = 6. Застосовуючи метод викреслювання, перевіряємо лінійну незалежність векторів умов, відповідних позитивним координатами рішення. Порядок викреслювання показаний на матриці Х:

1 2 5 6
Рішення є «викреслюємо» і, отже, опорним.
Перехід від опорного рішення до іншого. У транспортній задачі перехід від оного опорного рішення до іншого здійснюється за допомогою циклу. Для деякої вільної клітини таблиці будується цикл, у якому частина клітин, зайнятих опорним рішенням. З цього циклу перерозподіляються обсяги перевезень (здійснюється зрушення по циклу). Перевезення «завантажується» в обрану вільну клітину і звільняється одна з зайнятих клітин, виходить нове опорне рішення.
Якщо таблиця транспортної задачі містить опорне рішення, то для будь-якої вільної клітини таблиці існує єдиний цикл, у якому цю клітку і частина клітин, зайнятих опорним рішенням.
Для зручності обчислень вершини циклів нумерують і відзначають непарні знаком «+», а парні знаком «-». Такий цикл називається зазначеним.

Зрушенням по циклу на величину називається збільшення обсягів перевезень у всіх непарних клітинах циклу, позначених знаком «+», та зменшення обсягів перевезень на ту ж величину у всіх не парних клітинах, позначених знаком «-».
1.2.3 МЕТОД ПОТЕНЦІАЛІВ
Широко розповсюдженим методом вирішення транспортних задач є метод потенціалів.
Якщо допустиме рішення , I = 1,2, ..., m; j = 1,2, ... n транспортної задачі є оптимальним, то існують потенціали (числа) постачальників i = 1,2, ..., m і споживачів j = 1,2, ..., n, що задовольняє наступним чином:

Група рівностей (2.1) використовується як система рівнянь для знаходження потенціалів. Дана система рівнянь має m + n невідомих i = 1,2, ..., m і j = 1,2, ..., n. Число рівнянь системи, як і число відмінних від нуля координат невиродженого опорного рішення, так само m + n-1. Так як число невідомих системи на одиницю більше числа рівнянь, то однією з них можна задати значення довільно, а решта знайти з системи.
Група нерівностей (2.2) використовується для перевірки оптимальності опорного рішення. Ці нерівності зручніше представити в наступному вигляді:
(2.3)
Числа називаються оцінками для вільних клітин таблиці (векторів умов) транспортної задачі.
Опорне рішення є оптимальним, якщо для всіх векторів умов (клітин таблиці) оцінки недодатні.
Оцінки для вільних клітин транспортної таблиці використовуються при поліпшенні опорного рішення. Для цього знаходять клітку (l, k) таблиці, відповідну . Якщо , То рішення оптимальне. Якщо ж , То для відповідної клітини (l, k) будують цикл і покращую рішення, перерозподіляють вантаж
з цього циклу.
Алгоритм вирішення транспортних задач методом потенціалів:
1. Перевірити виконання необхідного і достатнього умови розв'язності задачі. Якщо завдання має неправильний баланс, то вводиться фіктивний постачальник або споживач з відсутніми запасами або запитами і нульовими вартостями перевезень.
2. Побудувати початкове опорне рішення (методом мінімальної вартості або яким-небудь іншим методом), перевірити правильність його побудови за кількістю зайнятих клітин (їх має бути m + n-1) і переконатися в лінійній незалежності векторів умов (використовується метод викреслювання).
3. Побудувати систему потенціалів, відповідних опорному рішенням. Для цього вирішують систему рівнянь:

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

якщо відомий потенціал , І

якщо відомий потенціал
4. Перевірити виконання умови оптимальності для вільних клітин таблиці. Для цього обчислюють оцінки для всіх вільних клітин за формулами

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

Будують цикл, що включає до свого складу дану клітину і частина клітин, зайнятих опорним рішенням. У клітинах циклу розставляють по черзі знаки «+» і «-», починаючи з «+» в клітині з найбільшою позитивною оцінкою. Здійснюють зрушення (перерозподіл вантажу) по циклу на величину . Клітка зі знаком «-», в якій досягається залишається порожньою. Якщо мінімум досягається в декількох клітинах, то одна з них залишається порожньою, а в інших проставляють базисні нулі, щоб число зайнятих клітин залишалась рівною .
Далі перейти до пункту 3 цього алгоритму.
1.2.4 МЕТОД ПІВНІЧНО-ЗАХІДНОГО УГЛА
Відповідно до даного методу запаси чергового постачальника використовуються для забезпечення запитів чергових споживачів до тих пір, поки не будуть вичерпані повністю, після чого використовується запаси наступного за номером постачальника.
Заповнення таблиці транспортної задачі починається з лівого верхнього кута і складається з ряду однотипних кроків. На кожному кроці, виходячи із запасів чергового постачальника і запитів чергового споживача, заповнюється тільки одна клітина і відповідно виключається з розгляду один постачальник або споживач. При цьому нульові перевезення прийнято заносити в таблицю тільки в тому випадку, коли вони потрапляють у клітину (i, j), що підлягає заповненню, тобто в таблицю заносяться тільки базисні нулі , Інші клітини з нульовими перевезеннями залишаються порожніми.
Щоб уникнути помилок після побудови початкового опорного рішення необхідно перевірити, що число зайнятих клітин одно m + n-1 і вектори умов, що відповідають цим клітинам, лінійно незалежні.
Необхідно мати на увазі, що метод північно-західного кута не враховує вартість перевезень, тому, опорне рішення, побудоване за цим методом, може бути далеким від оптимального.
Приклад 3:
Скласти опорне рішення методом північно-західного кута транспортної задачі, у якій 5 постачальників та 5 споживачів. дані записані в таблиці 6
Таблиця 6

В1
50
В2
40
В3
30
В4
20
В5
10
А1
10
А2
20
А3
30
А4
40
А5
50
Рішення:
Розподіляємо запаси першого постачальника. Так як його запаси менше запитів перший споживача , То в клітку (1,1) записуємо перевезення і виключаємо з розгляду першого постачальника. Визначаємо залишилися незадоволеними запити першим споживача .
Розподіляємо запаси другого постачальника. Так як його запаси , Менше запитів першого споживача , То записуємо в клітку (2,1) перевезення і виключаємо з розгляду другого постачальника. Визначаємо залишилися незадоволеними запити першим споживача .
Розподіляємо запаси третього постачальника . Так як його запаси більше запитів перший споживача , То записуємо в клітку (3,1) перевезення і виключаємо з розгляду першого споживача. Визначаємо залишилися незадоволеними запити третіх постачальника .
Розподіляємо запаси третього постачальника . Так як його запаси менше запитів другий споживача , То в клітку (3,2) записуємо перевезення і виключаємо з розгляду третіх постачальника. Визначаємо залишилися незадоволеними запити другого споживача .
Розподіляємо запаси четвертого постачальника . Так як його запаси більше запитів другий споживача , То записуємо в клітку (4,2) перевезення і виключаємо з розгляду другого споживача. Визначаємо залишилися незадоволеними запити четвертого постачальника .
Розподіляємо запаси четвертого постачальника . Так як його запаси менше запитів третій споживача , То в клітку (4,3) записуємо перевезення і виключаємо з розгляду четвертого постачальника. Визначаємо залишилися незадоволеними запити третіх споживача .
Розподіляємо запаси п'ятого постачальника. Так як його запаси більше запитів третій споживача , То в клітку (5,3) записуємо перевезення і виключаємо з розгляду третіх споживача. Визначаємо залишилися незадоволеними запаси п'ятого постачальника .
Розподіляємо запаси п'ятого постачальника. Так як його запаси більше запитів четвертого споживача , То в клітку (5,4) записуємо перевезення і виключаємо з розгляду четвертого споживача. Визначаємо залишилися незадоволеними запаси п'ятого постачальника .
Розподіляємо запаси п'ятого постачальника. Так як його запаси рівні запитам п'ятого споживача , То в клітку (5,5) записуємо перевезення і виключаємо з розгляду п'ятого постачальника і п'ятого споживача.
З огляду на те, що завдання з правильним балансом, запаси всіх постачальників вичерпані і запити всіх споживачів задоволені.
Результати побудови опорного рішення наведені в таблиці 7.

В1
50
В2
40
В3
30
В4
20
В5
10
А1
10
10
-
-
-
-
А2
20
20
-
-
-
-
А3
30
20
10
-
-
-
А4
40
-
30
10
-
-
А5
50
-
-
20
20
10

1.3 БЛОК-СХЕМА (АЛГОРИТМ РІШЕННЯ)
1
початок
2
Введення
даних
3
Пров. введення
6
Запаси менше потроеб
4
Підсумовування потреб споживачів
5
Підсумовування запасів постачальників
7
Додам. Уявного постачальника
8
Додам. Уявного споживача


немає немає

та

15
кінець
13
цикл
14
побудова нового рішення
9
Побудова початкового плану
10
Знаходження оцінок вільних клітин
11
Оцінки більше 0
12
Оптимальне рішення


Метод
північно-
- Західного
кута
метод
потенціалів

2. ФОРМИ ВХІДНИЙ ІНФОРМАЦІЇ
Вхідні дані вводяться з клавіатури
· Запаси i-го постачальника
· Запити j-го споживача
У даному прикладі
· Запаси постачальників (10; 20; 30; 40; 50)
· Запити споживачів (50: 40; 30; 20; 10)

3. ФОРМИ ВИХІДНИЙ ІНФОРМАЦІЇ
Інформація виводиться на екран у вигляді таблиці з введеними даними і допустимий початковий базис

В1
50
В2
40
В3
30
В4
20
В5
10
А1
10
10
-
-
-
-
А2
20
20
-
-
-
-
А3
30
20
10
-
-
-
А4
40
-
30
10
-
-
А5
50
-
-
20
20
10

4. ІНСТРУКЦІЯ ДЛЯ КОРИСТУВАЧА
Загальні відомості:
Програма робить обчислення припустимого початкового базису
Завдання є збалансованою. Пошук початкового базису відбувається методом «північно-західного кута»
Управління:
Дані вводяться з клавіатури:
Користувач вводить запаси i-го споживача. Після натискання клавіші «0» користувач вводить запити j-го постачальника. Далі на екрані після натискання клавіші «Enter» з'являється таблиця з вводяться даними і початковий базис.

5. ІНСТРУКЦІЯ ДЛЯ ПРОГРАМІСТА
Дана програма реалізується за допомогою процедурної мови Turbo Pascal 7.0, використовується текстовий режим.
5.1 НЕОБХІДНІ ІНФОРМАЦІЙНО-ОБЧИСЛЮВАЛЬНІ ЗАСОБИ:
1) технічне забезпечення: IBM PC \ XT сумісні машини
а) оперативна пам'ять - не менше 8Мб
б) вільне місце на жорсткому диску - не менше 60Кб
в) центральний процесор - від Intel 8088 до сімейства Pentium або сумісних з ним
2) інформаційні засоби для нормального функціонування програми досить мати інформаційну систему MS DOS
5.2 ТИПИ ЗМІННИХ, ВИКОРИСТАНИХ У ПРОГРАМІ:
const n = 20 (рядки)
m = 20 (стовпці)
a: array [1 .. n] of integer; {масив запасів}
b: array [1 .. m] of integer; {масив потреб}
a1: array [1 .. n] of integer; {допоміжний масив запасів}
b1: array [1 .. m] of integer; {допоміжний масив потреб}
c: array [1 .. n, 1 .. m] of integer; {основний масив в який проводиться запис базисного рішення}
i, j, k, x, y, s1, s2: integer;

5.3 ПРОЦЕДУРИ
procedure vvod_klav; (введення даних з клавіатури)
begin
i: = 1;
k: = 0;
s1: = 0;
while (k = 0) and (i <n) do
begin
write ('введіть запaси', i, '-того постачальника:');
readln (a [i]);
if a [i] = 0 then
begin
k: = 1;
i: = i-1;
end
else
begin
a1 [i]: = a [i];
s1: = s1 + a1 [i];
i: = i +1;
end;
end;
j: = 1;
k: = 0;
s2: = 0;
textcolor (5);
while (k = 0) and (j <m) do
begin
write ('введіть запит', j, '-того споживача:');
readln (b [j]);
if b [j] = 0 then
begin
k: = 1;
j: = j-1;
end
else
begin
b1 [j]: = b [j];
s2: = s2 + b1 [j];
j: = j +1;
end;
end;
textcolor (yellow);
k: = 0;
if s1 <s2 then
begin
writeln ('помилка вводу, перевірте баланс');
readln;
halt;
end;
if (s2 <s1) and (k = 0) then
begin
writeln ('помилка вводу, перевірте баланс');
readln;
halt; end;
x: = i;
y: = j;
end;

ВИСНОВОК
Мені була поставлена ​​задача скласти програму для розрахунку початкового базису збалансованої транспортної задачі, де сумарні запаси постачальників рівні сумарним запитам споживачів.
Програма реалізована на мові програмування Паскаль.
Всі дані, що вводяться і початковий базис виводяться у вигляді таблиці.
У програмі зручний і зрозумілий інтерфейс. Для введення даних використовується клавіатура. Дані, виведені програмою, відповідають тим, що отримані при розрахунках без використання комп'ютера. Таким чином, поставлена ​​задача була виконана.

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
1 Загальний курс вищої математики для економістів. Підручник / за ред В.І. Єрмакова .- М.: інфа - М. - 656 с. - (Серія «вищу освіту»).
2 Збірник задач і вправ з вищої математики: математичне програмування: підручник посібник / О.В. Кузнєцов, В.А. Сакович, Н.І. Холод та ін; МН.: Виш. ік., 2002. - 447с.: Іл.
3 Т.Л. Партикіна, І.І. Попов Математичні методи: підручник. - М.: ФОРУМ: інфа-М, 2005. - 464 с.: Іл - (професійна освіта)
4. І.Г. Семакін Основи програмування: підручник для середовищ. проф. Освіти / І.Г. Семакін, А. П. Шестаков. - 2-е вид., Стер, - М.: Видавничий центр «Академія», 2003.-432 с.
5 Федосєєв В.В. та ін Економіко-математичні методи і прикладні моделі: навчальний посібник для ВУЗів. - М.: Юніті, 2002.
6 Коршунов Ю.М. математичні основи кібернетики: навчальний посібник для ВУЗів. - М.: Вища школа, 1987.

ДОДАТОК А
Лістинг програми
program sev_zap;
uses crt; {підключення модуля "crt"}
const n = 5; {кількість рядків}
m = 5; {кількість стовпців}
var a: array [1 .. n] of integer; {масив запасів}
b: array [1 .. m] of integer; {масив потреб}
a1: array [1 .. n] of integer; {допоміжний масив запасів}
b1: array [1 .. m] of integer; {допоміжний масив потреб}
c: array [1 .. n, 1 .. m] of integer; {основний масив в який проводиться запис базисного рішення}
i, j, k, x, y, s1, s2: integer;
{Введення з клавіатури}
procedure vvod_klav;
begin
i: = 1;
k: = 0;
s1: = 0;
while (k = 0) and (i <n) do
begin
write ('введіть запaси', i, '-того постачальника:');
readln (a [i]);
if a [i] = 0 then
begin
k: = 1;
i: = i-1;
end
else
begin
a1 [i]: = a [i];
s1: = s1 + a1 [i];
i: = i +1;
end;
end;
j: = 1;
k: = 0;
s2: = 0;
textcolor (5);
while (k = 0) and (j <m) do
begin
write ('введіть запит', j, '-того споживача:');
readln (b [j]);
if b [j] = 0 then
begin
k: = 1;
j: = j-1;
end
else
begin
b1 [j]: = b [j];
s2: = s2 + b1 [j];
j: = j +1;
end;
end;
textcolor (yellow);
k: = 0;
if s1 <s2 then
begin
writeln ('помилка вводу, перевірте баланс');
readln;
halt;
end;
if (s2 <s1) and (k = 0) then
begin
writeln ('помилка вводу, перевірте баланс');
readln;
halt;
end;
x: = i;
y: = j;
end;
begin
textcolor (white);
clrscr; {очищення екрана}
writeln ('Побудова початкового базису в збалансованої транспортної задачі методом північно-західного кута');
writeln;
writeln ('Програму склав: Руднєв Єгор Миколайович');
writeln;
vvod_klav; {процедура введення з клавіатури}
repeat
k: = 0;
if (b [j]-a [i] <0) then
begin
c [i, j]: = b [j];
a [i]: = a [i]-b [j];
b [j]: = 0;
j: = j-1;
k: = 1;
end;
if (b [j]-a [i]> 0) and (k = 0) then
begin
c [i, j]: = a [i];
b [j]: = b [j]-a [i];
a [i]: = 0;
i: = i-1;
k: = 1;
end;
if (b [j]-a [i] = 0) and (k = 0) then
begin
c [i, j]: = a [i];
a [i]: = 0;
b [j]: = 0;
i: = i-1;
j: = j-1;
end;
if (i = 0) or (j = 0) then break;
until false;
{Висновок на екран базисного рішення}
clrscr;
textcolor (white);
for i: = 1 to x do
begin
for j: = 1 to y do
if j = y then write (c [i, j]: 6, '│', a1 [i])
else
write (c [i, j]: 6);
writeln;
end;
write ('');
for i: = 1 to y * 6-4 do
write (# 196);
writeln ('┘');
for j: = 1 to y do
write (b1 [j]: 6);
readln;
end.
Додати в блог або на сайт

Цей текст може містити помилки.

Економіко-математичне моделювання | Курсова
148.7кб. | скачати


Схожі роботи:
Рішення економічних задач
Рішення задач на графах
Методи рішення текстових задач
Рішення задач лінійного програмування 2
Рішення задач на уроках хімії
Рішення задач за допомогою ЕОМ
Рішення задач по податковому забезпечення
Рішення задач з курсу статистики
Рішення задач дослідження операцій
© Усі права захищені
написати до нас
Рейтинг@Mail.ru