https://doi.org/10.53656/math2023-5-7-alg

Резюме. В настоящата статия е представено приложно решаване на транспортна задача с помощта на софтуер MS Excel (solver). Едно от предимството на алгоритмичните задачи е, че може да се реши чрез подходящ софтуер, който значително разширява практическото им приложение, свързано с обработката на данни и изпълнение на многобройни изчислителни операции.

Ключови думи: транспортна задача; MS Excel Solver

1. Увод

Много математически модели на основни икономически задачи (Eiselt et al. 2002), (Winston 2002), (Tahan 2017), произлизащи от производството (Anderson et al. 2012), (Dvorkin et al. 2023), са свързани с оптимизационни методи като симплекс метод и транспортна задача (Marinov et al. 2016). Последните са известни още като количествени методи в икономиката (Ivanov & Lomev 2008), (Slavkova & Tzenova 2011), (Anderson et al. 2012), но изследването на математическата им основа допринася за изясняване на тяхното значение за практиката (Ivanov 2020), (Faizullin et al. 2022). Голяма част от икономическите задачи могат да бъдат формулирани като линейни математически модели (Ivanov 2004) и е наложително владеенето на съответни математически умения за съставяне на подходящи математически модели, както и знания, свързани с методите за тяхното решаване (Ivanov et al. 1989), (Luenberger & Ye 2008), (Ivanov & Tanov 2018). Най-ефективното от множеството на всички възможни решения сe нарича оптимално.

Между задачите на линейното оптимиране (разпространен е още терминът линейно програмиране) могат да се отделят някои класове задачи, които имат определени структурни особености. За тези задачи общите методи на линейното оптимиране могат съществено да се опростят или да се построят методи, по-ефективни от традиционния за тях симплекс-метод.

Задачата, която разглеждаме тук, е била формулирана през 1939 г. от няколко автори и е известна класическа транспортна задача (Slavkova & Tzenova 2011). В предговора към (Ivanov & Kaltinska 1973) проф. Бл. Сендов отбелязва, че „теорията е сравнително много млада“, но „важността на методите на линейното оптимиране за решаване на производствено-икономически задачи изисква тази теория да се овладее масово“.

Въпреки името си, произхождащо от първоначално решаваната задача, методът, използван за решаване на транспортната задача, се прилага при решаване на разнообразни типове задачи, свързани с определяне, обработка и изразходване на ресурси, управление на запаси, съставяне на работни графици и смени, на маршрути не само в транспорта, а например и в компютърните мрежи. За подготовката на настоящия ръкопис са използвани (Ivanova et al. 2011), (Marinov et al. 2016), (Ivanova et al. 2018) и (Kuneva et al. 2021).

2. Формулировка

Транспортната задача (ТЗ) се формулира по следния начин. В пунктовете \(A_{1}, A_{2}, \ldots, A_{m}\) (наречени производители) се произвежда продукция в количества \(a_{1}, a_{2}, \ldots, a_{m}\), съответно. Пунктовете \(B_{1}, B_{2}, \ldots, B_{n}\) (наречени потребители) се нуждаят от същата продукция в количества \(b_{1}, b_{2}, \ldots, b_{n}\) съответно. Между производството и потреблението има баланс, т.е. \(\sum_{i=1}^{m} a_{i}=\sum_{j=1}^{n} b_{j}\). Транспортните разходи за превоза на единица продукция от пункта \(A_{i}, i=1,2, \ldots, m\), до пункта \(B_{j}, j=1,2, \ldots, n\), са \(c_{i j}\). Да се състави план за снабдяването на пунктовете \(B_{1}, B_{2}, \ldots, B_{n}\) с продукция от пунктовете \(A_{1}, A_{2}, \ldots, A_{m}\), така че потребностите на потребителите да бъдат задоволени, стоката на производителите да бъде пласирана и общите транспортни разходи да бъдат минимални.

Тази формулировка на транспортната задача е предложена за първи път от Л. В. Канторович през 1939 г.

Обикновено един екземпляр на транспортната задача се задава с така наречената транспортна таблица (табл. 1), която е достатъчна за дефинирането на задачата.

Матрицата \(C=\left\|c_{i j}\right\|, i=1,2, \ldots, m ; j=1,2, \ldots, n\), се нарича матрица на транспорт-ните разходи.

