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

Занятых клеток 4, и по условию N = 2+3-1 = 4.

Значит, план опорный.

Клетки, в которых помещаются грузы, называются занятыми, им соответствуют базисные переменные. Остальным клеткам (незанятым) соответствуют свободные переменные.

2. Вычислим стоимость перевозки.

.

3. Проверим план па оптимальность.

Найдем потенциалы ui и vj из условия для :

(ui соответствует строка, vj - столбец),

для x11:

для x12:

для x22:

для x23:

Система содержит 4 уравнения и 5 неизвестных, следовательно, система имеет бесконечно много решений. Одну переменную можно выбрать произвольно (потенциал строки или столбца с наибольшим количеством занятых клеток). Пусть v2 = 0.

u1 = 2

v1 = 3 – u1 = 3 – 2 = 1

u2 = 4 – v2 = 4

v3 = 3 – u2 = 3 – 4 = –1

Вычислим оценки свободных клеток:

Dij = ui + vj - cij

D13 = u1 + v3 – c13 = 2+(-1)-4 = -3

D21 = u2 + v1 – c21 = 4+1-2 = 3

4. Делаем выводы.

План не оптимален, т. к. имеются положительные оценки Dij.

Наибольшую экономию можно получить по клетке, где наибольшее значение Dij из положительных.

Клетку (2, 1) необходимо загрузить.

5. Делаем переход к следующему лучшему (не худшему) плану.

Строим означенный цикл:

Базы	Предприятия
П1	П2	П3
Б1	600 3	240 2	4
Б2	2	120 4	480 3

Анализируем клетки со знаком «минус» и выбираем клетку с минимальным объемом перевозок.

Q = min{xij} = min(x11, x22) = 120.

Прибавляем данное число к вершинам с «+», вычитаем из вершин с «-».

0+120

120-120

360

480

0

120

Новый план:

.

Внесем в таблицу полученные поставки:

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

6. Повторим проверку плана на оптимальность.

Пусть , тогда

Оценки:

Данный план оптимальный.

Вычислим стоимость перевозки:

L(Xопт) = 3 × 480+2 × 360+4 × 0+2 × 120+4 × 0+3 × 480 = 3840.

Ответ: , L(Xопт) = 3840.

Задание

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

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

Базы	Предприятия	Запасы на базах
П1	П2	П3	П4	П5
Б1 Б2 Б3	c11 c21 c31	c12 c22 c32	c13 c23 c33	c14 c24 c34	c15 c25 c35	а1 а2 а3
Потребность предприятий	b1	b2	b3	b4	b5

Составить математическую модель сформулированной задачи. Решить задачу при следующих данных:

a1 = 920 + 2k; a2 = 780 + 3k; a3 = 840 + 4k;

b1 = 510 + 3k; b2 = 480 + 2k; b3 = 470 + k;

b4 = 530 + 2k; b5 = 550 +k.

Матрица стоимости перевозок имеет вид:

где k – номер варианта,
m равно остатку от деления k на три.