Статья: Метод сравнения альтернатив для поиска первоначального решения транспортной задачи

Т а б л и ц а 3

Матрица оценок свободных клеток для примера 1

Т а б л и ц а 4 Пример 2 транспортной задачи

Т а б л и ц а 5 Первоначальное решение для примера 2, найденное методом аппроксимации Фогеля

Для проверки оптимальности была получена следующая матрица оценок свободных клеток (табл. 6).

Т а б л и ц а 6 Матрица оценок свободных клеток для примера с оптимальным решением

Полученное первоначальное решение является неоптимальным, причем общие расходы при таком распределении равны 1900.

Решим пример 2, используя метод сравнения альтернатив.

Т а б л и ц а 7

Первоначальное решение, найденное методом сравнения альтернатив для примера 2

1. Поиск первой ячейки.

1.1. Первый этап. Выбор ячеек (3,1), (2,1), (3,2). Для них минимальные альтернативные издержки - 2, 3, 3 соответственно, поэтому переходим ко второму этапу.

1.2. Второй этап. Выбор (2,1) и (3,2). Минимальные альтернативные суммы для (2,1) и (3,2) - 4 и 4. Переход к третьему этапу.

1.3. Третий этап. Выбор (2,1) и (3,2). Минимальные полные альтернативные суммы для (2,1) и (3,2) - 720 и 340 соответственно. Полные затраты для них - 240 и 160 соответственно. Разности между этими двумя показателями для (2,1) и (3,2) - 480 и 180 соответственно. Выбор (2,1) для поставки (120 ед.). Закрывается первый столбец.

2. Поиск второй ячейки.

2.1. Первый этап. Выбор (3,2) и (2,2). Для них минимальные альтернативные издержки - 4 и 4 соответственно. Переход ко второму этапу.

2.2. Второй этап. Выбор (3,2) и (2,2). Для них минимальные альтернативные суммы - 7 и 6 соответственно. Выбор (3,2) для поставки (80 ед.). Закрывается второй столбец.

3. Поиск третьей ячейки.

3.1. Первый этап. Выбор (3,3) и (2,3). Для них минимальные альтернативные издержки - 5 и 6 соответственно, поэтому выбираем (2,3) для поставки (30 ед.). Закрывается вторая строка.

4. Поиск четвертой ячейки.

4.1. Первый этап. Выбор (3,3), (1,3) и (3,4). Для них минимальные альтернативные издержки - 5, 6 и 6 соответственно, поэтому переходим ко второму этапу.

4.2. Второй этап. Выбор (1,3) и (3,4). Для них минимальные альтернативные суммы - 10 и 10. Переход к третьему этапу.

4.3. Третий этап. Выбор (1,3) и (3,4). Минимальные полные альтернативные суммы для (1,3) и (3,4) - 1280 и 1280. Полные затраты для них - 100 и 100. Разности между этими двумя показателями для (1,3) и (3,4) - 1180 и 1180. Выбор ячейки осуществляется случайно (в данном случае выбор не влияет на конечное решение). Выберем (1,3) для поставки (20 ед.).

Оставшиеся поставки однозначно определены условиями. Получим первоначальное решение (табл. 7).

Для проверки оптимальности была получена следующая матрица оценок свободных клеток (табл. 8).

Т а б л и ц а 8 Матрица оценок свободных клеток для решения примера 2 методом сравнения альтернатив

Данное первоначальное решение не является оптимальным, общие затраты равны 1800. Однако оно ближе к оптимуму, чем решение, полученное методом аппроксимации Фогеля.

Особенностью этого примера является то, что большое количество ячеек имеет одинаковые коэффициенты затрат. Это создает большое количество неопределенностей, что сильно усложняет нахождение лучшего первоначального варианта распределения поставок при решении любым методом [5, 6].

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

Т а б л и ц а 8 Пример задачи, решение которой оптимально

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

