6 задача. Составление первого опорного плана методом северозападного угла

Название	Составление первого опорного плана методом северозападного угла
Дата	10.10.2022
Размер	48.51 Kb.
Формат файла
Имя файла	6 задача.docx
Тип	Документы #725009

Сумма мощностей поставщиков: 230 + 340 + 670 = 1240 больше суммы мощностей потребителей: 256 + 354 + 582 = 1192. Модель задачи открытая. Чтобы привести ее к закрытому типу, вводим фиктивного потребителя Φ с мощностью 1240 – 1192 = 48. В результате модель задачи становится закрытой. Решаем ее методом потенциалов.

Составление первого опорного плана методом северо-западного угла

Составляем первый опорный план методом северо-западного угла. Даем наибольшую поставку 230 в клетку (1, 1). Поставщик A₁ реализовал весь имеющийся у него груз: a₁ = 230. Вычеркиваем строку A₁.

Даем наибольшую поставку 26 в клетку (2, 1). Потребитель B₁ получил требуемое количество груза: b₁ = 230 + 26 = 256. Вычеркиваем столбец B₁.

Даем наибольшую поставку 314 в клетку (2, 2). Поставщик A₂ реализовал весь имеющийся у него груз: a₂ = 26 + 314 = 340. Вычеркиваем строку A₂.

Даем наибольшую поставку 40 в клетку (3, 2). Потребитель B₂ получил требуемое количество груза: b₂ = 314 + 40 = 354. Вычеркиваем столбец B₂.

Даем наибольшую поставку 582 в клетку (3, 3). Потребитель B₃ получил требуемое количество груза: b₃ = 582. Вычеркиваем столбец B₃.

Даем наибольшую поставку 48 в оставшуюся не зачеркнутую клетку (3, 4). Получаем первый опорный план.

Таблица 1.1

	B₁ 256	B₂ 354	B₃ 582	Φ 48
A₁230	4 230	3	8	0
A₂340	7 26	5 314	3	0
A₃670	4	7 40	7 582	0 48

Целевая функция:
F = 4·230 + 7·26 + 5·314 + 7·40 + 7·582 + 0·48 = 7026

Построение оптимального плана

Находим потенциалы u_i, v_j. Для этого нам нужно решить приведенную ниже систему уравнений, используя только заполненные клетки:
u₁ = 0;
u_i + v_j = c_ij.
Полагаем u₁ = 0.
Для клетки (1, 1): v₁ = c_1,1 – u₁ = 4 – 0 = 4;
Для клетки (2, 1): u₂ = c_2,1 – v₁ = 7 – 4 = 3;
Для клетки (2, 2): v₂ = c_2,2 – u₂ = 5 – 3 = 2;
Для клетки (3, 2): u₃ = c_3,2 – v₂ = 7 – 2 = 5;
Для клетки (3, 3): v₃ = c_3,3 – u₃ = 7 – 5 = 2;
Для клетки (3, 4): v₄ = c_3,4 – u₃ = 0 – 5 = -5.
Заносим потенциалы в таблицу 1.2.

Таблица 1.2

	B₁ 256	B₂ 354	B₃ 582	Φ 48	u
A₁230	4 230	3	8	0	0
A₂340	7 26	5 314	3	0	3
A₃670	4	7 40	7 582	0 48	5
v	4	2	2	-5

Находим оценки свободных клеток по формуле:
Δ_ij = c_ij – u_i – v_j.
Δ_1,2 = c_1,2 – u₁ – v₂ = 3 – 0 – 2 = 1;
Δ_1,3 = c_1,3 – u₁ – v₃ = 8 – 0 – 2 = 6;
Δ_1,4 = c_1,4 – u₁ – v₄ = 0 – 0 – (-5) = 5;
Δ_2,3 = c_2,3 – u₂ – v₃ = 3 – 3 – 2 = -2;
Δ_2,4 = c_2,4 – u₂ – v₄ = 0 – 3 – (-5) = 2;
Δ_3,1 = c_3,1 – u₃ – v₁ = 4 – 5 – 4 = -5.
Поскольку есть отрицательные оценки, то план не оптимален.

Наименьшая оценка Δ_3,1 = -5 в клетке (3,1). Вводим ее в базис. Строим цикл для этой клетки. Изображаем его в таблице 1.3. Расставляем знаки ′+′ и ′–′ в вершинах цикла, чередуя их, начиная со знака ′+′ в клетке (3,1).

