Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

РАЗРАБОТКА СПЕЦИАЛЬНОГО МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ СИСТЕМЫ ОПТИМИЗАЦИИ ЛОГИСТИЧЕСКИХ ЗАТРАТ НА ОСНОВЕ МЕТОДА НЕРАВЕНСТВ

Кравчук С.П. 1 Кравчук И.С. 2 Швед Е.В. 1
1 ФГБОУ ВО «Российский экономический университет им. Г.В. Плеханова»
2 ФГБОУ ВО «Московский государственный университет путей сообщения Императора Николая II»
Известно, что задачи линейного программирования широко используются во всевозможных практических задачах оптимизации как экономических, так и технических проблем. Однако изучение основных методов решения подобных задач требует длительной теоретической подготовки, включающей в себя серьёзное освоение фундаментального раздела высшей математики – линейной алгебры. Авторы данной статьи в предыдущем цикле работ по линейному программированию предложили простой универсальный способ решения любых задач линейного программирования с помощью исключения переменных в системе линейных неравенств. Настоящая статья продолжает цикл работ авторов по применению метода неравенств к задачам транспортного типа, в том числе с правильным и неправильным балансами, ограничениями на пропускную способность и т.п. Предлагаемый метод будет полезен студентам экономических специальностей, а также инженерам-практикам, использующим методы оптимизации.
неравенства
линейное программирование
симплекс-метод
метод Жордана-Гаусса
целевая функция
экстремум
матрица
1. Быканова О.А. Исследовательская деятельность в рамках обучения финансовой грамотности социально ориентированной молодежи // Молодой ученый. – 2015. – № 22.
2. Быканова О.А. Элементы общей топологии: Учеб.-метод. пособие по специальности 032100 «Математика» по курсу «Геометрия». Под ред. О.Н. Бабенко; М-о образования Рос. Федерации. Таганрог. гос. пед. ин-т. – Таганрог: Изд-во Таганрог. гос. пед. ин-та, 2001.
3. Гольштейн Е.Г., Юдин Д.Б. Задачи и методы линейного программирования. Задачи транспортного типа. – М.: Либроком, 2010.
4. Общий курс высшей математики для экономистов. Учебник под ред. проф. В.И. Ермакова. – М.: ИНФРА-М, 2000.
5. Сборник задач по высшей математике для экономистов: Учебное пособие / Под ред. В.И. Ермакова. – М.: ИНФРА-М, 2005.
6. Кравчук С.П., Кравчук И.С., Швед Е.В. Экстремумы в системе линейных неравенств с двумя переменными. – СПб.: Современные аспекты экономики, 2010. – № 6 (154).
7. Кравчук С.П., Кравчук И.С., Татарников О.В., Швед Е.В. Метод неравенств в задачах линейного программирования // Фундаментальные исследования. – 2014. – № 3–1. – С. 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


Библиографическая ссылка

Кравчук С.П., Кравчук И.С., Швед Е.В. РАЗРАБОТКА СПЕЦИАЛЬНОГО МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ СИСТЕМЫ ОПТИМИЗАЦИИ ЛОГИСТИЧЕСКИХ ЗАТРАТ НА ОСНОВЕ МЕТОДА НЕРАВЕНСТВ // Фундаментальные исследования. – 2016. – № 12-5. – С. 998-1003;
URL: https://fundamental-research.ru/ru/article/view?id=41206 (дата обращения: 29.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674