Да съставим математическия модел на задачата. За целта с \(x_{i j}\) да означим количеството продукция, изпратена от производителя \(A_{i}, i=1,2, \ldots, m\), до потребителя \(B_{j}, j=1,2, \ldots, n\).

Матрицата \(X=\left\|x_{i j}\right\|, i=1,2, \ldots, m ; j=1,2, \ldots, n\), се нарича матрица на превозите. Ако всеки елемент \(x_{i j}\) от тази матрица поставим в клетката \((i, j)\) на транспортната таблица, получаваме т.нар. разширена матрица на превозите.

Целевата функция, отразяваща общите транспортни разходи, е линейна и има вида:

\[ \begin{gathered} L(X)=c_{11} x_{11}+c_{12} x_{12}+\cdots+c_{1 n} x_{1 n}+ \\ +c_{21} x_{21}+c_{22} x_{22}+\cdots+c_{2 n} x_{2 n}+ \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ +c_{11} x_{11}+c_{12} x_{12}+\cdots+c_{1 n} x_{1 n} \end{gathered} \]

Ограничителните условия, наложени на променливите \(x_{i j}\), също са линейни уравнения.

1. Поради това, че продукцията на всеки производител трябва изцяло да се пласира, са в сила равенствата:

\[ \begin{gathered} x_{11}+x_{12}+\cdots+x_{1 n}=a_{1} \\ x_{21}+x_{22}+\cdots+x_{2 n}=a_{2} \\ \cdots \cdots \cdots \cdots \cdots \cdots \\ x_{m 1}+x_{m 2}+\cdots+x_{m n}=a_{m} \end{gathered} \]

2. Поради това че трябва да бъдат задоволени потребностите на всички потребители, трябва да е изпълнено:

\[ \begin{array}{r} x_{11}+x_{21}+\cdots+x_{m 1}=b_{1} \\ x_{12}+x_{22}+\cdots+x_{m 2}=b_{2} \\ \cdots \cdots \cdots \cdots \cdots \cdots \\ x_{1 n}+x_{2 n}+\cdots+x_{m n}=b_{n} \end{array} \]

Всички превозени количества продукция \(x_{i j}\) трябва да са неотрицателни, т.е. \(\quad x_{i j} \geq 0\). Аналогично, количествата \(a_{i}, i=1,2, \ldots, m\) и \(b_{j}, j=1,2, \ldots, n\), трябва да са положителни. Като имаме предвид, че целта е минимизиране на общите транспортни разходи, получаваме следния математически модел на ТЗ (записан в съкратен вид).

Да се намери минимумът на линейната функция \(L(X)=\sum_{i=1}^{m} \sum_{j=1}^{n} c_{i j} x_{i j}\) при следните ограничителни условия: \(\sum_{j=1}^{n} x_{i j}=a_{i}, i=\overline{1, m}, \sum_{i=1}^{m} x_{i j}=\) \(b_{j}, j=\overline{1, n}, x_{i j} \geq 0, i=\overline{1, m}, j=\overline{1, n}\), и при условия за съществуване на баланс между произведена и използвана продукция, т.е. \(\sum_{i=1}^{m} a_{i}=\sum_{j=1}^{n} b_{j}\).

Така формулираната транспортна задача с условието за баланс се нарича затворена транспортна задача.

3. Алгоритъм на решаване на транспортна задача с MS Excel Solver

MS Excel (използвана е версията MS Excel 2016) разполага с модул за решаване на оптимизационни задачи. Модулът се нарича Solver и може да бъде намерен в менюто Data („Данни“). Преди първото му използване модулът трябва да бъде активиран. Това става в следната последователност:

– стартираме MS Excel;

– от меню „Файл“ (File) избираме „Опции“ (Options);

– отваря се диалоговата кутия „Опции„ на Excel;

– от подменюто „Добавки“ (Add-in) намираме падащото меню „Управление“ (фиг. 1), от списъка с възможности избираме „Добавки“ на Excel и натискаме бутона „Почни“…;

– в отворилия се диалогов прозорец поставяме отметка в кутията „Добавка решател“ (Solver) и натискаме бутона ОK;

– затваряме диалоговата кутия с бутона OK.

По този начин вече разполагаме с програмата за решаване на оптимизационни задачи в MS Excel. Отваряме работен лист, в който да въведем данните за транспортната задача, на която търсим оптимално решение. За илюстрация на възможностите на MS Excel ще решим една транспортната задача от затворен тип.

А. Попълване на работния лист

На фиг. 2 е показан работен лист в електронна таблица, в който въвеждаме данните на транспортна задача.

1. Въвеждаме стойностите на транспортните разходи в клетките С3:F5, в клетките G3:G5 – константите от матрица \(A\left(A_{i}\right)\), а в клетки C6:F6 – константите от матрица \(B\left(B_{i}\right)\) на задачата.

2. Подготвяме празно копие на таблицата, както е показано на фигурата.

3. В клетка I8 въвеждаме формулата, по която се пресмята стойността на целевата функция, т.е. \(=\) SUMPRODUCT(C3:F5;C11:F13). Препоръчва се преди извикването на Solver текуща да е клетката с целевата функция – в случая клетка I8.

3. В клетка C14 на втората таблица въвеждаме формулата \(=\) SUM(C11:C13) и след щракване с мишката в нея се появява нула. След това разпространяваме формулата и в клетките D14:F14, където също се показват нулеви стойности (фиг. 3а). Аналогично въвеждаме формулата =SUM(C11:F11) в клетка G11 и я разпространяваме в клетките G12 и G13 (фиг. 3б).

Б. Решаване на задачата

След въвеждане на входните данни и изписване на формулите поставяме фокуса в клетка I8, където сме въвели формулата за изчисляване стойността на целевата функция от меню „Данни“ (Data) → Solver, с натискане на бутона Solver отваряме диалоговата кутия Solver Parameters. (фиг. 4). В текстовата кутия Set Objective автоматично се изписва адресът I8.

От радиобутоните To избираме съответния на модела критерий, който в разглежданата задача е Min. В текстовото поле By Changing Variable Cells въвеждаме клетките, в които се намират стойностите на променливите на задачата – в примера това са клетките C11:F13, по които се минимизира целевата функция.

В полето Subject to the Constraints с бутона Add се въвеждат ограниченията, с бутона Change се правят изменения, а с бутона Deleteсе изтриват съществуващи ограничения. При натискане на бутона Add се отваря диалоговата кутия за добавяне на ограничителни условия (фиг. 5).

Чрез диалога Add Constrain едно по едно се попълват ограниченията на задачата, като за всяко ограничение попълваме: клетките от лявата страна на ограничителното условие – в полето Cell Reference; вида на ограничението: int, <=, =, >= и т.н. от списъка на безименната комбинирана кутия;клетките или константите от дясната страна на ограничителното условие в полето Constraint.

Когато приключим въвеждането на текущото ограничение, натискаме бутона Add, ако трябва да въведем ново огрaничение, или бутона OK, ако въвеждането е приключило.

След като се върнем в диалоговата кутия Solver Parameters, поставяме отметка в полето Make Unconstrained Variables Non-Negative, защото всички променливи в задачата трябва да са неотрицателни. От списъка на комбинираната кутия Select a Solving Method избираме Simplex LP (това е най-често използваният алгоритъм за решаване на транспортната задача, известен като симплекс метод). Не се препоръчва промяна на останалите елементи в диалоговата кутия.

Стартираме решаването на задачата, като натиснем бутона Solve в диалоговата кутия Solver Parameters. Резултатът е показан на фиг. 6.

В диалоговата кутия Solver Results се дава информация за резултата от извършената оптимизация. В конкретния случай се оказва, че за полученото решение всички ограничителни условия и условия за оптималност са удовлетворени. Оптималните решения са показани в клетките C11:F13 на таблицата и както е показано в целевата клетка I8, цената на намерения оптимален план е \(L_{\text {min }}=180\).

В диалоговата кутия Solver Results се дава възможност да се запази в таблицата намереното оптимално решение (с избиране на радиобутона Keep Solver Solution) или да се възстанови първоначалният вид на работния лист (с избиране на радиобутона Restore Original Values). От тази диалогова кутия има възможност да се изработи справка с решението на задачата (Answer в полето Report).

Такъв подход е използван при разработката (Dallev et al. 2021).

4. Заключение

