Решение транспортной задачи на ПК с помощью Excel.

Рассмотрим следующую транспортную задачу. На три базы А₁, А₂, А₃ поступил однородный груз в количествах а₁,а₂, а₃ единиц. Груз требуется перевезти в пять пунктов В₁, В₂, В₃, В₄, В₅ в количествах b₁, b₂, b₃, b₄, b₅ единиц соответственно.

Требуется так спланировать перевозки, чтобы общая их стоимость была минимальной.

Пусть количество груза на базах и потребности в грузе в пункте назначения, а также стоимости перевозки единицы груза известны (в условных единицах).

 

Запасы поставщиков	Потребности потребителей
b1=85	b2=65	b3=90	b4=60	b5=70
a1=120
a2=150
a3=100

 

В данном случае запасы поставщиков и потребности потребителей совпадают, и мы имеем дело с закрытой моделью транспортной задачи. Войдя в MS EXCEL, создаем форму для решения задачи.

Для этого необходимо выполнить резервирование изменяемых ячеек (рис. 3.1)

 

	A	B	C	D	E	F	G
	Матрица перевозок (изменяемые ячейки)
	Исходные данные

Рис. 3.1 Ввод исходных данных и граничных условий.

Выполним резервирование изменяющихся ячеек: в блок ячеек В3:F5 вводится «1», т.е. резервируется место, где после решения задачи будет находиться распределение поставок, обеспечивающие минимальные затраты на перевозку груза.

Введем условие реализации запасов поставщиков, т.е.

a_i= , i= , где

a_i- запас i-го поставщика;

х_ij- объем поставки груза от i-го поставщика к j-му потребителю;

n – количество потребителей

Для этого следует выполнить следующие операции:

· курсор в ячейку А3;

· щелкнуть знак ;

· выделить необходимые для суммирования ячейки В3: F3;

· нажать enter – подтверждение ввода формулы для суммирования.

Аналогичные действия выполняются для ячеек А4, А5 (или: курсор в А3; копировать в буфер; выделить ячейки А4:А5; вставить из буфера).

Введем условие удовлетворения запросов потребителей:

b_j= , j=

bj – это потребность j-го потребителя

m – это кол-во поставщиков.

Для этого выполняют следующие операции:

- курсор в В6;

- щелкнуть знак При этом автоматически выделяется весь столбец В3:В5;

- нажать enter – это подтверждение суммирования показателей выделенного столбца.

Аналогичные действия выполняем для ячеек С6:F6. (курсор В6; копировать в буфер; выделить С6:F6; вставить из буфера).

Ввод исходных данных осуществляем для трёх поставщиков (ячейки А10:A12), пяти потребителей (В9:F9), а также удельных затрат по доставке единицы товара от конкретного поставщика к конкретному потребителю (блок B10:F12) (рис. 3.1).

Для назначения целевой функции, соответствующей минимальным суммарным затратам на доставку груза зарезервируем ячейку и введем формулу для ее вычисления:

F= , где

C_ij – стоимость доставки единицы груза от i-го поставщика к j-ому потребителю;

X_ij – это объем поставщика от i-го поставщика к j-ому потребителю.

Для этого:

- курсор переводим в ячейку В13(сюда будет помещаться значение целевой функции);

- щелкнуть мастер функций (значение f_x);

- в окне категории выбрать математические;

- в окне функции при помощи спинора выбрать СУММПРОИЗВ;

- ОК;

- В окне СУММПРОИЗВ указать адреса массивов, элементы которых обрабатываются этой функцией. Целевая функция представляет собой произведение удельных затрат на доставку груза (расположенных в блоке ячеек B10:B12) и объемов поставок для каждого потребителя (содержимое ячеек В3:F5).

Для этого:

- в поле массив 1 указать адреса B10:F12;

- в поле массив 2 указать адреса B3:F15;

- ОК;

- Подтверждение окончания ввода массивов.

В поле ячейки В13 появится числовое значение, равное произведению единичных поставок на удельные коэффициенты затрат по доставке грузов (число 135) в данной задаче (рис 3.1).

Для ввода зависимостей из математической модели необходимо выполнить следующий перечень операций:

