Розв’язання транспортної задачі, як складова підготовки бакалаврів з економіки та підприємництва



Скачати 126.42 Kb.
Дата конвертації13.03.2017
Розмір126.42 Kb.
УДК 004.67

Овчарук І.В., Овчарук В.О.

РОЗВ’ЯЗАННЯ ТРАНСПОРТНОЇ ЗАДАЧІ, ЯК СКЛАДОВА ПІДГОТОВКИ БАКАЛАВРІВ З ЕКОНОМІКИ ТА ПІДПРИЄМНИЦТВА

Наведено основні теоретичні відомості, приклад розв’язання транспортної задачі класичними методами та у програмному середовищі Mathcad. Дана розробка сприятиме більш якісній підготовці висококваліфікованих спеціалістів в економіці та підприємництві.

Ключові слова: лінійне програмування, MathCad, економічні розрахунки.

Постановка проблеми. Транспортна задача посідає важливе місце в лінійному програмуванні і широко застосовується на транспорті і в промисловості. Її також можна застосовувати при виникненні деяких практичних ситуацій, пов’язаних з управлінням запасами, складанням змінних графіків, призначенням службовців на робочі місця та ін. Особливе значення вона має в організації раціональних поставок важливих вантажів, а також в оптимальному плануванні вантажопотоків і роботі різних видів транспорту. Поява в останні роки засобів інженерних та наукових розрахунків дає можливість фахівцю розв’язувати поставлені задачі без досконалого знання мов програмування, із застосуванням формату звичайного математичного запису. Проте виникає необхідність досконалого володіння таким програмним продуктом, як системи автоматизованих інженерних та економічних розрахунків Excel та MathCad.

Аналіз попередніх досліджень. Окремі аспекти розв’язування задач лінійного програмування (в тому числі і транспортної задачі) засобами MS Excel в інженерних розрахунках розкрито в працях [1, 2, 3]. Однак недостатньо проробленими залишаються методики розв’язання задач оптимізації та лінійного програмування з використанням сучасних комп’ютерних технологій, а саме з використанням математичного процесора MathCad. В Україні над цією проблемою працюють науковці М.А. Мартиненко, Т.О. Кривець, Я.Б. Петрівський та ін.

Цілі статті полягають у запропонуванні методики розв’язання транспортної задачі лінійного програмування, як найбільш популярної в економічних обчисленнях та важливої складової при підготовці бакалаврів у галузі знань «Економіка і підприємництво», використовуючи математичний процесор MathCad.

Виклад основного матеріалу. У пунктах А1, А2 … Аm міститься однорідна сировина або товар, що потрібно перевезти в пункти споживання В1, В2 … Вn. Запаси пунктів постачання і потреби пунктів споживання є відомі задані величини, що відповідно дорівнюють: A = (a1, a2am), B = (b1, b2bn). Вартість перевезень із кожного пункту постачання у кожний пункт споживання характеризується матрицею

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

Складемо математичну модель задачі. Позначимо xij – кількість одиниць сировини або товару, що планується перевезти з і-го пункту постачання Аі у j-ий пункт споживання Вj. Тоді отримаємо наступну задачу лінійного програмування

(1)

(2)

(3)

Означення 1. Планом транспортної задачі (1) – (3) називається набір величин x = xij (i = 1…n, j = 1…n) який задовольняє умови (2) – (3).

Означення 2. План x* =( xij*) (i = 1…n, j = 1…n), який задовольняє умову (1) називається оптимальним планом транспортної задачі (1) – (3).

Теорема 1. Для розв’язності транспортної задачі необхідно і достатньо, щоб виконувалась умова балансу



Алгоритм методу потенціалів ґрунтується на справедливості наступної теореми:

Теорема 2. Якщо для деякого опорного плану = (xij), (i = 1…n, j = 1…n) транспортної задачі існують такі числа , , що

для xij > 0 i



для xij = 0, то = (xij) є оптимальний план транспортної задачі.

Означення 3. Числа і, і називають потенціалами пунктів постачання і споживання відповідно.

