Урок 15. Практическая работа по теме: Решение транспортной задачи

Группа С-303, С-304

Дисциплина: Информационные технологии в профессиональной деятельности

Дата: 13.04.2020

1. Запишите на 1 строке в тетради Тему урока, фамилию, группу, дату. ОБЯЗАТЕЛЬНО!

2. Фото выполненных в тетради заданий отправить на адрес электронной почты Nailjrakv@mail.ru, либо в ВК ( https://vk.com/id250125494) .

Выполнить задание:

1. Изучить теоретический материал урока.

2. Разобрать решение транспортной задачи.

3. Решить примеры 1 и 2 по образцу.

Теоретический материал урока:

Урок 15. Практическая работа по теме: Решение транспортной задачи.

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

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

В фирме имеются 4 склада с запасами цемента, на складе 1: 30 т, на складе 2: 48т, на складе 3: 20т, на складе 4: 30т. Всего 128т цемента. В эту фирму поступили 5 заявок продать цемент покупателям. Заявка 1 просит 18т, заявка 2: 27т, заявка 3: 42т, заявка 4: 15т, заявка 5: 26т.

Всего запросов на 128т.

Каждая перевозка будет иметь свою стоимость, которая зависит от того, с какого склада будут перевозиться запасы и в какое место их повезут. Все стоимости фирме известны и представлены в таблице.

Склады обозначены A1, A2, A3, A4

Заявки обозначены B1, B2, B3, B4, B5

Таблица стоимости перевозки со склада A на заявку B:

	B1	B2	B3	B4	B5
A1	13	7	14	7	5
A2	11	8	12	6	8
A3	6	10	10	8	11
A4	14	8	10	10	15

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

Таблица состоит из m- строк и n- столбов. В правом верхнем углу каждой клетки ставится стоимость C ij, а в центре вычисляются перевозки.

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

Теперь можно составить полную таблицу с данными:

Добавить столб «запасы на складах» и строку «заявки».

Внесение данных делается следующим образом:

	B1	B2	B3	B4	B5	Запасы Аi
A1	13	7	14	7	5	30
A2	11	8	12	6	8
A3	6	10	10	8	11
A4	14	8	10	10	15
Заявки Bj

Теперь можно составить полную таблицу с данными:

Добавить столб «запасы на складах» и строку «заявки».

Внесение данных делается следующим образом

Теперь составляем план перевозок, выполняем заявку B1 (туда требуется 18т): берем со склада A1 (где имеется 30т) необходимые 18 т, и тогда заявка B1 будет выполнена, а запасы на складе A1 уменьшатся (30 - 18 = 12). Заносим операцию в таблицу и получается следующее:

	B1	B2	B3	B4	B5	Запасы Аi
A1	13	7	14	7	5	30
A2	11	8	12	6	8	48
A3	6	10	10	8	11	20
A4	14	8	10	10	15	30
Заявки Bj		27	42	15	26	128

Заявка B1 выполнена, а на складе A1 осталось еще 12т цемента. Значит, их можно отправить по следующей заявке, например B2. Заявка B2 требует 27т, а значит, отправив остатки с A1, еще потребуется добавить 15 т в В2. Следовательно, для выполнения заявки B2, нужно взять цемент с другого склада, например, A2. Операции заносим в таблицу, она будет иметь следующий вид:

	B1	B2	B3	B4	B5	Запасы Аi
A1	13 18	7	14	7	5	30
A2	11	8	12	6	8
A3	6	10	10	8	11	20
A4	14	8	10	10	15	30
Заявки Bj	18		42	15	26	128

Так как со склада A2 было взято 15т цемента, то на нем осталось 48 -15 = 33 т цемента, которые можно использовать для следующих заявок.

Так как на складе A2 осталось еще 33т цемента, отправляем их по заявке B3, которая в свою очередь требует 42т. Остается с следующего склада отправить еще 9т, чтобы полностью закрыть заявку. Тогда на складе A3 остается еще 11т. Вид таблицы:

Теперь 11т отправляем на заявку B4 и еще со склада A4 отправляем 4т на заявку B4. Тогда, на складе A4 остается еще 26т для выполнения последней заявки

Выполняем последнюю заявку: оставшиеся 26т на складе A4 отправляем по заявке B5, получается такая таблица:

План перевозок готов. Теперь требуется проверить, оптимален ли он по количеству перевозок. Вычисляется это по следующей формуле:

M[строк] + N[столбов] – 1 < = [Кол-во перевозок].

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

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

Кол-во перевозок: 8

4 + 5 – 1 = 8

8 <= 8

Следственно, план оптимален.

Теперь вычисляем стоимость. Обведенные числа умножаем и складываем, получается следующее:

L (стоимость перевозки) =

18*13 + 12*7 +15*8+ 33*12 + 9*10 + 11*8 + 4*10 + 26*15 = 1442.

Литература:

Статьи по теме

1) Решение задач различными методами

2) Вычисление оптимальных решений математическими методами

Задачи

Пример 1. На три базы A ₁, A ₂, A ₃ поступил очередной груз в количествах равных 140, 160, 120 ед. Этот груз требуется перевезти в четыре пунктов назначения B ₁, B ₂, B ₃, B ₄ в количествах 150, 90, 100, 80. Тарифы перевозок представлена матрицей: