Лекции по линейному программированию
1 1 1 1 1 1 1 1 1 1 Рейтинг 4.00 (1 Голос)

Как и в других задачах ЛП, итерационный процесс отыскания оптимального плана транспортной задачи начинается с какого-либо опорного плана. Опорный план Т-задачи строим в виде матрицы размеров Заполненные позиции матрицы, то есть, в которых , соответствуют базисным переменным. Для невырожденного опорного плана их количество равно где Ранг[1] матрицы системы ограничений.

Начальный опорный план может быть построен, например, методом Северо-западного угла[2].

Определим элементы матрицы начиная с верхнего левого угла. Находим величину Если , то , и первый столбец закрыт для расчета остальных элементов, то есть . Если , то , и первый столбец закрыт для расчета остальных элементов, то есть .

Затем вычисляем

при ,

Либо

при .

Этот процесс продолжается до тех пор, пока на каком-то этапе не исчерпаются ресурсы и не удовлетворятся потребности .

Существуют и другие методы определения начального плана перевозок.

Метод минимального элемента.

В методе минимального элемента просматриваются клетки таблицы в порядке возрастания стоимости перевозок и таким же образом, как и в методе Северо-западного угла удовлетворяются потребности потребителей за счет запасов поставщиков, вычеркиваются строки (столбцы) таблицы Т-задачи. Метод дает иногда лучшее начальное приближение, чем метод Северо-западного угла.

Метод аппроксимации (метод Фогеля).

Метод аппроксимации Фогеля при выборе клетки учитывает не только минимальную величину стоимости перевозок, но и возможные ее увеличения в случае выбора другой клетки строки (столбце). Для этого используют "штрафы" строк и столбцов. Штраф строки (столбца) равен разности первой стоимости (большей минимальной стоимости в строке (столбце)) и минимальной стоимости в данной строке (соответственно столбце). Затем из всех строк и столбцов выбирается строка или столбец с максимальным штрафом и в нем ( в ней) выбирается клетка с минимальной стоимостью. Эта клетка будет соответствовать базисной переменной. Если остается не вычеркнутой одна строка или столбец, то клетки в ней выбираются по методу минимального элемента. Метод Фогеля обычно дает решение, близкое к оптимальному.

Метод двойного предпочтения.

Если таблица стоимости велика, то перебор всех элементов затруднителен. В этом случае используют метод двойного предпочтения, суть которого заключается в следующем.

В каждом столбце отмечают знаком * клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки будут иметь отметку **. В них находится минимальная стоимость как по строке, так и по столбцу. Тогда в них помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по клеткам, отмеченным знаком *. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.

Полученный таким образом план может оказаться неоптимальным, то есть значение целевой функции, получаемое в соответствии с ним, может быть уменьшено за счет некоторых эквивалентных преобразований системы ограничений и перехода к другим смежным решениям Т-задачи, как задачи ЛП. В основе таких переходов лежит так называемый метод Потенциалов, идея которого состоит в улучшении начального опорного плана до тех пор, пока не будет удовлетворяться некий признак оптимальности.

Алгоритм метода потенциалов решения Т-задачи состоит из предварительного этапа и конечного числа итераций.

На предварительном этапе метода потенциалов мы уже получили некоторый начальный план перевозок. Назовем его . Затем для этого плана рассчитывают оценочную матрицу

Где Потенциалы пунктов отправления и пунктов назначения соответственно.

Предварительные потенциалы выбирают таким образом, чтобы для связанных Коммуникациями пар пунктов, для которых в плане , сумма потенциалов была равна :

Если матрица не содержит отрицательных элементов, то - оптимальный план. В противном случае, план можно улучшить.

Описание алгоритма решения Т-задачи.

10. Предварительный этап:

Определяется начальный опорный план одним из указанных выше способов (например, методом северо-западного угла).

20. Первый шаг:

Вычисляется оценочная матрица . Для расчета всех элементов матрицы необходимо сначала определить все потенциалы. Далее строится схема перевозок, соответствующая начальному опорному плану , то есть соединяем коммуникациями пункты отправления и пункты назначения, для которых . Пользуясь выше указанными соотношениями для определения потенциалов по базисным клеткам, определяем последовательно все потенциалы пунктов отправления и назначения, принимая для удобства . Затем пересчитываем стоимости в небазисных клетках таблицы издержек. Очевидно, что позиции матрицы , отвечающие базисным элементам плана , будут заняты нулями.

30. Итерации:

·  Я итерация. Если в оценочной матрице все элементы неотрицательны, то план - оптимальный, в противном случае следует приступить к его улучшению;