- щелкнуть СЕРВИС – ПОИСК РЕШЕНИЯ:….;

- курсор в поле установки целевой ячейки;

- ввести адрес $В$13 (или курсор в В13, а затем щелкнуть ПОИСК РЕШЕНИЯ. При этом осуществляется автоматический ввод адреса $B$13 в поле адреса целевой ячейки);

- установить направление изменения ценовой функции, равное “минимальному значению”;

- ввести адреса измененяемых ячеек В3:F5. Для этого:

- щелкнуть в поле изменение ячейки;

- ввести адреса $B$3:$F$5 (или же щелкнуть на маленькой красной стрелке рядом с этим полем, выйти в таблицу с матрицей перевозок, выделить блок ячеек B3:F5, щелкнуть на красной стрелке и вернуться в блок ПОИСКА РЕШЕНИЙ, при этом нужные адреса будут введены).

Для ввода ограничений задачи, необходимо ввести условие реализации запасов всех поставщиков. Для этого:

- щелкнуть ДОБАВИТЬ ОГРАНИЧЕНИЯ;

- в поле ссылки на ячейки ввести адреса $A$3:$A$5;

- в среднем поле установить знак “=”. Для этого щелкнуть спинор и выбрать знак “=”.

- в поле ОГРАНИЧЕНИЯ установить адреса $A$10:$A$12.

- щелкнуть ОК, т.е. подтвердить введенное условие.

После этого вы вернетесь в поле “ПОИСК РЕШЕНИЯ”. Далее вводим ограничение, которое реализует условие удовлетворения потребности для всех потребителей. Для этого:

- щелкнуть ДОБАВИТЬ ограничение;

- в поле ССЫЛКА НА ЯЧЕЙКУ ввести адреса $B$6:$F$6;

- в поле знака выбрать “=”;

- в поле ОГРАНИЧЕНИЯ (третье поле) установить адреса $B$9:$F$9;

- ОК.

Устанавливаем ограничения на решение задачи. Для этого:

- щелкнуть ПАРАМЕТРЫ;

- установить ЛИНЕЙНАЯ МОДЕЛЬ;

- установить НЕОТРИЦАТЕЛЬНЫЕ ЗНАЧЕНИЯ, т.к. объемы поставок груза отрицательной величиной быть не могут;

- ОК.

После этого произойдет выход в поле ПОИСКА РЕШЕНИЙ:

- нажать ВЫПОЛНИТЬ.

После завершения решения осуществляется просмотр результатов и отчета с помощью появившегося на экране диалогового окна “РЕЗУЛЬТАТЫ ПОИСКА РЕШЕНИЯ”.

В окне ТИП ОТЧЕТА выбрать интересующий вид отчета (результаты; устойчивость; пределы) и ОК.

Внизу страницы экрана содержится сообщение “ОТЧЕТ ПО РЕЗУЛЬТАТАМ ”.

Щелкнуть это сообщение, на экран выводится результат решения задачи, который можно распечатать.

При нажатии ЛИСТ1 происходит возврат в программу к исходным данным.

В матрице перевозок содержатся оптимальные объемы поставок грузов от поставщика потребителям, дающие минимум затрат на доставку. Значение ценовой функции содержится в ячейки В13 и для конкретной задачи равна 2265 ден. ед. (рис 3.2)

 

 

	А	B	C	D	E	F	G
	Матрица	Перевозки
	Исходные	Данные

 

Рис. 3.2. Результаты поиска решений

Ответ: Минимальная стоимость затрат на перевозку грузов, равна 2265 ден. ед. и будет обеспечен при следующем плане перевозок:

- с базы А1 в пункт В1 50 ед. груза;

в пункт В5 70 ед. груза;

- с базы А2 в пункт В2 65 ед. груза;

в пункт В3 85 ед. груза;

- с базы А3 в пункт В1 35 ед. груза;

в пункт В3 5 ед. груза;

в пункт В4 60 ед. груза.

 

4.Тестовые вопросы.

0613234 Дать общую формулировку транспортной задачи.

1.Составить такой план перевозки некоторого груза от фиксированного количества поставщиков к фиксированному количеству потребителей, при котором весь груз будет доставлен за одинаковое время.

