Контрольные, курсовые, рефераты, тесты – готовые и на заказ!
 Гарантия качества, доступные цены, индивидуальный подход
 Работы выполняют высококвалифицированные специалисты
Войти      Регистрация
 тел. 8-912-388-82-05
  std72@mail.ru
> 20 лет успешной работы
> 50000 выполненных заказов
Отзывы/вопросы

Форма входа



Главная » Учебно-методические материалы » ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ » Математические методы. Попова Н.В.

Тема 2.7. Оптимальность плана транспортной задачи
22.12.2011, 14:14

Метод потенциалов

Пусть одним из рассмотренных в п.2.6 методов найден опорный план, содержащий n + m - 1 занятых клеток (в некоторых из них могут стоять нули). Поставим в соответствие каждому пункту отправления Аi некоторое число ui (i = l, ..., m) и каждому пункту назначения Bj - число vj (j = 1, ..., n). Эти числа назовем потенциалами, соответственно, пунктов отправления и пунктов назначения.

Вопрос об оптимальности опорного плана решает следующая теорема:

Теорема 5. Если для некоторого плана X*= (xij ), (i = l, ..., m; j = l, ..., n) транспортной задачи выполняются условия:

1. ui + vj = cij для xij > 0 (для занятых клеток),          (2.22)
2. ui + vj < cij для xij = 0 (для свободных клеток),     (2.23)

то план X* является оптимальным. Из теоремы следует, что если для некоторой свободной клетки 
ui + vj < cij , то план не является оптимальным.

Отметим, что система (2.22) (m + n - 1) уравнений содержит (m + n) неизвестных ui , v, и потому, приравнивая одно из них, например uк нулю, однозначно определим остальные неизвестные.

Для «улучшения» опорного плана (при невыполнении условия (2.23)) выбирают свободную клетку с max (ui + vj - cij ) и строят для нее цикл пересчета (сдвига).

Циклом называют замкнутую ломаную линию, все вершины которой лежат в занятых ячейках, кроме одной, расположенной в свободной клетке, подлежащей заполнению, а звенья параллельны строкам и столбцам, причем в каждой строке (столбце) лежит не более 2-х вершин. Всем вершинам поочередно приписывают знаки «+» и «-», начиная со свободной клетки. 
Далее, в свободную клетку помещают груз величиной λ, равной минимальному значению из всех чисел в отрицательных ячейках цикла. Во все положительные клетки прибавляется λ, из отрицательных - вычитается λ (сдвиг по циклу). Нетрудно подсчитать, насколько изменится (уменьшится) стоимость перевозок при новом плане:

, где  - сумма тарифов в положительных вершинах, - в отрицательных вершинах цикла. 
Новый опорный план снова проверяют на оптимальность с помощью системы уравнений потенциалов. 
Заметим, что в результате пересчета по циклу может оказаться число занятых клеток меньше, чем n+m-1 (план называется вырожденным). В этом случае следует заполнить числом «0» пустую клетку, имеющую минимальный тариф, и не образующую с занятыми клетками замкнутого прямоугольного контура.

Пример 2.7.1.

Свойство 1. Если, для некоторого оптимального плана X*= (xij ), (i = l, ..., m; j = l, ..., n) транспортной задачи, выполняется условие: ui + vj = cij для xij =0 (для свободных клеток), то, существует как минимум еще один оптимальный план, для которого общая стоимость плана перевозок остается прежней, поскольку (ui + vj) – cij = 0.

Пример 2.7.2.

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

http://matmetod-popova.narod.ru/




БАНКОВСКОЕ ДЕЛО
БУХГАЛТЕРСКИЙ, УПР. И ФИН. УЧЕТ
БЮДЖЕТ И БЮДЖЕТНАЯ СИСТЕМА РФ
ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ
ГУМАНИТАРНЫЕ НАУКИ
ДОКУМЕНТОВЕДЕНИЕ И ДЕЛОПРОИЗВОДСТВО
ИНВЕСТИЦИИ
ИНФОРМАЦИОННЫЕ СИСТЕМЫ В ЭКОНОМИКЕ
ИССЛЕДОВАНИЕ СИСТЕМ УПРАВЛЕНИЯ
МАРКЕТИНГ
МЕНЕДЖМЕНТ
МЕТ. РЕКОМЕНДАЦИИ, ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
МИРОВАЯ ЭКОНОМИКА И МЭО
НАЛОГИ И НАЛОГООБЛОЖЕНИЕ
ПЛАНИРОВАНИЕ И ПРОГНОЗИРОВАНИЕ
ПРАВОВЕДЕНИЕ
РАЗРАБОТКА УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ
РЫНОК ЦЕННЫХ БУМАГ
СТАТИСТИКА
УПРАВЛЕНИЕ ПЕРСОНАЛОМ
УЧЕБНИКИ, ЛЕКЦИИ, ШПАРГАЛКИ (СКАЧАТЬ)
ФИНАНСОВЫЙ МЕНЕДЖМЕНТ
ФИНАНСЫ, ДЕНЕЖНОЕ ОБРАЩЕНИЕ И КРЕДИТ
ЦЕНЫ И ЦЕНООБРАЗОВАНИЕ
ЭКОНОМИКА
ЭКОНОМИКА, ОРГ-ЦИЯ И УПР-НИЕ ПРЕДПРИЯТИЕМ
ЭКОНОМИКА И СОЦИОЛОГИЯ ТРУДА
ЭКОНОМИЧЕСКАЯ ТЕОРИЯ (МИКРО-, МАКРО)
ЭКОНОМИЧЕСКИЙ АНАЛИЗ
ЭКОНОМЕТРИКА
Оформить заказ
Ваше имя *
Ваш e-mail *
Контактный телефон
Город *
Учебное заведение *
Предмет *
Тип работы *
Тема работы/вариант *
Кол-во страниц
Срок выполнения *
Прикрепить файл
Дополнительные условия


Статистика
Онлайн всего: 20
Гостей: 20
Пользователей: 0