|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Решение стандартной транспортной задачи
Алгоритм решения стандартной транспортной задачи базируется на идее симплексного метода и включает в себя следующие шаги. Шаг 1. Найти начальный опорный план. Перейти к шагу 2. Шаг 2 . Выделить из числа небазисных переменных переменную, вводимую в базис. Если среди небазисных переменных нет таких, ввод которых в базис увеличивает значение целевой функции (условие оптимальности симплекс-метода), закончить вычисления. В противном случае перейти к шагу 3. Шаг 3. Выбрать переменную, выводимую из базиса, используя условие допустимости симплекс-метода. Найти новое базисное решение и вернуться к шагу 2. Рассмотрим, каким образом каждый из этих шагов реализуется при решении транспортной задачи. 2. 1. Определение начального опорного плана Начальный опорный план будем искать для сбалансированной транспортной задачи, т. е. для задачи удовлетворяющей соотношению В силу сбалансированности ранг матрицы ограничений транспортной задачи равен n+m-1, следовательно, любой ее опорный план, в том числе и начальный, должен иметь n+m-1 базисных переменных. В задаче ЛП для получения начального опорного плана используется М-метод или метод искусственного базиса. При значительном числе переменных, что характерно для транспортной задачи, использование обоих этих методов связано с большим объемом вычислений. В транспортной задаче существуют гораздо более простые способы получения начального опорного плана. Для определения начального опорного плана и дальнейшего решения транспортной задачи, она записывается в виде специальным образом организованной транспортной таблицы. Структуру транспортной таблицы разберем на задаче из примера 1. Напомним задачу. В каждом из двух складов сосредоточено по Таблица 7
Крайний левый столбец транспортной таблицы содержит номера складов, верхние строки - номера городов. В крайнем правом столбце указан запас продукта на каждом исходном пункте Ячейки, в которых находится груз, называются занятыми. Им соответствуют базисные переменные. Остальные ячейки незанятые или пустые. Им соответствуют свободные переменные. Способ северо-западного угла. Этот способ является наиболее простым, а потому начальное решение, полученное с его помощью, как правило, уступает решениям, полученным двумя другими способами. Следуя правилу северо-западного угла, припишем переменной Поскольку На этом построение начального опорного плана закончено. Полученный план отображен в таблице 8. Он представляет собой вектор X=(4, 6, 2, 0, 0, 0, 5, 3), значение целевой функции на этом этапе равно 249 ( Таблица 8
1 шаг
2 шаг
3 шаг
3 шаг
3 шаг
Способ наименьшего элемента. При построении начального опорного плана способом северо-западного угла первой переменной назначаемой в качестве базисной всегда является переменная Корректировка выполняется в соответствии с соотношениями: Таблица 9
Анализ данной таблицы показывает, что Следующая базисная переменная выбирается аналогично, но при этом 3 столбец табл.9 не учитывается. Поэтому второй базисной переменной оказывается переменная Шаг 1
Шаг 2
Шаг 3
Шаг 4
Шаг 5
Полученный с помощью способа наименьшего элемента вектор опорного плана оказался равным (4, 6, 0, 2, 0, 0, 7, 1), а значение целевой функции на нем - равным 225. Сравнение значений целевой функции на опорном плане, полученном по методу северо-западного угла, со значением, полученным по способу наименьшего элемента, доказывает, что последний план более близок к оптимальному. Приближенный способ Фогеля. Этот способ является эвристическим. Он, как правило, дает решение близкое к оптимальному или даже оптимальное. Рассмотрим алгоритм нахождения опорного плана приближенным способом Фогеля на той же задаче из примера 1. На первом шаге алгоритма вычисляем штрафы для каждой строки и каждого столбца табл.10, содержащей решаемую задачу. Штраф равен модулю разности между минимальным элементом строки (столбца) и следующим за ним элементам. На втором шаге отметим строку или столбец с самым большим штрафом (если таких строк или столбцов несколько, то выбираем любой из них). Для нашего примера это будет вторая строка со штрафом равным 7. В отмеченной строке или столбце выбираем переменную с самой низкой стоимостью На третьем шаге: а) Если не вычеркнутой останется в точности одна строка или столбец с одним ненулевым б) Если остается не вычеркнутой только одна строка (столбец), с несколькими не равными нулю в) Если всем, не вычеркнутым строкам и столбцам, соответствуют, г) Во всех остальных случаях найти новые значения штрафов для не вычеркнутых строк и столбцов и перейти к шагу 2. Таблица 10 Шаг 1
Шаг 2
Шаг 3
Шаг 4
Вектор опорного плана, построенный с помощью приближенного алгоритма Фогеля, в данном случае оказался равным вектору, построенному способом наименьшего элемента. Решение Популярное:
|
Последнее изменение этой страницы: 2016-07-13; Просмотров: 797; Нарушение авторского права страницы
, где n - число исходных пунктов, m - число конечных пунктов. Поскольку любую транспортную задачу можно сбалансировать, введя фиктивный исходный или конечный пункт, это ограничение не является принципиальным.
однотипных средств. Необходимо перевести эти средства по четырем городам. Каждая j‑ я точка готова принять 
единиц товара. Стоимость перевозки средства из i‑ го склада в j‑ й город равна 
. Составить план, минимизирующий стоимость перевозки. Исходные данные, необходимые для решения задачи указаны в табл. 7, которая и называется транспортной.
- стоимость доставки единицы продукта из i‑ го исходного пункта в j‑ й конечный; в центре клетки - 
- общее количество продукта, доставленное из i‑ го исходного пункта в j‑ й конечный. Рассмотрим три способа построения начального опорного плана: способ северо-западного угла, способ наименьшего элемента и приближенный алгоритм Фогеля.
. Для нашей задачи получим 
. Вычеркнем из таблицы 7 первый столбец, показывая этим, что остальные переменные данного столбца ( 
и 
величину равную 
8, 
. Повторим операцию для переменной 
. Выполнив ту же операцию для 
.
, возможности по отправке продукта из первого исходного пункта исчерпаны. Переходим к элементу 
3‑ го столбца таблицы, и выполним с ним операцию аналогичную описанным выше. Получим 
. Переходим к элементу 
.
).
присваивается значение 
. После этого вычеркивается соответствующий столбец или строка транспортной таблицы и корректируются величины 
и 
.
, аналогично тому, как это делалось в способе северо-западного угла. Процедура повторяется до тех пор, пока не вычеркнутым останется одна строка или один столбец (пока хоть один ai или bj отличается от нуля).
. Следовательно, первая базисная переменная есть переменная 
. Соответственно получим 
.
. На третьем шаге в качестве базисной выбираем переменную 
, а на четвертом шаге - переменную 
, вычеркивая при этом нижнюю строку таблицы 9. Последней базисной переменной оказывается переменная 
, которой соответствует последняя не зачеркнутая клетка таблицы. Как следует из таблицы, 
.
аналогично тому, как это делалось в способе северо-западного угла, вычеркиваем строку или столбец, соответствующие выполненному ограничению (столбец 3).
, закончить вычисления; 