2.Составить такой план перевозки некоторого груза от фиксированного поставщика к фиксированному потребителю, при котором весь груз будет доставлен за одинаковое время.

3.Составить такой план перевозок некоторого груза от фиксированного количества поставщиков к фиксированному количеству потребителей, при котором все маршруты равны и затраты на перевозку оптимальны.

4.Составить такой план перевозок некоторого груза от фиксированного количества поставщиков к фиксированному количеству потребителей, при котором суммарные расходы на перевозку были бы минимальны.

5.Составить такой план перевозок некоторого груза от фиксированного количества потребителей к фиксированному количеству поставщиков, при котором суммарные расходы на перевозку будут минимальны.

 

0622354 Коэффициенты C_ij в функции цели транспортной задачи (X_ij – количество перевозимого груза от i-го поставщика к j-ому потребителю) представляют собой:

1. Вес единицы груза i-го поставщика.

2. Тарифы на перевозки всего груза от i-го поставщика к j-ому потребителю.

3. Себестоимость получения единицы товара i-го производителя.

4. Затраты на производство единицы товара i-го вида из j-го типа сырья.

5. Тарифы на перевозку единицы груза от i-го поставщика к j-ому потребителю

0632234 Модель транспортной задачи называется закрытой, если:

1.Суммарные потребности потребителей строго меньше суммарных запасов поставщиков.

2.Суммарные потребности потребителей не равны суммарным запасом поставщиков.

3.Суммарные потребности потребителей равны суммарным запасам поставщиков.

4.Суммарные потребности потребителей строго больше суммарных запасов поставщиков.

5.Суммарные потребности потребителей отличаются от суммарных запасов поставщиков на конкретную величину, задаваемую в каждом конкретном случае.

0643242 Модель транспортной задачи называется открытой, если:

1.Суммарные потребности потребителей строго меньше суммарных запасов поставщиков.

2.Суммарные потребности потребителей не равны суммарным запасам поставщиков.

3.Суммарные потребности потребителей равны суммарным запасом поставщиков.

4.Суммарные потребности потребителей строго больше суммарных запасов поставщиков.

5.Суммарные потребности потребителей отличаются от суммарных запасов поставщиков на конкретную величину, задаваемую в каждом конкретном случае.

0653542 Перечислить методы построения исходного опорного плана

В транспортной задаче.

1. Диагональный метод, метод двойного предпочтения, симплексный метод.

2. Диагональный метод, метод минимальной стоимости, метод двойного предпочтения

3. Метод минимальной стоимости, метод двойного предпочтения, метод потенциалов.

4. Метод потенциалов, метод двойного предпочтения, диагональный метод.

5. Метод двойного предпочтения, диагональный метод (метод северо-западного угла), метод максимальной стоимости.

 

0662231 Построение опорного плана по методу минимальной стоимости в транспортной задаче начинается с клетки:

1. Имеющей максимальную стоимость перевозки от i-го поставщика, к j-ому потребителю;

2. Находящейся в левом верхнем углу таблицы соответствующей стоимости перевозок от первого поставщика к первому потребителю;

3. Имеющей наименьшую стоимость перевозки от i-го поставщика, к j-ому потребителю;

4. Находящейся на пересечении строки, имеющей минимальный запрос и столбца, имеющего минимальную потребность;

5. Находящейся в первом столбце матрицы соответствующей минимальной стоимости перевозки и проверки минимальна ли эта стоимость и в своей строке.

0673142 Построение первого опорного плана с помощью диагонального метода в транспортной задаче начинается с клетки:

1. Имеющей максимальную стоимость перевозки от i-го поставщика, к j-ому потребителю;

2. Находящейся в левом верхнем углу таблицы соответствующей стоимости перевозок от первого поставщика к первому потребителю;

3. Имеющей наименьшую стоимость перевозки от i-го поставщика, к j-ому потребителю;

4. Находящейся на пересечении строки, имеющей минимальный запрос и столбца, имеющего минимальную потребность;

5. Находящейся в первом столбце матрицы соответствующей минимальной стоимости перевозки и проверки минимальна ли эта стоимость и в своей строке.

 

 