Таблица 1.3

	B₁ 256	B₂ 354	B₃ 582	Φ 48
A₁230	4 230	3	8	0
A₂340	– 7 26	+ 5 314	3	0
A₃670	+ 4	– 7 40	7 582	0 48

Переходим к следующему опорному плану. Для этого определяем наименьшее значение поставок в вершинах цикла со знаком ′–′. Оно равно 26 в клетке (2,1). Выполняем сдвиг по циклу на величину 26: в клетках, помеченных знаком ′+′, прибавляем 26; в клетках, помеченных знаком ′–′, вычитаем 26. В результате клетка (3,1) входит в базис со значением 26, а клетка (2,1) выходит из базиса.
Получаем таблицу 2.1.

Таблица 2.1

	B₁ 256	B₂ 354	B₃ 582	Φ 48
A₁230	4 230	3	8	0
A₂340	7	5 340	3	0
A₃670	4 26	7 14	7 582	0 48

Целевая функция:
F = 4·230 + 5·340 + 4·26 + 7·14 + 7·582 + 0·48 = 6896

Находим потенциалы u_i, v_j. Для этого нам нужно решить приведенную ниже систему уравнений, используя только заполненные клетки:
u₁ = 0;
u_i + v_j = c_ij.
Полагаем u₁ = 0.
Для клетки (1, 1): v₁ = c_1,1 – u₁ = 4 – 0 = 4;
Для клетки (3, 1): u₃ = c_3,1 – v₁ = 4 – 4 = 0;
Для клетки (3, 2): v₂ = c_3,2 – u₃ = 7 – 0 = 7;
Для клетки (2, 2): u₂ = c_2,2 – v₂ = 5 – 7 = -2;
Для клетки (3, 3): v₃ = c_3,3 – u₃ = 7 – 0 = 7;
Для клетки (3, 4): v₄ = c_3,4 – u₃ = 0 – 0 = 0.
Заносим потенциалы в таблицу 2.2.

Таблица 2.2

	B₁ 256	B₂ 354	B₃ 582	Φ 48	u
A₁230	4 230	3	8	0	0
A₂340	7	5 340	3	0	-2
A₃670	4 26	7 14	7 582	0 48	0
v	4	7	7	0

Находим оценки свободных клеток по формуле:
Δ_ij = c_ij – u_i – v_j.
Δ_1,2 = c_1,2 – u₁ – v₂ = 3 – 0 – 7 = -4;
Δ_1,3 = c_1,3 – u₁ – v₃ = 8 – 0 – 7 = 1;
Δ_1,4 = c_1,4 – u₁ – v₄ = 0 – 0 – 0 = 0;
Δ_2,1 = c_2,1 – u₂ – v₁ = 7 – (-2) – 4 = 5;
Δ_2,3 = c_2,3 – u₂ – v₃ = 3 – (-2) – 7 = -2;
Δ_2,4 = c_2,4 – u₂ – v₄ = 0 – (-2) – 0 = 2.
Поскольку есть отрицательные оценки, то план не оптимален.

Наименьшая оценка Δ_1,2 = -4 в клетке (1,2). Вводим ее в базис. Строим цикл для этой клетки. Изображаем его в таблице 2.3. Расставляем знаки ′+′ и ′–′ в вершинах цикла, чередуя их, начиная со знака ′+′ в клетке (1,2).

Таблица 2.3

	B₁ 256	B₂ 354	B₃ 582	Φ 48
A₁230	– 4 230	+ 3	8	0
A₂340	7	5 340	3	0
A₃670	+ 4 26	– 7 14	7 582	0 48

Переходим к следующему опорному плану. Для этого определяем наименьшее значение поставок в вершинах цикла со знаком ′–′. Оно равно 14 в клетке (3,2). Выполняем сдвиг по циклу на величину 14: в клетках, помеченных знаком ′+′, прибавляем 14; в клетках, помеченных знаком ′–′, вычитаем 14. В результате клетка (1,2) входит в базис со значением 14, а клетка (3,2) выходит из базиса.
Получаем таблицу 3.1.

Таблица 3.1

	B₁ 256	B₂ 354	B₃ 582	Φ 48
A₁230	4 216	3 14	8	0
A₂340	7	5 340	3	0
A₃670	4 40	7	7 582	0 48

Целевая функция:
F = 4·216 + 3·14 + 5·340 + 4·40 + 7·582 + 0·48 = 6840

