- •П.И. Тутубалин, л.Т. Моисеева теория принятия решений
- •Оглавление
- •1. Основные понятия теории принятия решений 2
- •2. Классификация решений 5
- •4. Линейные модели задач принятия решений 16
- •5. Нелинейные модели задач принятия решений 42
- •6. Методы решения двухкритериальных задач принятия решений 53
- •1. Основные понятия теории принятия решений
- •2. Классификация решений
- •3. Общая математическая модель формирования оптимальных решений
- •3.1. Классификация математических моделей в задачах принятия решений
- •3.2. Краткая характеристика математических методов формирования оптимальных решений
- •4. Линейные модели задач принятия решений
- •4.1. Задача выбора оптимальной производственной программы предприятия
- •4.2. Распределительные задачи принятия решений
- •4.2.1. Задача распределения количества заказов по предприятиям
- •4.2.2. Задача распределения грузов по средствам доставки
- •4.2.3. Задача оптимизации перевозок однородного продукта
- •4.2.4. Метод минимальной стоимости для решения закрытой транспортной задачи
- •4.2.5. Задача о назначениях
- •4.3. Задача оптимального выбора
- •4.3.1. Задача о ранце
- •4.3.2. Задача оптимального выбора выполняемых работ
- •5. Нелинейные модели задач принятия решений
- •5.1. Задача о выборе геометрических размеров бака заданного объема
- •5.2. Задача оптимального размещения предприятий
- •5.3. Стохастическая модель выбора оптимальной производственной программы
- •5.4. Стохастическая модель стоимости товаров в торговых центрах
- •6. Методы решения двухкритериальных задач принятия решений
- •6.1. Решение двухкритериальной задачи о баке
- •6.2. Решение двухкритериальной стохастической задачи стоимости товаров в торговых центрах
- •Литература
4.2.3. Задача оптимизации перевозок однородного продукта
Эта задача является одной из важных задач в оптимизационной деятельности организационно-технических систем. Одной из первых задач оптимизации перевозок явилась классическая транспортная задача (КТЗ).
Основные предположения КТЗ:
1) потребности пунктов назначения перевозок груза удовлетворяются за счёт нескольких пунктов его отправления,
2) величина транспортных расходов при перевозке груза пропорциональна количеству перевозок по каждому маршруту.
Пусть имеется однородная продукция, сосредоточенная у m поставщиков в объёмах соответственно . Этот продукт необходимо доставить n потребителям, которые имеют потребности в нём, равные . Пусть заданы – стоимость перевозки единицы продукта от i-го поставщика j-му потребителю . Требуется определить величины объёмов продукта, перевозимого от i-го поставщика j-му потребителю. Транспортная задача графически представлена на рисунке 4.3.
Рис. 4.3
Все маршруты перевозок являются возможными.
Будем считать, что запасы и потребности в системе сбалансированы:
. (4.21)
Переменные в этом случае должны удовлетворять ряду условий. Запасы всех поставщиков должны быть вывезены:
. (4.22)
Все потребности в системе должны быть удовлетворены:
. (4.23)
Условие того, что не все маршруты перевозок могут быть реализованы:
. (4.24)
Суммарная стоимость всех перевозок с учетом транспортных расходов вычисляется как:
. (4.25)
КТЗ формулируется в следующем виде: требуется определить значение переменных , доставляющих минимум целевой функции (4.25) при выполнении ограничений (4.21) - (4.24). Видно, что данная модель является линейной моделью ЗПР. Модель (4.25), (4.21) - (4.24) при наличии условия (4.21) называется закрытой транспортной задачей по критерию стоимости.
В реальных задачах условие (4.21) часто нарушается. Рассмотрим два возможных случая:
1. Сумма запасов превышает сумму потребностей данной продукции
. (4.27)
Так как в этом случае все запасы не могут быть вывезены, то условие (4.22) заменяется условием вида:
. (4.28)
2. Сумма потребностей превышает сумму запасов:
. (4.29)
В этом случае часть потребностей не удастся удовлетворить, поэтому ограничение вида (4.23) заменяется неравенством:
. (4.30)
Математические модели вида (4.25), (4.23), (4.28), (4.24) и (4.25), (4.22), (4.30), (4.24) описывают открытые транспортные задачи. Как закрытые, так и открытые транспортные задачи являются задачами линейного программирования и могут быть решены соответствующими численными методами. Однако, если размерность задачи слишком велика (для больших и ), то эти методы являются весьма трудоемкими. Однако для закрытой транспортной задачи (ТЗ) имеются свои более простые методы решения, в которых используется табличная форма представления исходных данных.
С учетом сказанного, рассмотрим методы сведения открытой КТЗ к закрытой КТЗ.
1. Пусть в системе выполняются условия вида (4.27) в этом случае вводится фиктивный (n + 1) потребитель, с потребностью равной:
,
но, так как данного потребителя в системе нет, то стоимость перевозки к нему от всех поставщиков полагается равной .
2. Пусть в системе выполняется условие вида (4.29). В этом случае вводится фиктивный (m + 1) поставщик с запасом, равным
,
соответственно стоимость перевозки от этого поставщика ко всем потребителям полагается равной .
Вследствие вида критерия (4.25) и бесконечной стоимости перевозок при автоматически обнуляются переменные и . При практических расчетах коэффициенты и обычно полагают равными очень большим числам, на несколько порядков выше, чем реальный . Аналогичным образом с помощью коэффициентов можно ввести запрещающий маршрут и в закрытой КТЗ.
Рассмотрим свойства классической транспортной задачи. Задача (4.25), (4.21) - (4.24), как задача линейного программирования специального типа имеет следующие особенности:
1) Все коэффициенты при xij в ограничениях (4.22) и (4.23) равны 1.
2) Система ограничений (4.22), (4.23) включает в себя уравнений.
3) Ранг системы (4.22), (4.23) вследствие (4.21) равен . Это означает, что оптимальное решение задачи (4.25), (4.21) - (4.24) будет содержать ненулевых объемов перевозок.
Докажем, что любая закрытая ТЗ имеет решение.
Конкретизируем условие (4.21) в следующем виде:
, (4.31)
где , величина суммарного объема запасов и потребностей в системе.
Выберем объем перевозок в системе по формуле
. (4.32)
Покажем, что решение вида (4.32) является допустимым решением задачи (4.25), (4.21) - (4.24).
Подставив величину (4.32) в выражение (4.22), (4.23) получим подтверждение условий (4.22), (4.23) при выбранном решении. Условие (4.24) выполняется очевидным образом, так как все и . Отсюда следует, что допустимое множество решений задачи (4.25), (4.21) - (4.24) не пустое, так как содержит хотя бы одну точку вида (4.32).
Покажем, что целевая функция (4.25) ограничена. Выберем в матрице стоимости перевозок максимальный и минимальный элемент , . Внесем в матрицу сначала , а затем и посчитаем при этом значение целевой функции для выбранного решения (4.32). В итоге получим следующее двойное неравенство, свидетельствующее об ограниченности целевой функции сверху и снизу: .