Определение нового, улучшенного опорного решения транспортной задачи (3-й шаг метода) - Транспортная задача и ее решение методом потенциалов
Специфика транспортной задачи позволяет находить новое опорное решение задачи и новый базис по правилу более простому, чем в симплекс-методе. Пусть найденное опорное решение является невырожденным и пусть для клетки (i0, j0) условие оптимальности нарушено и - одна из положительных оценок (например, наибольшая). Согласно теореме об улучшении опорного решения, мы получим лучшее опорное решение, если вектор введем в базис (в вырожденном случае может появиться прежнее решение). Тогда клетка (i0, j0) станет базисной. Обозначим объем перевозок по маршруту (i0, j0) в новом решении через Q > 0. В клетку (i0, j0) запишем значение перевозки. Теперь суммарный объем перевозок из i0-го пункта стал равен, что невозможно по условиям задачи т. к. нарушен баланс в строке i0 и в столбце j0. Чтобы восстановить баланс в строке i0 перевозку Q надо компенсировать, т. е. надо уменьшить на Q суммарный объем старых базисных перевозок в этой строке. Условимся восстанавливать баланс только за счет уменьшения одной базисной перевозки в строке i0. Пусть, например, мы уменьшаем на Q базисную перевозку, записанную в клетке (i0, j1), в эту клетку запишем "- Q ". Но теперь потребитель j1 получает груз на Q единиц меньше, чем ему требуется, т. е. нарушается баланс по столбцу j1. Чтобы его восстановить, надо увеличить на Q суммарный объем перевозок в этом столбце. Компенсируем это уменьшение за счет увеличения на Q одной только базисной перевозки в столбце j1. Пусть, например, мы увеличиваем на Q перевозку, в клетку (i1, j1) запишем "+ Q ". Тогда, поскольку, нарушается баланс по строке i1, необходимо компенсировать это увеличение за счет уменьшения на Q объема одной базисной перевозки в строке i1. Продолжаем этот процесс баланса по строкам и столбцам до тех пор, пока не восстановим баланс в столбце j0, за счет уменьшения одной базисной перевозки в этом столбце на величину Q. Последовательность клеток (i0, j0), (i0, j1), (i1, j1), ... должна замкнуться на клетке (i0, j0). Будем называть эту цепочку клеток циклом пересчета свободной клетки (i0, j0). Соединяя отрезками прямой последовательные клетки цепочки, мы получим замкнутую ломаную линию, которую также будем называть циклом пересчета. Можно доказать, что если задан некоторый опорный план T. З., то для любой свободной клетки можно построить единственный цикл пересчета. Назовем клетки цепочки, в которые мы записываем "- Q " отрицательными, а в которые "+ Q " - положительными. Определим Q. Будем исходить из того, что значение Q надо взять как можно больше (как в симплекс-методе). Рассмотрим отрицательные клетки. Значение перевозок в таких клетках будет равно xijбаз - Q ? 0. Отсюда следует, что Q надо положить равным наименьшей из перевозок, записанных в отрицательных клетках. Новый опорный план T. З. определяем, увеличивая на Q перевозки, записанные в положительных клетках и уменьшая на Q перевозки, записанные в отрицательных. Клетка (i0, j0), для которой составлен цикл пересчета, становиться базисной. Очевидно, что при этом, по крайней мере, одна из старых базисных перевозок обращается в нулевую, соответствующий ей вектор выводится из базиса и соответствующая клетка становиться свободной.
В общем случае может случиться, что нулевые значения перевозок после вычитания Q получатся в нескольких отрицательных клетках. Тогда только одна из них (любая) будет считаться свободной, остальные отрицательные клетки цепочки будут базисными и в них запишется значение перевозки равное нулю - это так называемые базисные нули. Полученный план будет вырожденным, но число базисных клеток (переменных) для любого спорного плана всегда будет равно: m + n - 1.
В случае улучшения вырожденного опорного плана при построении цикла пересчета может оказаться, что в клетку с базисным нулем будет записано "- Q ". В этом случае значение Q = 0 и новый опорный план, который получим после пересчета не меняется, но меняется состав базисных клеток (переменных); отрицательная клетка с базисным нулем станет свободной, а в клетку, для которой составляли цикл перерасчета, запишем базисной ноль. Вероятность зацикливания в T. З. чрезвычайно мала, поэтому правило предупреждения зацикливания не рассматривается. Переход от одного опорного решения к другому, лучшему в методе потенциалов по существу происходит по правилам симплексного метода. Действительно, в базис вводится вектор, по правилам симплекс-метода (для задачи на минимум). Значение новой базисной переменной, где Q равно минимальному из значений перевозок (базисных переменных), записанных в отрицательных клетках:
(xijбаз из отрицательных клеток) =Q. (1.10)
При решении общей з. л.п. симплекс-методом [] значение новой базисной переменной xs (т. е. значение Q) определяется по формуле:
(1.11)
При решении T. З. симплекс-методом формула (1.11) будет иметь вид:
( xijбаз/) =Q.
Поскольку в T. З. положительные значения коэффициентов, то легко видно, что последняя формула совпадает с формулой (1.10). Таким образом, формула (1.10) является частным случаем формулы (1.11), т. е. последняя применительно к T. З. превращается в формулу (1.10).
Рассмотрим переход к новому опорному решению (3-й шаг метода) в задаче об удобрениях. В табл. 1.7 записано исходное опорное решение, которое следует улучшить. Среди клеток, для которых нарушаются условия оптимальности (1.7), выбираем клетку (1,4) с наибольшей оценкой Д14 = 4 >0. Соответствующую переменную x14 введем в базис, и клетку (1,4) сделаем базисной. Обозначим новый объем перевозок через x14 = Q > 0 и в клетку (1,4) табл. (1.7) запишем "+Q", т. е. перевозку x14 увеличим на "Q". Однако теперь от 1-го поставщика вывозится (100+Q) т. груза, что не возможно по условию задачи. Нарушился баланс в 1-й строке таблицы, одновременно он нарушился и в 4-ом столбце, так как теперь 4-й потребитель получает (200 + Q) т. груза.
Восстановим баланс сначала в т 1-й строке за счет одной базисной клетки и в клетку (1,1) запишем "-Q". т. е. перевозку x11 уменьшаем на Q. Теперь нарушен баланс в 1-ом столбце, восстановим его за счет одной базисной клетки (2,1), в которой запишем "+Q". Далее восстановим нарушенный баланс во 2-ой строке, записав "-Q" в клетку (2,2) и затем во 2-ом столбце, записав "+Q" в клетку (3,2). Затем одновременно восстановим нарушенный баланс в 3-й строке и в 4-ом столбце, записав "-Q" в клетку (3,4). Теперь баланс полностью восстановлен. В результате этих действий получим цепочку клеток (1,4); (1,1); (2,1); (2,2); (3,2); (3,4), которая называется циклом пересчета свободной клетки (1,4). Клетки этой цепочки называются вершинами цикла. Соединим эти клетки отрезками прямых, как показано в табл. 1.7, полученную замкнутую ломаную линию тоже будем называть циклом пересчета. Клетки (вершины) цикла, в которых записано "-Q" будем называть отрицательными, а в которых записано "+Q" - положительными.
При решении конкретных задач могут встретится различные формы циклов (рис.1.1).
Особенности цикла:
- А) цикл единственный, замкнутый; Б) исходная клетка цикла - свободная ее оценка Дij > 0, остальные - базисные; В) если в строке (столбце) таблицы есть положительная (отрицательная) клетка, то в строке (столбце) должна быть отрицательная (положительная) клетка.
Определим значение Q, его надо выбрать так, чтобы перевозки в отрицательных клетках остались неотрицательными и по крайней мере в одной из них перевозка обратилась в нуль.
Для этого приравниваем Q минимальной из перевозок, записанных в отрицательных клетках табл. 1.7. Отрицательными будут клетки (1,1), (2,2), (3,4), в них записаны перевозки: 100, 200 и 200 соответственно, следовательно,
Q = min(100, 200, 200) = 100.
Теперь пересчитаем план перевозок. Перевозки в положительных клетках увеличиваем на 100, в отрицательных - уменьшаем на 100. Клетку (1,1), в которой перевозка обращается в ноль, будем считать свободной, а клетка (1,4) станет базисной. Все остальные клетки таблицы оставляем без изменения. Новый план X2 получим в табл.1.8.
Число базисных клеток: m + n - 1 = 6. Покажем, что новый план лучше предыдущего и вычислим величину изменения целевой функции ?Z. Рассмотрим оценку
?14 = U1 + V4 - c14 .
Перемещая груз Q по циклу, мы изменяем величину целевой функции на следующую величину:
?Z = С14 - Q - c11 - Q + c21 - Q - c22 - Q + c32 - Q - c34 - Q =
= (c14 - c11 + c21 - c22 + c32 - c34 ) - Q. (1.12)
Запишем условия (1.6) для всех клеток цикла пересчета, кроме (1.4), получим:
U1 + V1 = c11
U2 + V1 = c21
U2 + V2 = c22
U3 + V2 = c32
U3 + V4 = c34
Первое, третье и пятое уравнение умножим на " - 1" и затем сложим со вторым и четвертым уравнениями, получим:
- U1 - V4 = - c11 + c21 - c22 + c32 - c34 (1.13)
Подставим (1.13) в (1.12), получим:
?Z = (c14 - U1 - V4) - Q.
Учитывая, что: ?14 = U1 + V4 - c14 , получим "- ?14 = - U1 - V4 + c14 " и тогда
?Z = - ?14 - Q. (1.14)
Так как ?14 > 0, Q > 0, то ?Z = - ?14 - Q < 0 и значение целевой функции уменьшается.
Таблица 1.8
Bj Ai |
300 |
500 |
100 |
200 |
Ui |
100 |
3 Ї |
6 Ї |
5 Ї |
|
U1= 0 |
400 |
|
|
3 Ї |
2 Ї |
U2 = 2 |
600 |
4 Ї |
|
|
|
U3 = 1 |
Vj |
V1 = -1 |
V2 = 2 |
V3 = 0 |
V4 = 1 |
Из таблицы 1.8 выписываем новый план перевозок:
Со стоимостью транспортировки:
Z(X2) = 1-100 + 1-300 + 4-100 + 3-400 + 1-100 + 2-200 = 2300 у. е.
Z(X2) = 2300 < Z(X1) = 2700.
Стоимость транспортировки уменьшилось на величину
ДZ = Z(X1) - Z(X2) = 2700 - 2300 = 400.
Для контроля вычислений величину ДZ можно вычислить по формуле
ДZ = Q -Д14, где Д14 = 4, а Q = 100.
Действительно, ДZ = 100-4 = 400, результат совпадает со значением ДZ, найденным выше, значит, вычисления проведены верно.
Новый опорный план X2 проверяем на оптимальность аналогично тому, как это делалось для плана X1, т. е. для плана X2 выполняем 2-й шаг метода. Для всех базисных клеток табл. 1.8 записываем систему уравнений:
Полагаем U1 = 0 и находим остальное значение потенциалов.
Запишем их в последних строке и столбце табл.1.8. Затем вычисляем значения оценок Дij для свободных оценок:
Д11 = -4 < 0,
Д12 = -4 < 0,
Д13 = -5 < 0,
Д23 = -1 < 0,
Д24 = 1 > 0,
Д31 = -4 < 0.
План X2 не оптимален, так как условия оптимальности нарушены для клетки (2,4). Клетку (2,4) будем считать базисной, и составим для нее цикл пересчета. Выполним это в табл.1.9.
Отрицательными являются клетки (2,2) и (3,4), в них записаны перевозки x22 = x34 = 100.
Вычисляем Q:
Q = min(100;100) = 100.
Аналогично тому, как это было сделано выше, пересчитаем план перевозок, перевозки в отрицательных клетках уменьшаем на Q = 100, а в положительных - увеличиваем на Q = 100.
Нулевые значения перевозок получают в клетках (2,2) и (3,4), поэтому одну из них, например, (2,2), будем считать свободной, а (3,4) - базисной, и запишем в нее базисный ноль, так как клетка (2,4) становится базисной и только одна из отрицательных клеток должна быть свободной. Число базисных клеток для нового плана X3 должно быть равно: m + n - 1 = 6.
В результате этих действий получаем новый план X3, записанный в табл. 1.10.
Таблица 1.10
bj Ai |
300 |
500 |
100 |
200 |
Ui |
100 |
3 Ї |
6 Ї |
5 Ї |
1 100 |
U1= 0 |
400 |
|
4 Ї |
3 Ї |
2 100 |
U2 = 1 |
600 |
4 Ї |
|
1 100 |
|
U3 = 1 |
Vj |
V1 = 0 |
V2 = 2 |
V3 = 0 |
V4 = 1 |
Вычисляем затраты на транспортировку:
Z(X3) = 1-100 + 1-300 + 2-100 + 3-500 + 1-100 = 2200 у. е.;
Z(X3) = 2200 < Z(X2) = 2300.
План X3 является вырожденным, базисная переменная x34 = 0, клетка (3,4) - базисная.
Проверим вычисления:
ДZ = Z(X2) - Z(X3) = 2300 - 2200 = 100.
С другой стороны,
ДZ = Q -Д24 = 100-1 = 100, т. е. расчеты проведены правильно.
План X3 проверяем на оптимальность. Для базисных клеток составляем систему уравнений:
Полагая U1 = 0, находим остальные значения потенциалов, которые записываем в табл.1.10 в соответствующих строке и столбце.
Вычисляем значения оценок Дij для свободных клеток:
Д11 = -3 < 0;
Д12 = -4 < 0;
Д13 = -5 < 0;
Д22 = -1 < 0;
Д23 = -2 < 0;
Д31 = -3 < 0.
Все оценки Дij < 0, значит, план X3 является оптимальным. Вспоминая смысловое содержание задачи, запишем ответ.
Ответ: Первому населенному пункту следует перевезти 300 т удобрений со 2-й станции; второму - 500 т с 3-й станции, третьему - 100 т с 3-й станции и четвертому - 100 т с 1-й и 100 т со 2-й станции. Суммарная минимальная стоимость транспортировки груза составляет 2200 у. е..
Замечание: Процесс пересчета циклов в T. З. всегда конечен, поскольку число способов выбора базисных переменных не более, чем число
- конечное число.
Похожие статьи
-
Транспортная задача оптимальность Поставим в соответствие поставщикам потенциалы Ui, , а потребителям - Vj, . В оптимальном плане для всех базисных...
-
Ранг системы ограничений T. З. равен (m + n - 1), следовательно, невырожденный опорный план Т-задачи содержит (m + n - 1) положительных компонент или...
-
Признак оптимальности плана перевозок T. З. устанавливает теорема. Теорема. Для того, чтобы некоторый допустимый план X = (xij)m-nT. З. был оптимальным,...
-
Вариант №1 1. Выбрать и обосновать наиболее эффективный метод решения задачи. 2. Разработать алгоритм и программу для решения задачи в общем виде. 3....
-
Теорема. Чтобы транспортная задача была разрешима, необходимо и достаточно, чтобы выполнялось условие: (1.5) Доказательство: Необходимость. Пусть...
-
Транспортная задача (Т. З.) является одной из распространенных задач линейного программирования специального вида. Эта задача такого наиболее...
-
Пересчет симплекс-таблицы. - Транспортная задача
Формируем следующую часть симплексной таблицы. Вместо переменной x в план 1 войдет переменная x1 . Строка, соответствующая переменной x1 в плане 1,...
-
Технические требования Техническое задание данной работы требует разработать программу для визуального редактирования HTML-кода. Программа должна быть...
-
Решение задач линейного программирования - Основы информатики
Имеются n пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции с i-го пункта производства в j-ый центр...
-
На рисунке 1 представлен фрагмент электронной таблицы, в которой содержаться исходные данные для решения задачи. Рисунок 1 - Фрагмент электронной...
-
Теоретическая основа линейного программирования, Симплекс метод - Линейное программирование
Симплекс метод Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного...
-
Предложенный подход к решению задач исследования Используя в качестве основы присутствующее в наличии программное обеспечение, которое применимо к...
-
Методика решения задач ЛП графическим методом - Линейное программирование
I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые. II. Найти и заштриховать...
-
Транспортная задача - Линейное программирование
Одна из наиболее распространенных задач математического программирования -- транспортная задача. В общем виде ее можно представить так: требуется найти...
-
Широкое распространение в операционной системе Windows имеет множество стандартных программ обеспечивающих работу устройств компьютера и служащих для...
-
Для решения задачи №3 необходимо ввести исходные данные в электронную таблицу, т. е. таблицы 1,2 (рисунок 16). Рисунок 16 - Ввод исходных данных в...
-
"РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL" Цель работы Приобретение навыков решения задач линейного программирования...
-
Библиотека MSHTML MSHTML (так же известен как Trident) - браузерный движок для Microsoft Internet Explorer. Впервые Trident был реализован в четвертой...
-
Чтобы начать редактировать содержимое ячейки, нужно сначала промаркировать эту ячейку. На следующем шаге необходимо включить режим редактирования, нажав...
-
Задача многокритериальной оптимизации формально представляется как задача нелинейного программирования, включающая: процедуру анализа, выбор управляемых...
-
Обобщенный алгоритм решения задачи Необходимо рассчитать сумму налога на дарение, воспользовавшись налоговой шкалой. Если сумма подарка менее 80, то она...
-
Корпоративная интеграционная подсистема на базе IBM WebSphere Business Integration Message Broker [28] отвечает за выстраивание корпоративной...
-
1. Провести обзор методов автоматического построения профиля нормального поведения веб-приложения. 2. Сформулировать требования к методу, провести...
-
Задача поведенческой сегментации, формирование портретов клиентов по поведению Одними из основных задач анализа являлись: поведенческая сегментация...
-
Выведем в общем виде уравнение движения заданной динамической модели при помощи уравнений Лагранжа II рода. Полная кинетическая энергия: , Полная...
-
Табличный процессор Excel фирмы Microsoft предназначен для ввода, хранения, обработки и выдачи больших объемов, данных в виде, удобном для анализа и...
-
Метод конечных элементов является численным методом для нахождения приближенных решений физических задач. В основе этого метода лежит разделение...
-
Метод конечных элементов (МКЭ) жесткости возник в аэрокосмической отрасли. Исследователи рассматривали различные подходы к анализу сложных частей...
-
Геометрический метод, Двойственная задача - Линейное программирование
Применяется для задач с двумя переменными. Метод решения состоит в следующем: На плоскости строятся прямые, которые задают соответствующие ограничения:...
-
Необходимо исследовать зависимость влияния различных факторов на параметр, характеризующий производство. В качестве такого параметра было выбрано...
-
Решим следующую систему методом Гаусса. - Составление программы для решения системы уравнений
A 11 = 2 0. (1) Для решения систем уравнения с помощью Гаусса будем выделить коэффициенты системы следующим образом: A 11 =2, A 12 = 7, a 13 =13 b 1 = 0...
-
, Алгоритм обратного хода: Шаг 1. Вычислим Шаг 2. Вычислим: , Рис. 1. Основной алгоритм решения СЛУ методом исключения Гаусса. Для контроля правильности...
-
Дана система линейных уравнений (СЛУ) с n неизвестными: В матричной форме записи система (1) имеет вид: (2) Где : n - порядок системы; - матрица...
-
В первом параграфе был проведен краткий анализ организационной структуры ЗАО УК "Отель Менеджмент" гостиница "Холидей Инн Москва Сокольники", которая...
-
Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования,...
-
Постановка задачи: Для заданных функций необходимо: 1. Построить электронную таблицу (одну для обеих функций) для вычисления значений функций в заданном...
-
В качестве доступного инструментария были рассмотрены две открытые кроссплатформенные библиотеки для разработки C++ приложений WxWidgets и Boost ,...
-
Групповые имена. - Приложения технологии системы электронных таблиц Excel к решению задач механики
Предположим, что необходимо вычислить сумму целой группы ячеек. Вместо того чтобы перечислять в формуле отдельные ячейки, промаркируйте всю группу и...
-
Анализ предметной области Описание ПО решаемой задачи Предметной областью задачи № 2 также является процесс оплаты денежных средств по кредиту. Решается...
-
Необходимо построить базу данных, содержащую информацию о ПО, используемом в ЦЗН. В результате анализа предметной области выявляются документы -...
Определение нового, улучшенного опорного решения транспортной задачи (3-й шаг метода) - Транспортная задача и ее решение методом потенциалов