Зауваження. Якщо для транспортної задачі (1) – (3) не виконуються умови балансу, то маємо відкриту модель транспортної задачі. В даному випадку потрібно ввести додатковий, фіктивний пункт постачання (споживання) із запасами (потребами) у такій кількості, щоб умови балансу виконувались. Вартість перевезень із такого пункту споживання (постачання) дорівнює нулю. Після знаходження розв’язку із оптимального плану відкидають штучні компоненти.

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


Матриця вартості

Постачальники

Споживачі
















Так як , то задача є збалансованою.

Таблиця 1

Знаходимо допустимий опорний план методом північно-західного кута

Постача-

льники


Споживачі

Запаси

B1

B2

B3

B4

B5




А1

2

8

4

8

3

120 90 0

30

90

 

 

 

А2

3

2

5

2

6

30 0

 

 

30

 

 

А3

6

5

8

7

4

40 0

 

 

40

 

 

А4

3

4

4

2

1

60 50 30 0

 

 

10

20

30

Попит на ресурси

30 0

90 0

80 50 10 0

20 0

30

250

25

Отримали опорний план. Цьому плану відповідають витрати на перевезення:



Отриманий опорний план не є оптимальним. Для оптимізації скористаємось методом потенціалів. Для визначення потенціалів постачальників і споживачів складемо систему рівнянь для заповнення клітин табл. 2.



Ця невизначена система містить 7 рівнянь 9 невідомих, тому для її розв’язку одному з потенціалів надамо довільного значення. Значення потенціалів запишемо в табл.2.



Таблиця 2

Постача-

льники


Споживачі

Запаси

ui

B1

B2

B3

B4

B5

А1

2

8

4

8

3

0

0

30

90 160

0 30

-6

-2

А2

3

2

5

2

6

0

1

0

7 30

30 10

1

-4

А3

6

5

8

7

4

0

4

0

7

40

-1

1

А4

3

4

4

2

1

0

0

-1

4

10

20

30

Потреби

0

0

0

0

0

 




 




vj

2

8

4

2

1







Визначимо оцінки вільних клітин .





– обираємо (2,2),

Змінюється завантаження клітин.



Таблиця 3

 

B1

B2

B3

B4

B5

А1

2

8

4

8

3

30

60

30




 

А2

3

2

5

2

6

 

30

0

 

 

А3

6

5

8

7

4

 

 

40

 

 

А4

3

4

4

2

1

 

 

10

20

30





Пропустимо 2 ітерації. Після 4-ї ітерації отримаємо наступний план



.

Знайдемо розв’язок транспортної задачі в програмному середовищі Mathcad.



















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

ЛІТЕРАТУРА

  1. А.І. Українець, А.М. Гуржій, В.В. Самсонов та ін. Задачі лінійного та нелінійного програмування. Навчальний посібник – К.: НУХТ, 2007. – 158 с.

  2. Математичне програмування: Навч. посібник/ М.А. Мартиненко, О.М. Нещадим, В.М. Сафонов. – К.: «Четверта хвиля», 2002. – 220 с.

  3. Математичне програмування. Лабораторний практикум в середовищі Mathcad. Методичні вказівки до виконання лабораторних робіт для студентів спеціальності 6.050102 «Економічна кібернетика» / Я.Б. Петрівський. – Рівне: РДГУ, 2003. – 80 с.

Овчарук И.В., Овчарук В.А.

РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ, КАК СОСТАВЛЯЮЩАЯ ПОДГОТОВКИ БАКАЛАВРОВ ПО ЭКОНОМИКЕ И ПРЕДПРИНИМАТЕЛЬСТВУ

Приведены основные теоретические сведения, пример решения транспортной задачи классическими методами и в программной среде MathCad. Данная разработка будет содействовать более качественной подготовке высококвалифицированных специалистов в экономике и предпринимательстве.

Ключевые слова: линейное программирование, MathCad, экономические расчеты.

Ovcharuk I., Ovcharuk V.

TRANSPORT PROBLEM SOLVING AS A COMPONENT OF TRAINING BachelorS IN Economics and Business

The article provides basic theoretical information, as well as the sample of transportation problem solution by using classical methods and in the software environment MathCad. This design is to contribute to better quality of training in economics and business.

Keywords: linear programming, MathCAD, economic calculations.

Поділіться з Вашими друзьями:


База даних захищена авторським правом ©divovo.in.ua 2017
звернутися до адміністрації

войти | регистрация
    Головна сторінка


загрузить материал