0682453 Построение первого опорного плана с помощью о метода двойного предпочтения:

1. Имеющей максимальную стоимость перевозки от i-го поставщика, к j-ому потребителю;

2. Находящейся в левом верхнем углу таблицы соответствующей стоимости перевозок от первого поставщика к первому потребителю;

3. Имеющей наименьшую стоимость перевозки от i-го поставщика, к j-ому потребителю;

4. Находящейся на пересечении строки, имеющей минимальный запрос и столбца, имеющего минимальную потребность;

5. Находящейся в первом столбце матрицы соответствующей минимальной стоимости перевозки и проверить минимальна ли эта стоимость и в своей строке.

0692135 Опорный план транспортной задачи будет невырожденным, если он содержат в матрице перевозок следующее количество заполненных клеток

(m-количество поставщиков, а n-количество потребителей):

1. m+n+1;

2. m+n;

3. m+n-1;

4. m*n-1;

5. любое количество клеток.

0701432 Если исходный опорный план транспортной задачи вырожденный, количество занятых клеток доводят до m+n-1 (m-количество поставщиков, а n-количество потребителей) путем введения:

1. Либо фиктивного поставщика, либо фиктивного потребителя;

2. Фиктивного поставщика;

3. Фиктивного потребителя;

4. Нулевых поставок поставщиков;

5. Нулевых поставок потребителей.

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

1. Фиктивную клетку с нулевой перевозкой;

2. Фиктивного поставщика с нулевыми тарифами перевозок;

3. Фиктивного потребителя с нулевыми перевозками и с нулевыми тарифами перевозок;

4. Фиктивного поставщика с нулевыми перевозками и с нулевыми тарифами перевозок;

5. Фиктивного потребителя с нулевыми тарифами перевозок.

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

1. Фиктивную клетку с нулевой перевозкой;

2. Фиктивного поставщика с нулевыми тарифами перевозок;

3. Фиктивного потребителя с нулевыми перевозками и с нулевыми тарифами перевозок;

4. Фиктивного поставщика с нулевыми перевозками и с нулевыми тарифами перевозок;

5. Фиктивного потребителя с нулевыми тарифами перевозок.

0732453 Метод потенциалов при решении транспортной задачи – это метод:

1. Решения задач нелинейного программирования;

2. Построения системы потенциалов;

3. Проверки плана перевозок на их объективность;

4. Улучшения первого опорного плана;

5. Нахождения оптимального плана перевозок.

0742345 Решение транспортной задачи методом потенциалов начинается с построения:

1. Первой симплексной таблицы;

2. Общей постановки задач и приведение её к каноническому виду;

3. Системы потенциалов;

4. Первого опорного плана;

5. Сетевого графика во времени.

0752132 Система потенциалов при решении закрытой модели транспортной задачи (m-количество поставщиков, n-количество количество потребителей) определяется из решения системы:

1. m+n-1 линейных уравнений составленных для клеток имеющих минимальные стоимости перевозок;

2. m+n-1 линейных уравнений составленных для свободных клеток опорного плана;

3. m+n-1 линейных уравнений составленных для занятых клеток опорного плана;

4. m+n линейных уравнений составленных для свободных клеток опорного плана;

5. Линейных уравнений составленных для вершин цикла пересчета.

0763435 Косвенными тарифами в методе потенциалов транспортной задачи понимают сумму потенциалов поставщиков и потребителей:

1. найденную для любой клетки матрицы перевозок, соответствующей планируемым тарифом по перевозке;

2. найденную для занятых клеток плана перевозок;

3. найденную для занятых клеток перевозок, если полученный план является оптимальным;

4. найденную для любой клетки матрицы перевозок, соответствующей фактической стоимости перевозок;

5. найденную для свободных (незанятых) клеток плана перевозок.

0772345 Косвенный тариф в методе потенциалов транспортной задачи должен быть:

1. Больше или равен тарифу занятой клетки матрицы перевозок;

2. Больше или равен тарифу перевозки для свободной (незанятой) клетки матрицы перевозок;

3. Меньше или равен тарифу занятой клетки матрицы перевозок;

4. Меньше или равен тарифу перевозки для свободной (незанятой) клетки матрицы перевозок;