Ячейка (1,1) может иметь коэффициент затрат больший или равный 3. Данная ячейка исключается из заполняемых на третьем этапе поиска первой ячейки для заполнения (пункт 1.3 решения примера 2). Такие варианты не приведут к отрицательным значениям в матрице оценок свободных клеток. Ячейка (3,1) также исключается при закрытии первого столбца. Она может содержать коэффициент затрат больший или равный 2, так как иные значения повлияют на решение (пункт 1.1 решения примера 2). Ячейка (1,2) исключается при закрытии второго столбца. Она может содержать издержку большую или равную 4, так как при значении 3 или меньше данная ячейка будет рассматриваться при выборе ячеек для заполнения на первом этапе поиска второй ячейки, что может изменить решение (пункт 2.1 в решении примера 2). Ячейка (2,2) может содержать издержку, равную только 3, так как это значение влияет на решение (это значение является минимальной альтернативной издержкой для ячеек (3,2), (2,1) в пункте 1.1 решения примера 2). Аналогично (3,3) может содержать только издержку, которая равна 4 (минимальная альтернативная издержка для (3,2) в пункте 2.1 решения примера 2). Ячейка (2,4) исключается при закрытии второй строки. Она может содержать издержку большую или равную 6, так как иные значения изменят решение (пункт 3.1 решения примера 2). Общее количество вариантов условий задач, при которых решение оптимально, можно определить произведением вариантов значений коэффициентов затрат для каждой ячейки. Пусть существует некое значение х, определяющее максимально возможный коэффициент затрат в каждой ячейке. Такое ограничение позволяет рассматривать конечную группу условий задач, приводящих к оптимальному решению при изменении каждого из коэффициентов. При этом количество этих условий определено числами (х-3), (х-2), (х-4), (х-6) (относительно каждой ячейки, коэффициент которой может быть изменен). Обозначим М произведение этих чисел. Оно представляет собой все возможные варианты задач с оптимальными решениями, получаемыми методом сравнения альтернатив. При этом общее количество рассматриваемых вариантов условий задач состоит из количества задач с оптимальным решением и количества условий, решение для которых может быть неоптимальным. Для оценки количества вариантов с возможным неоптимальным решением рассмотрим матрицу оценок свободных клеток. Любые изменения коэффициентов свободных клеток, обращающие значения в этой матрице в отрицательные или нулевые, определяют варианты условий, которые приведут или могут привести к неоптимальному решению. При таких условиях ячейка (1,1) может содержать значения от 0 до 2. Ячейка (1,2) - от 0 до 3. Ячейка (2,2) - от 0 до 2 и от 4 до х. Ячейка (2,4) - от 0 до 5. Ячейка (3,1) - от 0 до 1. Ячейка (3,3) - от 0 до 3 и от 5 до х. Из этого

К = 3 х 4 х (х - 1) х 6 х 2 х (х - 1) =

= 144 х (х - 1) х (х - 1),

где К - число примеров с явным неоптимальным решением. В этом случае общее число условий N равно сумме количества условий с оптимальным решением и количества условий с явным неоптимальным решением, т. е.

N = М + К = (х - 3) х (х - 2) х (х - 4) х

х (х - 6) + 144 х (х - 1) х (х - 1).

Тогда отношение числа задач с оптимальным решением к общему выделенному числу задач:

М / N = (х - 3) х (х - 2) х (х - 4) х

х (х - 6) / ((х - 3) х (х - 2) х (х - 4) х

х (х - 6) + 144 х (х - 1) х (х - 1)).

Данное отношение представляет собой вероятность получения оптимального решения при использовании метода сравнения альтернатив. Для расчета значения этого показателя необходимо взять некоторое значение х, отражающее, какую максимальную издержку может содержать ячейка в рассматриваемом наборе транспортных задач. Пусть х = 20, тогда вероятность при рассматриваемых условиях будет примерно равна 0,57.

Таким образом, метод сравнения альтернатив имеет следующие преимущества.

1. Метод применим к любому типу транспортных задач.

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

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

4. В рамках рассмотренной группы задач сделан вывод, что метод в 57 % случаев приводит к оптимальному первоначальному решению.

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

Литература

1. Исследование операций в экономике: учеб. пособие для вузов / Н.Ш. Кремер [и др.] ; под ред. Н.Ш. Кремера. - 3-е изд., перераб. и доп. - М. : Юрайт, 2013. - 438 с.

2. Юдин Д.Б. Задачи и методы линейного программирования. Задачи транспортного типа / Д.Б. Юдин, Е.Г. Гольштейн. - М. : Либроком, 2010. - 184 с.

3. Ашманов С.А. Линейное программирование / С.А. Ашманов. - М. : Книга по Требованию, 2012. - 304 с.

4. Вентцель Е.С. Исследование операций: задачи, принципы, методология: учебник для вузов / Е.С. Вентцель. - М. : Дрофа, 2004. - 208 с.