Задача классическая. Метод мини-матриц icon

Задача классическая. Метод мини-матриц



НазваниеЗадача классическая. Метод мини-матриц
Дата17.10.2016
Размер
ТипЗадача

Транспортная задача классическая.

Метод мини-матриц

Замечание:

Все выкладки, приведённые в данной статье, соответствуют направленности решения задачи на минимум. В противном случае, каждый контекст на тему min-max необходимо поменять на зеркально - противоположный.

Однородный груз сосредоточен у m поставщиков в объемах a1, a2, …, am. Данный груз необходимо доставить n потребителям в объемах b1, b2, …, bn. Известны cij, i = 1, 2, …, m, j = 1, 2, …, n – стоимости перевозки единицы груза от каждого i – го поставщика каждому j – му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков будут вывезены полностью, а запросы всех потребителей будут полностью удовлетворены при минимальных затратах на перевозку всех грузов.

Исходные данные транспортной задачи обычно записываются в табличном виде (табл.1).

Таблица 1

bj

ai

b1

b2



bn

a1

c11

c12



c1n

a2

c21

c22



c2n











am

cm1

cm2



cmn



i = 1, 2, …, m, (1)

j = 1, 2, …, n, (2)

xij 0, i = 1, 2, …, m, j = 1, 2, …, n, (3)

В транспортных задачах под поставщиками и потребителями понимаются различные промышленные и сельскохозяйственные предприятия, заводы, фабрики, склады, магазины и т.п. Однородными считаются грузы, которые могут быть перевезены одним видом транспорта. Под стоимостью перевозок понимаются тарифы, расстояния, время, расход топлива и т.п.


^ Сущность метода

Рассмотрим мини-матрицу, т.е. матрицу размерностью 2х2 (рис.1).

Пусть исходные данные для решения транспортной задачи (она обычно решается на минимум) представлены такой матрицей (рис.2). Очевидно, что в схему оптимального решения войдут её элементы x11 и x22 (дополнительно - x21).


x11 · 10 + x22 · 15+ x21 · 5 < x12 · 10+ x21 · 15 + x22 · 5 т.е.


1 · 10 + 2 · 15+ 4 · 5 < 3 · 10+ 4 · 15 + 2 · 5 т.е. 60 < 100

безымянный5.jpgбезымянный6.jpg

Рис.1 Рис.2


Исходная матрица любой размерности имеет мини-матриц определённое количество, рассчитываемое по формуле:


Кмм = ( ) · ( ) (1.1)

где m – количество строк;

n – количество столбцов.

Нетрудно теперь согласиться с утверждением, что в оптимальной схеме решения задачи не должно присутствовать ни одной мини-матрицы, частное решение которой идёт вразрез с направленностью решения задачи в целом.

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


Примечание: Мини-матрицы могут быть квадратными или вытянутыми по строке (столбцу).


Алгоритм решения:

Для получения начального опорного плана используем любой из известных методов. К примеру, метод минимальной стоимости.

1. Составляем начальное опорное решение методом минимальной стоимости.

2. Проверка опорного плана на наличие мини-матриц, имеющих направленность частного решения, идущую вразрез с направленностью решения задачи в целом.

3. В случае, если таковых нет, данный опорный план считается оптимальным, после чего переходим к пункту 5.

4. В случае, если такая мини-матрица имеется, внутри неё проводится переназначение с целью изменения её направленности в нужную сторону. При этом, таких мини-матриц может оказаться не одна, а несколько (они могут перекрывать одна другую). В этом случае для коррекции выбирается та, от которой эффект корректировки получаем наибольший. Если же мини-матрицы не пересекаются, то их коррекцию можно делать одновременно. После чего переходим к выполнению пункта 2. И так до тех пор, пока в очередном опорном плане ни одной такой мини-матрицы присутствовать не будет. Тогда переходим к пункту 5.

5. Проверка оптимальности опорного плана методом потенциалов.

Стоит отметить, что этот пункт является формальным, т.к. после полного устранения “вредных” мини-матриц опорный план непременно оптимален.

6. Оформление плана решения и вычисление целевой функции.


Примеры

Примечание: В ниже следующих примерах показано действие лишь 2, 3 и 4 пунктов алгоритма, т.к. с описанной в них информацией широкий читатель (а может быть и просто читатель) не знаком в отличие от 1, 5 и 6 пунктов, теория по которым достаточно широко представлена как в массовой научной литературе, так и в Интернете. В связи с этим все задачи начинаются с уже готового опорного плана.

Пример 1. Решить транспортную задачу на минимум методом мини- матриц (рис.3):

В начальном опорном плане (рис.3) красной пунктирной линией выделена единственная “вредная ” мини-матрица (12-14-22-24): sp < sa или (5 + 3) < (3 + 8). Значит, в этой мини-матрице между её элементами необходимо осуществить корректировку назначений в допустимых границах цены корректировки. Допустимая цена корректировки в этом случае равна 10. Проделав эту операцию, получим новый опорный план (рис.4), в котором отсутствуют “вредные” мини-матрицы. Значит, он оптимальный.

