Методы оптимальных решений (стр. 3 )

Составить математическую модель задачи. Решить задачу геометрически, а также симплекс – методом.

Задание 3. Транспортная задача.

Методические указания

Рассмотрим пример.

3.1 Постановка задачи.

На двух базах Б1 и Б2 находится однородный груз в количестве соответственно: а1 и а2 условных единиц. Этот груз необходимо перевести на три предприятия П1, П2 и П3, потребности которых составляют соответственно b1, b2 и b3 условных единиц. Стоимость перевозки одной условной единицы груза с базы Бi на предприятие Пj составляет cij руб. Эти стоимости указаны в таблице.

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

Базы	Предприятия	Запасы на базах
П1	П2	П3
Б1	3	2	4	840
Б2	2	4	3	600
Потребность предприятий	600	360	480

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

Определим количество груза, отправленного с каждой базы:

(4)

Определим количество груза, доставленное на каждое предприятие:

(5)

Общая стоимость перевозок:

при (4) ,(5) и .

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

,

.

,задача сбалансированная, модель закрытая.

3.3 Решение транспортной задачи

1. Найдем первоначальный опорный план методом северно-западного угла.

Сделаем поставку в клетку (1, 1):

x11 = min (a1, b1) = min (600, 840) = 600. Следовательно, удовлетворяем полностью потребности П1.

Значение 600 вписываем в клетку (1, 1); первый столбец вычеркиваем.

Пересчитываем запас груза на базе Б1, т. е. значение a1: a1 - b1 = 840 – 600 = 240.

Базы	Предприятия	Запасы на базах
П1	П2	П3
Б1	600 3	2	4
Б2	2	4	3	600
Потребность предприятий	600	360	480

Сделаем поставку в клетку (1, 2):

x12 = min (a1, b2) = min (240, 360) = 240. Следовательно, удовлетворяем полностью поставщика Б1.

Значение 240 вписываем в клетку (1, 2); первую строку вычеркиваем.

Пересчитываем потребность П2, т. е. значение b2: b2 - a1 = 360 – 240 = 120.

Базы	Предприятия	Запасы на базах
П1	П2	П3
Б1	600 3	240 2	4	840 240
Б2	2	4	3	600
Потребность предприятий	600	360 120	480

Сделаем поставку в клетку (2, 2):

x22 = min (a2, b2) = min (600, 120) = 120. Следовательно, удовлетворяем полностью потребность П2.

Значение 120 вписываем в клетку (2, 2); второй столбец вычеркиваем.

Пересчитываем запасы груза на Б2, т. е. значение a2: a2 – b2 = 600 – 120 = 480.

Базы	Предприятия	Запасы на базах
П1	П2	П3
Б1	600 3	240 2	4	840 240
Б2	2	120 4	3	600 480
Потребность предприятий	600	360 120	480

Сделаем поставку в клетку (2, 3):

x23 = min (a2, b3) = min (480, 480) = 480. Удовлетворяем полностью потребность П3 и запасы на Б2.

Значение 480 вписываем в клетку (2, 3).

Базы	Предприятия	Запасы на базах
П1	П2	П3
Б1	600 3	240 2	4	840 240
Б2	2	120 4	480 3	600 480
Потребность предприятий	600	360 120	480

План составлен, полностью удовлетворены и поставщики, и потребители.