Решение транспортной задачи в среде Excel-7.0 Текст научной статьи по специальности «Математика»
Текст научной работы на тему «Решение транспортной задачи в среде Excel-7.0»
Ю. Н. Кондратьев. Решение транспортной задачи в среде Excel-7.0
Решение транспортной задачи в среде Excel-7.0
Ю. Н. Кондратьев1 Петрозаводский государственный университет
Статья посвящена оптимизации транспортных перевозок в среде Excel-7. Приведен конкретный пример решения транспортной задачи.
Ключевые слова: транспортная задача, среда Excel-7.
The article is devoted to the problem of transport optimization in software Excel-7. It presents a specific example of the transport problem solution.
Keywords: transport task, optimization, software Excel-7.
Решение транспортной задачи, которая связана с оптимизацией перевозок различных грузов, является актуальной задачей.
В настоящее время эта задача решается при помощи программирования на различных алгоритмических языках. В то же время решение этой задачи можно осуществлять более простыми методами в среде Excel-7.0.
Известно, что транспортная задача в общем виде имеет следующую формулировку:
1. Имеется m пунктов отправления (ПО) А1, А2. Am, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2. а;^ единиц.
2. Имеется n пунктов назначения (ПН) В1, В2. Bn, подавших заявки на получение соответственно bb b2. bn единиц груза.
3. Сумма всех запасов грузов равна сумме всех заявок
i=1 j=1 где i = 1, 2. m, а j = 1, 2. n.
4. Известны стоимости Су перевозки единицы груза от каждого пункта отправления А; до каждого пункта назначения В^
Все числа стоимости Су перевозки единицы груза образуют прямоугольную матрицу (2):
1 Автор - доцент кафедры технологии металлов и ремонта
© Ю. Н. Кондратьев, 2003
С1,1 С1,2 ■ ■ ■ C1,n С2,1 С2,2 ■ ■ ■ C2,n
5. Требуется составить такой план перевозок (откуда, куда и сколько единиц груза), чтобы все заявки были выполнены, а общая стоимость всех перевозок была бы минимальной.
Для решения этой задачи обозначим количество перевозимого груза Хц.
Тогда неотрицательные значения этих переменных можно записать в виде матрицы (3).
Х2 1 Х2 2 ■ ■ ■ X2
В свою очередь неотрицательные переменные должны удовлетворять следующим условиям:
1) Суммарное количество груза, вывозимого из каждого ПО во все ПН, должно быть равно запасу груза в данном пункте, тогда это даст т уравнений-равенств (4):
2) Суммарное количество груза, поступающее в каждый ПН из всех ПО, должно соответствовать заявке каждого пункта назначения, тогда это даст п условий-равенств (5):
Тогда целевая функция примет вид (6):
Особенностью транспортной задачи является то, что все коэффициенты при неизвестных Хц в условиях (4) и (5) равны единицам.
В данной задаче число линейно независимых уравнений равно числу базисных переменных:
1и = Вр = т + п - 1,
где 1и - число линейно независимых уравнений; Вр - число базисных переменных, а число свободных переменных равно:
Труды лесоинженерного факультета ПетрГУ
Sp = m * n - (m + n - 1) = (m - 1) * (n - 1).
Следовательно, в оптимальном плане число (т - 1)(п - 1) перевозок будет равно нулю, то есть из каких-то пунктов отправления в какие-то пункты назначения ничего не будет перевозиться.
Решение транспортной задачи в среде Ехсе1-7.0 рассмотрим на конкретном примере с исходными данными, приведенными в табл. 1, то есть имеется три
пункта отправления А; с количеством груза в каждом пункте 35, 45 и 50 единиц.
Требуется перевезти эти грузы в четыре пункта назначения Bj с заявками 30, 10, 65 и 25 единиц со стоимостью перевозок единицы груза из А; в Bj, представленной в табл. 1.
Для решения задачи в электронную таблицу вводятся исходные данные и записываются условия (табл. 2).
Пункт отправления (ПО) Пункт назначения (ПН)
обозначение Bi В2 Вз В4
запас груза Стоимость перевозок Су, у.е.
Ai 35 5 13 6 11
Заявка 30 10 65 25
Запись условий в ячейку Запись условий в окно Поиск решения
адрес ячейки условия
G13 СУММПРОИЗВ(В7:Е7;В19:Е19) $0$13=$1$13
G14 СУММПРОИЗВ(В8:Е8;В20:Е20) $0$14=$1$14
G15 СУММПРОИЗВ(В9:Е9;В21:Е21) $0$15=$1$15
G16 СУММ(В7:В9) $0$16=$1$16
G17 СУММ(С7:С9) $0$17=$1$17
G18 CyMM(D7:D9) $0$18=$1$18
G19 СУММ(Е7:Е9) $0$19=$1$19
G20 СУММ(113:115) $0$20=$1$20
G21 СУММ(116:119) $0$21=$1$21
Стоимость перевозок в условных единицах записываем в блок ячеек В13:Е15 (табл. 3).
Коэффициенты при неизвестных, равные единицам, заносим в ячейки В19:Е21.
В ячейки 113:115 записываем количество грузов, находящихся в пунктах отправления А;, а в ячейки
116:119 заносим количество грузов, требуемых по заявкам пунктов назначения Bj.
В ячейку G7 записываем условия целевой функции:
Электронная таблица решения транспортной задачи
№ стр. A B С D E F G H I
1 2 3 4 5 6 7 8 9 10
2 Транспортная задача
5 Значения переменных
6 X(i,1) X(i,2) X(i,3) X(i,4) Целевая функция Ъ min
7 35 10 0 25 0 620 у.е.
Ю. Н. Кондратьев. Решение транспортной задачи в среде Ехсе1-7.0
Продолжение табл. 3
1 2 3 4 5 6 7 8 9 10
11 Стоимость перевозок от А; до Bj
13 5 13 6 11 35 = 35
14 4 7 12 8 45 = 45
15 9 2 3 10 50 = 50
17 Коэффициенты уравнений 10 = 10
18 к(;,1) к(;,2) к(;,3) к(;,4) 65 = 65
19 1 1 1 1 25 = 25
20 1 1 1 1 130 = 13 0
21 1 1 1 1 130 = 13 0
В результате поиска решения найден оптимальный план перевозок, представленный в ячейках В7:Е9 табл. 3, то есть сколько, откуда и куда надо перевезти единиц груза с минимальными затратами, при этом целевая функция составила:
1. Кондратьев Ю. Н. Оптимизация транспортных перевозок в среде ЕХСЕЬ-7 // Новые технологии и устойчивое управление в лесах северной Европы: Тез. докл. межд. конф. Петрозаводск: Изд-во ПетрГУ. 2001. С. 66.