ZAD803 (Лабораторные работы)

ЗАДАЧА 803

Транспортная задача линейного программирования.

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

xij

Найти  0, максимизирующие функцию:

Z =



n



m

i =1

j =1

cij

xij

..,

при условии:

b ( j = 1, ...m)

= ( i = 1, ... n); =

Алгоритм решения (венгерский метод).

Подготовительный этап.

cij

В каждом столбце матрицы С =( ) ) находим минимальный элемент, который вычитаем из всех элементов данного столбца. Всё то же самое повторяем для строк матрицы С. В результате получим матрицу Со.

Формируем матрицу Хо по столбцам : все элементы матрицы Хо , соответствующие ненулевым элементам матрицы Со, полагаем равными нулю, а остальные элементы определяем так:

хij = min { ai - xil , bj - xlj }

Вычисляем значения:

; .

;

Е сли выполняются условия = 0 и = 0 ; i = 1, ... n;

j = 1, ... m,

то матрица Хо является решением задачи.

Итерационные этапы

1 .Выделяем признаком 1(+) те столбцы матрицы Ск (к =0,1, ....) для которых: = 0.

Элементы выделенных столбцов и строк назовём выделенными.

2.Среди невыделенных элементов выбираем произвольный нуль:

= 0. При отсутствии нуля переходим на пункт 4. В

противном случае рассматриваем два условия:

1) если = 0, то

а) выделяем i - ю строчку матрицы Ск признаком 1(+), а

элемент отмечаем признаком 2(!);

б) просматриваем каждый l -й выделенный столбец матрицы Ск

и если > 0, то признак выделения столбца матрицы Ск

уничтожаем , а элемент отмечаем признаком 3(*);повторяем пункт 2.

2) если > 0, то элемент отмечаем признаком 2(!); и переходим к пункту 3.

3. Образуем в матрице Ск последовательную цепочку от последнего выделенного нуля с признаком 2(!) до нуля с признаком 3(*) по столбцу, затем от нуля с признаком 3(*) до нуля с признаком 2(!) по строке и т.д. Находим число , равное минимуму:

1. всех элементов матрицы Хк , соответствующих элементам с признаком 3(*) матрицы Ск , входящих в цепочку;

1. в еличины , соответствующие первому элементу цепочки;

2. величины , соответствующие последнему элементу цепочки.

Цепочка может содержать только один элемент - последний выделенный нуль.

Число  добавляем ко всем элементам матрицы Хк, стоящим на нечётных местах цепочки, и отнимаем от всех элементов , стоящих на чётных местах. В результате получим матрицу Хк+1.

Число  вычитается из i, где i - строка первого элемента цепочки; число  вычитается из ε^(к)_j где j - столбец последнего элемента цепочки.

Получаем и . Если при этом выполняется условие:

= 0 и = 0 ( i = 1, ...n; j = 1, ... m);

то матрица Хк+1 является решением задачи, в противном случае все признаки матрицы Ск уничтожаем и переходим к пункту 1.

4. Находим число h , равное минимуму среди невыделенных элементов матрицы Ск . Число h отнимаем от всех элементов , не входящих в выделенные строки и столбцы матрицы Ск , и добавляем ко всем элементам , входящим в выделенные строки и столбцы одновременно. В результате получим матрицу Ск+1. Переходим к пункту 2.

Пример для отладки:

_

в=(3 6 2 1)

Решение:

1. Выполняем подготовительный этап:

;

b_j = ( 3 6 2 1 )

⁽_j⁰⁾ = ( 0 1 2 0 )

1. Выполняем пункт 1. и дважды пункт 2.

+ ++

При третьем повторении пункта 2.

переходим к пункту 4.

+

+

+

3

+

. Выполняем пункт 4 .

h = min (2,8,6,6) = 2;

Переходим к пункту 2.

4 . Выполняем пункт 2.

+ Переходим к пункту 3.

5 . Выполняем пункт 3.

 = min (1) = 1

6. Выполняем пункт 1. трижды пункт 2.

+

Переходим к пункту 4.

7. Выполняем пункт 4.

h = min (3,4,4) = 3;

Переходим к пункту 2.

1. В ыполняем пункт 2.

Переходим к пункту 3.

9. Выполняем пункт 3.

 = min (3,3,2,2) = 2;

М атрица Х2 является решением задачи.

Z = 42 .

Результаты счёта

Выдать на печать матрицу Х2 и значение функции.

Окончательный счёт

Z = ?

Z = ?

Z = ?