Находим потенциалы u_i, v_j. Для этого нам нужно решить приведенную ниже систему уравнений, используя только заполненные клетки:
u₁ = 0;
u_i + v_j = c_ij.
Полагаем u₁ = 0.
Для клетки (1, 1): v₁ = c_1,1 – u₁ = 4 – 0 = 4;
Для клетки (1, 2): v₂ = c_1,2 – u₁ = 3 – 0 = 3;
Для клетки (2, 2): u₂ = c_2,2 – v₂ = 5 – 3 = 2;
Для клетки (3, 1): u₃ = c_3,1 – v₁ = 4 – 4 = 0;
Для клетки (3, 3): v₃ = c_3,3 – u₃ = 7 – 0 = 7;
Для клетки (3, 4): v₄ = c_3,4 – u₃ = 0 – 0 = 0.
Заносим потенциалы в таблицу 3.2.

Таблица 3.2

	B₁ 256	B₂ 354	B₃ 582	Φ 48	u
A₁230	4 216	3 14	8	0	0
A₂340	7	5 340	3	0	2
A₃670	4 40	7	7 582	0 48	0
v	4	3	7	0

Находим оценки свободных клеток по формуле:
Δ_ij = c_ij – u_i – v_j.
Δ_1,3 = c_1,3 – u₁ – v₃ = 8 – 0 – 7 = 1;
Δ_1,4 = c_1,4 – u₁ – v₄ = 0 – 0 – 0 = 0;
Δ_2,1 = c_2,1 – u₂ – v₁ = 7 – 2 – 4 = 1;
Δ_2,3 = c_2,3 – u₂ – v₃ = 3 – 2 – 7 = -6;
Δ_2,4 = c_2,4 – u₂ – v₄ = 0 – 2 – 0 = -2;
Δ_3,2 = c_3,2 – u₃ – v₂ = 7 – 0 – 3 = 4.
Поскольку есть отрицательные оценки, то план не оптимален.

Наименьшая оценка Δ_2,3 = -6 в клетке (2,3). Вводим ее в базис. Строим цикл для этой клетки. Изображаем его в таблице 3.3. Расставляем знаки ′+′ и ′–′ в вершинах цикла, чередуя их, начиная со знака ′+′ в клетке (2,3).

Таблица 3.3

	B₁ 256	B₂ 354	B₃ 582	Φ 48
A₁230	– 4 216	+ 3 14	8	0
A₂340	7	– 5 340	+ 3	0
A₃670	+ 4 40	7	– 7 582	0 48

Переходим к следующему опорному плану. Для этого определяем наименьшее значение поставок в вершинах цикла со знаком ′–′. Оно равно 216 в клетке (1,1). Выполняем сдвиг по циклу на величину 216: в клетках, помеченных знаком ′+′, прибавляем 216; в клетках, помеченных знаком ′–′, вычитаем 216. В результате клетка (2,3) входит в базис со значением 216, а клетка (1,1) выходит из базиса.
Получаем таблицу 4.1.

Таблица 4.1

	B₁ 256	B₂ 354	B₃ 582	Φ 48
A₁230	4	3 230	8	0
A₂340	7	5 124	3 216	0
A₃670	4 256	7	7 366	0 48

Целевая функция:
F = 3·230 + 5·124 + 3·216 + 4·256 + 7·366 + 0·48 = 5544

Находим потенциалы u_i, v_j. Для этого нам нужно решить приведенную ниже систему уравнений, используя только заполненные клетки:
u₁ = 0;
u_i + v_j = c_ij.
Полагаем u₁ = 0.
Для клетки (1, 2): v₂ = c_1,2 – u₁ = 3 – 0 = 3;
Для клетки (2, 2): u₂ = c_2,2 – v₂ = 5 – 3 = 2;
Для клетки (2, 3): v₃ = c_2,3 – u₂ = 3 – 2 = 1;
Для клетки (3, 3): u₃ = c_3,3 – v₃ = 7 – 1 = 6;
Для клетки (3, 1): v₁ = c_3,1 – u₃ = 4 – 6 = -2;
Для клетки (3, 4): v₄ = c_3,4 – u₃ = 0 – 6 = -6.
Заносим потенциалы в таблицу 4.2.

Таблица 4.2

	B₁ 256	B₂ 354	B₃ 582	Φ 48	u
A₁230	4	3 230	8	0	0
A₂340	7	5 124	3 216	0	2
A₃670	4 256	7	7 366	0 48	6
v	-2	3	1	-6