5. Больше или равен тарифу для любой клетки матрицы перевозок.

0781324 Что бы построенный план перевозок транспортной задачи (при использовании метода потенциалов) был оптимальным, сумма потенциалов поставщиков и потребителей для занятых клеток:

1. Должна быть больше тарифа перевозок, а для свободных равняться ему;

2. Должна равняться тарифу, а для занятых должна быть равна или меньше тарифа перевозок;

3. Должна равняться тарифу, а для свободных должна быть равна или меньше тарифа перевозок;

4. Должна равняться тарифу, а для свободных быть больше тарифа перевозок.

5. Нет правильного ответа.

 

0792324 Циклом пересчета плана перевозок в транспортной задаче называется замкнутый многоугольник:

1. Одна вершина которого совпадает с занятой клеткой, для которой образуется цикл, а все остальные со свободными клетками, которые следует заполнить;

2. Одна вершина которого совпадает со свободной клеткой, для которой образуется цикл, а все остальные с заполненными клетками;

3. две вершины которого совпадают со свободными клетками, которые находятся либо в одной строке, либо в одном столбце, а все остальные – с занятыми клетками;

4. две вершины которого совпадают с занятыми клетками, которые лежат либо в одной строке, либо в одном столбце, а все остальные – со свободными клетками.

5. Нет правильного ответа.

0803452 Новый план перевозок, полученный по циклу пересчета в транспортной задаче отличается тем, что:

1. Свободная переменная заменена на базисную, а остальные переменные стали свободными.

2. Свободная переменная заменена на базисную, но одна из базисных переменных становится свободной.

3. Базисная переменная заменена на свободную, а соседние с ней на базисные.

4. Поменялось равновесие между запасами и потребностями.

5. Нет правильного ответа.

0812415 Пересчет по циклу в транспортной задаче осуществляется для:

1. Свободной клетки матрицы перевозок, для которой косвенный тариф больше тарифа перевозки;

2. Свободной клетки матрицы перевозок, для которой косвенный тариф меньше тарифа перевозки;

3. Занятой клетки матрицы перевозок, для которой косвенный тариф больше тарифа перевозки;

4. Занятой клетки матрицы перевозок, для которой косвенный тариф меньше тарифа перевозки;

5. Любой клетки матрицы перевозок, для которой косвенный тариф меньше тарифа перевозки.

0821435 Оптимальный план транспортной задачи является единственным, если:

1. Сумма потенциалов поставщиков и потребителей строго меньше тарифов перевозок для всех занятых клеток матрицы перевозок;

2. Сумма потенциалов поставщиков и потребителей строго больше тарифов перевозок для всех свободных клеток матрицы перевозок;

3. Сумма потенциалов поставщиков и потребителей больше или равна тарифам перевозок для всех свободных клеток матрицы перевозок;

4. Сумма потенциалов поставщиков и потребителей строго меньше тарифов перевозок для всех свободных клеток матрицы перевозок;

5. Косвенные тарифы строго больше тарифов перевозок для всех занятых клеток матрицы перевозок.

0832543 Замкнутый многоугольник, одна из вершин которого совпадает со свободной клеткой, а все остальные – с заполненными клетками называется:

1. Структурно-временная таблица.

2. Симплекс-таблица.

3. Многоугольник решений.

4. Цикл пересчета.

5. Область существования решений.

0841432 Любой цикл пересчета в транспортной задаче имеет:

1. Нечетное число вершин, каждая из которых отмечается знаком плюс или минус. Свободной клетке, для которой был выбран цикл, приписывается знак минус.

2. Четное число вершин, каждое из которых отмечается знаком плюс или минус. Свободной клетке, для которой был выбран цикл, приписывается знак минус.

3. Нечетное число вершин, каждая из которых отмечается знаком плюс или минус. Свободной клетке, для которой был выбран цикл, приписывается знак плюс.

4. Четное число вершин, каждое из которых отмечается знаком плюс или минус. Свободной клетке, для которой был выбран цикл, приписывается знак плюс.

5. Четное число вершин, каждое из которых отмечается знаком плюс или минус. Занятой клетке, для которой был выбран цикл, приписывается знак плюс.