безымянный8.jpg

Рис.3 Рис.4

Пример 2. Решить транспортную задачу на минимум методом мини- матриц (рис.5):

безымянный14.jpg

Рис.5 Рис.6

В начальном опорном плане (рис.5) красной пунктирной линией выделены единственные две “вредные” мини-матрицы: 22-25-42-45, где sp = sa или (2 + 7) = (0 + 9), и 21-25-31-35, где sp < sa или (4 + 1) < (0 + 8). Эффективность второй равна 3, т.е. большей, чем 0 (как у первой). Поэтому её и корректируем в пределах допустимой цены коррекции. А она здесь имеет значение 10. В результате получим новый опорный план, изображенный на рисунке 6. После его проверки выясняется, что в нём по-прежнему присутствует “вредная” мини-матрица: 21-22-41-42, где sp < sa или (2 + 8) < (4 + 9), Значит, в этой мини-матрице между её элементами необходимо осуществить корректировку назначений в допустимых границах цены корректировки. Допустимая цена корректировки в этом случае равна 10.

Читатель, очевидно, успел заметить, что все элементы этой мини-матрицы уже имеют назначения, т.е. формально все они имеют статус активных. В этом случае элементы 22 и 41 целесообразно назвать обделёнными, а соотношение уже можно представить как (so – сумма обделённых элементов):

so < sa или (2 + 8) < (4 + 9)

Осуществив корректировку, получим новый опорный план (рис.7), откуда видно, что он не содержит ни одной “вредной” мини-матрицы. Значит данный план оптимален.

безымянный16.jpg

Рис.7

Пример 3. Решить транспортную задачу на минимум методом мини- матриц (рис.8):

безымянный17.jpg

Рис.8 Рис.9

В начальном опорном плане (рис.8) красными пунктирными линиями выделены две непересекающиеся единственные “вредные ” мини-матрицы (12-14-22-24 и 31-33-41-43): в первой sp < sa или (5 + 3) < (8 + 3), во второй sp < sa или (2 + 3) < (1 + 5). Значит, в этих мини-матрицах (причём, одновременно, т.к. они не пересекаются) необходимо скорректировать назначения в пределах допустимой цены коррекции каждой из них. В обоих случаях она равна 10. Проделав эту операцию, получим новый опорный план (рис.9), который вследствие отсутствия “вредных” мини-матриц будет оптимальным.

Конец статьи.




Похожие:

Задача классическая. Метод мини-матриц iconЗадача о назначениях
Занятая строка. Занятый столбец. Незанятый элемент. Ноль со звездочкой. Ноль со штрихом. Преобразование матриц. Цепочка. Переход...
Задача классическая. Метод мини-матриц iconЛекция по теме «Двумерные массивы. Теория матриц». Достоинством занятия в форме лекции является возможность изложить большой по объему и сложный материал, раскрыть основные идеи, дать основные понятия
«Задача макси/мин», «Сортировка массивов», а также урок – лекция по теме «Двумерные массивы. Теория матриц». Достоинством занятия...
Задача классическая. Метод мини-матриц iconМетод аппроксимирующей прямой в задача
Метод аппроксимирующей прямой в задачах определения корней и экстремумов непрерывных функций (*)
Задача классическая. Метод мини-матриц iconЛекция Метод Монте-Карло Тема Процессы массового обслуживания в экономических системах
Метод статистического моделирования на ЭВМ основной метод получения результатов с помощью имитационных моделей стохастических систем,...
Задача классическая. Метод мини-матриц iconСамонаблюдение Самооценка Социально-психологические методы Беседа интервью
Метод контрольных близнецов Метод близнецовой пары Метод контрольного близнеца Метод разлученных монозиготных близнецов Дневниковый...
Задача классическая. Метод мини-матриц iconЛекции Опыт. Классическая схема теории вероятностей. Элементарное событие. Пространство элементарных событий. Совместные и несовместные события. Условная вероятность и формула сложе­ния в классической схеме теории вероятностей
Условная вероятность. Зависимые и независимые события. Тео­рема умножения вероятностей. Теорема сложения вероятностей. Геометрические...
Задача классическая. Метод мини-матриц iconЛекции темы: 4-8 Тема 4: применение интерполяции обратное интерполирование
Определим функцию f –1(y) и найдем значение функции f(xi)=yi в точке a – это и будет решением нелинейного уравнения f(x)=a. Таким...
Задача классическая. Метод мини-матриц iconМини-проект
Институт повышения квалификации и переподготовки государственных служащих и работников образования
Задача классическая. Метод мини-матриц iconБилет №17 №1 Метод релаксации. Методы Якоби и Гаусса-Зейделя. Методы релаксации для решения граничных задач
Как упоминалось выше, методы релаксации разбивают разреженную матрицу на несколько, а затем задача решается при помощи итераций....
Задача классическая. Метод мини-матриц iconСценарий мини-спектакля «Как Баба Яга с экологами подружилась…» для учащихся 4-6 классов

Разместите ссылку на наш сайт:
Уроки, сочинения


База данных защищена авторским правом ©izlov.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
связаться с нами