·  выбирается наибольший по абсолютной величине отрицательный элемент оценочной матрицы и, начиная с соответствующего ему элемента , в матрице строится замкнутая цепочка[3], в которую входят элементы ;

·  строится новый план , прибавляя: (минимальный элемент выбирается из только из тех элементов, которые связаны цепочкой) ко всем четным элементам цепочки и вычитая из нечетных[4]. Элементы матрицы , не входящие в цепочку, переносятся в матрицу без изменения;

·  далее с помощью эквивалентных преобразований (элементарные преобразования Гаусса) на основе матрицы строится матрица для нового плана . Для этого необходимо выделить в матрице все элементы, соответствующие ненулевым элементам плана (они обязательно равны нулю). В матрице вычеркивается строка, содержащая элемент . Если в этой строке имеются выделенные элементы, то вычеркиваются соответствующие этим элементам столбцы. Если в каждом вычеркнутом столбце присутствуют выделенные элементы, то далее вычеркиваются им соответствующие строки и так далее, до тех пор пока описанная процедура выполнима. После этого ко всем элементам вычеркнутых строк прибавляется величина равная , а из элементов вычеркнутых столбцов эта величина вычитается. Таким образом получается новая оценочная матрица. Если в матрице нет отрицательных элементов, то план на этом шаге оптимален. В противном случае необходимо выполнить еще одну итерацию.

На этом итерации завершаются.

ПРИМЕР: Пусть даны: матрица транспортных издержек , объемы производства и объемы потребления

         

А

 

1

2

9

7

60

С

3

4

1

5

55

 

6

4

8

3

40

 

2

3

3

1

35

В

70

5

45

70

 

Решение начинаем с проверки баланса: Далее, строим начальный опорный план по методу северо-западного угла:

60

0

0

0

10

5

40

0

0

0

0

35

0

0

0

35

Приступаем к вычислению потенциалов. В таблице издержек для удобства выделим клетки соответствующие плану перевозок.

1

2

9

7

3

4

1

5

6

4

8

3

2

3

3

1

По соответствующим маршрутам плана указываем стоимость перевозки единицы груза из Го пункта отправки в Й пункт потребления. Принимаем (можно выбрать любое число) и, пользуясь соотношением: определяем потенциалы

И так далее.

         

 

1

2

9

7

0

 

3

4

1

5

2

 

6

4

8

3

9

 

2

3

3

1

7

1

2

-1

-6

 

Далее рассчитываем элементы оценочной матрицы по соотношениям:

И так далее.

Таким образом

Поскольку в имеются отрицательные элементы, - план не является оптимальным.

Приступаем к итерациям. В матрице , начиная с элемента , соответствующего в оценочной матрице наибольшему по абсолютной величине отрицательному элементу, строим цепочку.

60

 

0

   

0

 

0

 

5

       

40

 

10

 

   

+

 

0

               
               

0

 

+

   

 

35

 

0

       

5

 

0

 

0

   

0

 

35

Изменяя элементы, входящие в цепочку, на величину строим новый план перевозок

60

0

0

0

10

0

35

0

0

5

0

35

0

0

0

35

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

         

 

1

2

9

7

0

 

3

4

1

5

2

 

6

4

8

3

2

 

2

3

3

1

0

1

2

-1

1

 

И далее строим оценочную матрицу:

В оценочной матрице нет отрицательных элементов, следовательно, план является оптимальным. Таким образом, остается оценить стоимость перевозки в условных единицах.

На этом решение задачи завершается.

 

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Имеется три пункта поставки однородного груза и пять пунктов потребления этого груза. В пунктах поставки находится груз в количествах и соответственно. В пункты потребления необходимо доставить груз в количествах соответственно . Издержки на транспортировку единицы груза из пунктов поставки в соответствующие пункты потребления сведены в таблицу - матрицу издержек .

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

I.

.

II.

.

III.

.

IV.

.

V.

.

VI.

.

VII.

.

VIII.

.

IX.

.

X.

.

 

[1] Количество линейно независимых строк или столбцов матрицы. Напомним, что существует и другое определение ранга матрицы (тоже и линейного оператора) - это порядок ее базисного минора.

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

[3] Ломаная линия с вершинами в отмеченных (базисных) клетках плана перевозок.

[4] Нумерация элементов цепочки начинается с элемента, соответствующего максимальному по абсолютной величине отрицательному элементу оценочной матрицы.

Метод определения начального опорного плана перевозок - 4.0 out of 5 based on 1 vote

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство