Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,685

DEVELOPMENT SPECIAL SOFTWARE ENGINE OPTIMIZATION OF LOGISTICS COSTS BASED ON THE METHOD INEQUALITIES

Kravchuk S.P. 1 Kravchuk I.S. 2 Shved E.V. 1
1 Plekhanov Russian University of Economics
2 Moscow state University of railway engineering
It is well known that linear programming problems are very useful in different practical tasks for the optimization of both economic and technical problems. However, the study of basic procedures solving such problems demands protracted theoretical background which involves the grave exploration of higher mathematics’ fundamental branch that is linear algebra. In the preceding series of linear programming works the authors of this article proposed a simple universal way to do any linear programming problems using the elimination of variables in the linear inequalities system. Present article continues authors’ series of works about the use of inequalities procedure to the problems of transport type including the problems with regular and irregular balances, with the constraint on capacity. Proposed procedure will be useful for the students who are economics majors as well as for practical engineers using optimization procedures.
inequality
linear programming
the simplex method
Gauss-Jordan method
the objective function
extremum
matrix
1. Bykanova O.A. Issledovatelskaja dejatelnost v ramkah obuchenija finansovoj gramotnosti socialno orientirovannoj molodezhi // Molodoj uchenyj. 2015. no. 22.
2. Bykanova O.A. Jelementy obshhej topologii: Ucheb.-metod. posobie po specialnosti 032100 «Matematika» po kursu «Geometrija». Pod red. O.N. Babenko; M-o obrazovanija Ros. Federacii. Taganrog. gos. ped. in-t. Taganrog: Izd-vo Taganrog. gos. ped. in-ta, 2001.
3. Golshtejn E.G., Judin D.B. Zadachi i metody linejnogo programmirovanija. Zadachi transportnogo tipa. M.: Librokom, 2010.
4. Obshhij kurs vysshej matematiki dlja jekonomistov. Uchebnik pod red. prof. V.I. Ermakova. M.: INFRA-M, 2000.
5. Sbornik zadach po vysshej matematike dlja jekonomistov: Uchebnoe posobie / Pod red. V.I. Ermakova. M.: INFRA-M, 2005.
6. Kravchuk S.P., Kravchuk I.S., Shved E.V. Jekstremumy v sisteme linejnyh neravenstv s dvumja peremennymi. SPb.: Sovremennye aspekty jekonomiki, 2010. no. 6 (154).
7. Kravchuk S.P., Kravchuk I.S., Tatarnikov O.V., Shved E.V. Metod neravenstv v zadachah linejnogo programmirovanija// Fundamentalnye issledovanija. 2014. no. 3–1. pp. 148–153.

Задачи линейного программирования транспортного типа широко распространены в практических исследованиях оптимизации различных экономических задач [1]. Однако существующие методы их решения нетривиальны и требуют специальной теоретической подготовки [1–3], как и вообще при решении любых других задач линейного программирования. В настоящее время существуют компьютерные программы, позволяющие решать подобные задачи с любым количеством переменных. Но для правильного использования этих программ и анализа найденного решения необходимо освоить хотя бы простейшие методы решения задач с малым числом переменных.

Авторам удалось построить простой универсальный метод решения задач линейного программирования с помощью исключения переменных в системе линейных неравенств, используя таблицы Гаусса [4, 5]. Данная работа демонстрирует применение этого метода к решению транспортных задач.

Решение транспортной задачи с правильным балансом

Пусть исходная таблица имеет вид:

bj

ai

10

12

8

17

3

х11

5

х12

2

х13

13

4

х21

1

х22

7

х23

где xij – объёмы перевозок от i-го поставщика к j-му потребителю, ai – запасы поставщиков, bj – запросы потребителей. Числа рядом с xij указывают стоимость cij перевозки единицы груза. Переменные xij должны удовлетворять следующим ограничениям:

krav01.wmf (1)

Приведём систему (1) к разрешённому виду, используя таблицы Жордана-Гаусса [2, 3].

В итоге решение системы (1) имеет вид:

krav02.wmf (2)

Целевая функция krav03.wmf является суммой затрат на перевозку всех грузов и должна быть минимальна: krav04.wmf

С учётом (2):

krav05.wmf

krav06.wmf (3)

Как показано в [4], система неравенств, обеспечивающая Zmin, объединяет (2), (3) и выглядит следующим образом:

krav08.wmf (4)

Исключаем переменные в системе (4) с помощью таблиц Гаусса, как в [4]:

Заметим, что в табл. 2 вычеркнуты автоматически выполняющиеся неравенства-следствия, например krav09.wmf

Таблица 1

kravch1.wmf

Таблица 2

kravch2.wmf

Подставляя Z = 59 в подтаблицу II, получим:

krav10.wmf.

Подставляя Z = 59 и x23 = 0 в подтаблицу I, найдём:

krav11.wmf.

С учётом (2) окончательное решение данной транспортной задачи таково:

krav12.wmf при krav13.wmf

В общем случае т поставщиков и п потребителей (начало табл. 3) выглядит так:

Таблица 3

x11

x12

x1n

x21

x22

x2n

xm1

xm2

xmn

 

1

1

1

0

0

0

0

0

0

a1

0

0

0

1

1

1

0

0

0

a2

0

0

0

0

0

0

1

1

1

am

1

0

0

1

0

0

1

0

0

b1

0

1

0

0

1

0

0

1

0

b2

0

0

1

0

0

1

0

0

1

bn

Нетрудно проверить, что в окончательной подтаблице табл. 3 первая строка заменится на:

1

0

0

0

– 1

– 1

0

– 1

– 1

a1 – (b2+…+bn),

а строка с b1 будет состоять из одних нулей:

x11

x12

x1n

x21

x22

x2n

xm1

xm2

xmn

 

1

0

0

0

– 1

– 1

0

– 1

– 1

a1 – (b2 +…+ bn)

0

0

0

1

1

1

0

0

0

a2

0

0

0

0

0

0

1

1

1

am

0

1

0

0

1

0

0

1

0

b2

0

0

1

0

0

1

0

0

1

bn

С помощью этой подтаблицы легко выписываются соотношения типа (2)–(4).

Решение транспортной задачи с неправильным балансом

Рассмотрим случай, когда запросы потребителей больше запасов поставщиков:

bj

ai

16

14

10

17

3

х11

5

х12

2

х13

13

4

х21

1

х22

7

х23

Ограничения на переменные таковы:

krav14.wmf (5)

Выражая из равенств (5), например,

krav15.wmf (6)

преобразуем целевую функцию

krav16.wmf

krav17.wmf (7)

В итоге исходная система неравенств (5)–(7) рассматриваемой задачи выглядит так:

krav18.wmf (8)

Далее, последовательно, исключая переменные x12, x13, x22, x23 (табл. 4), найдём решение задачи (8):

krav19.wmf.

Столь же просто составляется система неравенств для транспортной задачи с ограничениями на пропускную способность типа

krav20.wmf

В этом случае к неравенствам вида (4), (8) добавляются ещё такие:

krav21.wmf

При этом неравенство – xij ≤ 0 следует откинуть, как выполняющееся автоматически.

Таблица 4

kravch3.wmf