Тема: Решение транспортной задачи средствами ЭТ Excel

Цель:

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

2. Освоить порядок решение задачи средствами ЭТ Excel

3. Научиться анализировать полученные оптимальные решения

Теоретические сведения

1.1 Транспортная задача

Постановка транспортной задачи:

Некоторый однородный продукт, сосредоточенный у М поставщиков в количестве ai (i = 1…. M) единиц соответственно, необходимо доставить N потребителям в количестве bj (j=1… N). Известна стоимость Сij перевозки единицы груза от i – го поставщика к j – ому потребителю. Необходимо составить план перевозок, позволяющий вывезти все грузы, полностью удовлетворить потребности и имеющий минимальную стоимость.

Математическая модель:

X_ij ¾ количество единиц груза

Целевая функция:

 

(5.1)

 

Система ограничений:

- все грузы вывезены

(5.2)

 

 

- все потребности удовлетворены

 

(5.3)

 

Граничные условия Xij ³ 0

Прежде чем решать транспортную задачу, необходимо сначала определить, к какому типу она принадлежит.

Типы моделей

 

1. Модель закрытая

(5.4)

 

2. Модель открытая

2.1. Суммарные запасы превышают суммарные потребности

(5.5)

 

Решение: Вводим фиктивного потребителя, потребности которого равны

(5.6)

 

2.2. Суммарные потребности превышают суммарные запасы

(5.7)

 

Решение: Вводим фиктивного поставщика, объем производства которого

равен

(5.8)

 

 

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

Рассмотрим несколько примеров.

Пример 1

Суммарный объем потребностей больше суммарного объема производства. Потребности некоторых потребителей обязательно должны быть удовлетворены полностью.

Решение:

- Ввести фиктивного поставщика

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

Пример 2

Суммарный объем производства больше суммарного объема потребностей. От некоторых поставщиков нужно вывести всю продукцию.

Решение:

- Ввести фиктивного потребителя

- Стоимость перевозки от поставщика к фиктивному потребителю, установить значительно большими любой из стоимости перевозок решаемой задачи или заблокировать эти клетки.

Пример 3

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

Решение: Заблокировать клетки

 

1.2 Задача оптимального назначения

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

Пусть, имеются М лиц ai (i=1…M), которые могут выполнять bj (j=1…M) видов различных работ. Известна производительность i – го лица при выполнении j – ой работы Сij. Необходимо определить, кого и на какую работу следует назначить, что бы добиться максимальной суммарной производительности при условии, что каждое лицо может быть назначено только на одну работу.

Математическая модель:

Xij ¾ назначение i – го лица на j ¾ ю работу.

Xij принимает значение “0” или “1”. (“0” – не назначен; “1” – назначен).

Целевая функция:

(5.9)

Система ограничений:

(5.10)

Граничные условия Xij ³0

 

Пример выполнения лабораторной работы

2.1 Постановка транспортной задачи

Составить план перевозки песка из пунктов отправления: песчаный карьер №1, железнодорожная товарная станция, речной грузовой порт, песчаный карьер №2, в пункты назначения ЖБИ №1, ЖБИ №2, ДСК, при котором затраты на перевозку будут минимальными; затраты на перевозку 1 т песка между пунктами отправления и назначения указаны в таблице исходных данных в км. Потребности ДСК должны быть удовлетворены полностью.

Математическая модель

Таблица 5.1 – Таблица исходных данных

Поставщик bj	Потребитель	Запас   ai
ЖБИ №1	ЖБИ №2	ДСК
Песчаный карьер №1	11 x11	x12	x13
Ж/д станция	x21	x22	x23
Речной порт	x31	x32
Песчаный карьер №1	x41	x42	x43
Фиктивный поставщик	x51	x52
Заявки

 

Определим тип модели.

Следовательно, модель открытого типа. Для решения задачи необходимо ввести фиктивного поставщика, а также учесть, что потребности ДСК должны быть удовлетворены полностью, запретив перевозку Фиктивный поставщик – ДСК.

Целевая функция:

W = 11 X11+15 X12+ 17 X13+ 12 X21+ 16 X22+ 14 X23+ 13 X31 +10 X32 +9 X33+ 14 X41+ 9 X42 + 11 X43 + 0 X51 + 0 X52 ® min

Система ограничений:

Ø все потребности удовлетворены

 

Ø все запасы вывезены

 

Граничные условия Xij ³0

 

Решение задачи

Решение транспортной задачи и задачи о назначении проводится по алгоритмам 1.1, 1.2, 1.3 из лабораторной работы № 1 «Решение задач линейного программирования средствами ЭТ Excel».

На рисунке 5.1 представлена форма для решения задачи с введенными в нее исходными данными. Результаты поиска решения приведены на рисунке 5.2.

Ответ:

x11= 110 x12=0 x13=0

x21= 40 x22=0 x23=160

x31= 0 x32=20 x33=60

x 41= 0 x42=100 x43=0

x51= 0 x52=50

Целевая функция: W=5680

 

Вывод:

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

Песчаный карьера №1 ¾ ЖБИ №1 110 т песка

Ж/д станция ¾ ЖБИ №1 40 т песка

Ж/д станция ¾ ДСК 160 т песка

Речной порт ¾ ЖБИ №2 20 т песка

Речной порт ¾ ДСК 60 т песка

Песчаный карьер №2 ¾ ЖБИ №2 100 т песка

Потребности ДСК и ЖБИ №1 удовлетворены полностью, для ЖБИ №2 недопоставка составит 50 т песка.

 

Рисунок 5.1

 

Рисунок 5.2

 

 

Задание

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

- Составить и решить задачу о назначении.

 

Требования к отчету по лабораторной работе

Отчет должен содержать:

1. Словесное описание условия задачи

2. Таблицу исходных данных

3. Математическую модель

4. Результаты решения задачи

5. Выводы по решению задачи

 

 

Лабораторная работа N 6