Находим оценки свободных клеток по формуле:
Δ_ij = c_ij – u_i – v_j.
Δ_1,1 = c_1,1 – u₁ – v₁ = 4 – 0 – (-2) = 6;
Δ_1,3 = c_1,3 – u₁ – v₃ = 8 – 0 – 1 = 7;
Δ_1,4 = c_1,4 – u₁ – v₄ = 0 – 0 – (-6) = 6;
Δ_2,1 = c_2,1 – u₂ – v₁ = 7 – 2 – (-2) = 7;
Δ_2,4 = c_2,4 – u₂ – v₄ = 0 – 2 – (-6) = 4;
Δ_3,2 = c_3,2 – u₃ – v₂ = 7 – 6 – 3 = -2.
Поскольку есть отрицательная оценка, то план не оптимален.

Наименьшая оценка Δ_3,2 = -2 в клетке (3,2). Вводим ее в базис. Строим цикл для этой клетки. Изображаем его в таблице 4.3. Расставляем знаки ′+′ и ′–′ в вершинах цикла, чередуя их, начиная со знака ′+′ в клетке (3,2).

Таблица 4.3

	B₁ 256	B₂ 354	B₃ 582	Φ 48
A₁230	4	3 230	8	0
A₂340	7	– 5 124	+ 3 216	0
A₃670	4 256	+ 7	– 7 366	0 48

Переходим к следующему опорному плану. Для этого определяем наименьшее значение поставок в вершинах цикла со знаком ′–′. Оно равно 124 в клетке (2,2). Выполняем сдвиг по циклу на величину 124: в клетках, помеченных знаком ′+′, прибавляем 124; в клетках, помеченных знаком ′–′, вычитаем 124. В результате клетка (3,2) входит в базис со значением 124, а клетка (2,2) выходит из базиса.
Получаем таблицу 5.1.

Таблица 5.1

	B₁ 256	B₂ 354	B₃ 582	Φ 48
A₁230	4	3 230	8	0
A₂340	7	5	3 340	0
A₃670	4 256	7 124	7 242	0 48

Целевая функция:
F = 3·230 + 3·340 + 4·256 + 7·124 + 7·242 + 0·48 = 5296

Находим потенциалы u_i, v_j. Для этого нам нужно решить приведенную ниже систему уравнений, используя только заполненные клетки:
u₁ = 0;
u_i + v_j = c_ij.
Полагаем u₁ = 0.
Для клетки (1, 2): v₂ = c_1,2 – u₁ = 3 – 0 = 3;
Для клетки (3, 2): u₃ = c_3,2 – v₂ = 7 – 3 = 4;
Для клетки (3, 1): v₁ = c_3,1 – u₃ = 4 – 4 = 0;
Для клетки (3, 3): v₃ = c_3,3 – u₃ = 7 – 4 = 3;
Для клетки (2, 3): u₂ = c_2,3 – v₃ = 3 – 3 = 0;
Для клетки (3, 4): v₄ = c_3,4 – u₃ = 0 – 4 = -4.
Заносим потенциалы в таблицу 5.2.

Таблица 5.2

	B₁ 256	B₂ 354	B₃ 582	Φ 48	u
A₁230	4	3 230	8	0	0
A₂340	7	5	3 340	0	0
A₃670	4 256	7 124	7 242	0 48	4
v	0	3	3	-4

Находим оценки свободных клеток по формуле:
Δ_ij = c_ij – u_i – v_j.
Δ_1,1 = c_1,1 – u₁ – v₁ = 4 – 0 – 0 = 4;
Δ_1,3 = c_1,3 – u₁ – v₃ = 8 – 0 – 3 = 5;
Δ_1,4 = c_1,4 – u₁ – v₄ = 0 – 0 – (-4) = 4;
Δ_2,1 = c_2,1 – u₂ – v₁ = 7 – 0 – 0 = 7;
Δ_2,2 = c_2,2 – u₂ – v₂ = 5 – 0 – 3 = 2;
Δ_2,4 = c_2,4 – u₂ – v₄ = 0 – 0 – (-4) = 4.
Поскольку отрицательных оценок нет, то план оптимален.

Ответ

Наименьшее значение целевой функции:
F_min = 5296.
Оптимальный план указан в следующей таблице.

Оптимальный план

	B₁ 256	B₂ 354	B₃ 582	Φ 48
A₁230	4	3 230	8	0
A₂340	7	5	3 340	0
A₃670	4 256	7 124	7 242	0 48