От предложеното описание и представеното решение на транспортна задача в MS Excel, с ползване на възможностите на MS Excel Solver, могат да се направят следните изводи.

 Използването на софтуерни приложения значително ускорява изчислителните процедури.

 Разгледаната функционалност на добавката Solver може да се използва както за решаване на задачи от транспортен тип, така и за решаване на задачи и в други области.

 Предложеният алгоритъм за описание на транспортна задача и нейното последващо решение, чрез ползване на MS Excel Solver, е лесно приложим.

REFERENCES

ANDERSON, D., SWEENEY, D, WILLIAMS, T, CAMM, J, MARTIN, K., 2012. An Introduction to Management Science, Quantitative Approaches to Decision Making, Ninth edition, South-Western Cengage Learning, USA.

DALLEV, M., KUNEVA, V, 2021. Optimization Model for Fertilization Operations, Scientific Papers. Series E-L, Land Reclamation, Earth Observation& Surveying, Environmental Engineering, vol. 10, pp. 85 – 88.

DVORKIN, L., ZHITKOVSKY, V., BORDIUZHENKO, O., RIBAKOV, Y., 2023. High Performance Concrete Optimal Composition Design, ISBN 978100096276-5, 978-103241386-0, DOI 10.1201/9781003357865, 1 – 2001.

EISELT, H.A., SANDNLOM, C.L., 2002. Operations research: A model-based approach. Springer Nature.

FAIZULLIN, R., PAVLOV, I, KONSTANTINOV, P., 2022. Methodology for Optimizing Supply Chains, Proceedings of SPIE – The International Society for Optical Engineering, 12251,122510U.

IVANOV, G., KALTINSKA, R., 1973. Numerical methods (textbook for 10th grade of general education labor polytechnic schools, ed. acad. B. Sendov), Technika, Sofia.

IVANOV, I., KYUCHUKOVA, V., KALTINSKA, R., KARAMITEVA, Z., DONCHEV, A., MITEV, Y., MILANOV, P., KIROV, N., KUNCHEV, O., 1989. Mathematical Optimization Problem Solving Guide, Jusautir, Sofia, 36/9534612431/4805-33289.

IVANOV, I., 2004. Duality in Linear Optimization, Sofia University “St. Kliment Ohridski”, Sofia, ISBN 954-07-2055-9. [In Bulgarian]

IVANOV, I., LOMEV, B., 2008. Applications of Quantitative Methods in Business Management, Sofia, ISBN 978-954-9526-50-9. [In Bulgarian]

IVANOV, I., TANOV, V., 2018. Big Data Analytics Algorithms and Applications. Machine learning. Avangard Prima, Sofia, ISSN 978-619-239-010-5. [In Bulgarian]

IVANOV, I., 2020. Quantitative Analysis of Patterns and Big Data, Avangard Prima, Sofia, ISBN 978-619-239-403-5. [In Bulgarian]

IVANOVA, I., MILANOVA, M., KUNEVA, V., 2011. Handbook on Applied Mathematics. Academic Press AU, Plovdiv. (In Bulgarian).

IVANOVA, I., KUNEVA, V., 2018. Handbook on Optimization Methods. Academic Press AU, Plovdiv. [In Bulgarian]

KUNEVA, V., MILEV, M., GOCHEVA, M., 2021. Modeling The Transportation Assessment with MS Excel Solver, AIP Conference Proceedings, vol. 2333, 15005-1-1500510.

LUENBERGER, D. G., YE, Y., 2008. Linear and Nonlinear Programming, Springer Science+Business Media LLC, New York , \(3{ }^{\text {rd }}\) ed., ISBN 978-0-387745022.

MARINOV, M., MARINOVA, L., 2016. Algorithm for Calculating the Transportation Problem and Its Solution in Excel. Scientific Works in Rousse University, Russe, vol. 55. Issue 3.3, pp. 19 – 24. [In Bulgarian]

SLAVKOVA, M., TZENOVA, Z., 2011. Collection of Tasks on Quantitative Methods and Statistics, First Edition, Technical University Sofia, Simolini, ISBN: 978-954-9493-41-2. [In Bulgarian]

TAHAN, H.A., 2017. Operation Research. An Introduction, Tenth Edition.

WINSTON, W.L., 2004. Operations Research: Applications and Algorithms. Brooks/Cole, Thomson Learning.