42. Определение системы потенциалов. Метод потенциалов для решения ТЗ в матричной постановке.

1. Построение системы потенциалов.

Для построения системы потенциалов используют условие . Систему потенциалов можно построить только для невырожденного опорного плана.

Такой план содержит m+n-1 линейно-независимых уравнений с m+n неизвестными, поэтому система является неопределенной и одному неизвестному присваивают 0-е значение (обычно ). После этого остальные потенциалы определяются однозначно.

2. Проверка выполнения условия оптимальности для незанятых клеток.

Просматриваем строки и для каждой незанятой клетки проверяем выполнение условия оптимальности, т.е. суммируем потенциалы на пересечении которых стоит незанятая клетка, сумму сравниваем со стоимостью, стоящей в ней. Если для всех незанятых клеток , то план является оптимальным. Если для некоторых клеток , то план является неоптимальным. Тогда для каждой клетки, в которой не выполняется условие оптимальности, находим величину разности и записываем ее значение в правый верхний угол клетки.

3. Выбор клетки, в которую необходимо послать перевозку.

Загрузке подлежит в первую очередь клетка, которой соответствует .

4. Построение цикла и определение величины перераспределения груза.

Циклом будем называть ломанную с вершинами в клетках и звеньями. Лежащими вдоль строк и столбцов матрицы, удовлетворяющую условиям:

1) Ломанная должна быть связанной

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

Циклом пересчета называют такой цикл, при котором 1 из его вершин лежит в свободной клетке, а другие – заполнены. Цикл пересчета называется означенным, если в его вершинах расставлены знаки «+» и «-», так, что в пустой клетке стоит «+», а в соседних – «-».

Величина перераспределения принимается равной наименьшему из значений клеток цикла.

В результате перераспределения получаем новый план, который снова подлежит проверке на оптимальность.

<< | >>
Источник: Шпаргалка - Математические методы и модели исследования операций. 2016
Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме 42. Определение системы потенциалов. Метод потенциалов для решения ТЗ в матричной постановке.:

  1. Лекция №3. Решение КТЗ методом потенциалов.
  2. Решение транспортной задачи методом потенциалов.
  3. Уравнения для вычисления псевдостоимости в методе потенциалов;
  4. Метод потенциалов.
  5. Алгоритм метода потенциалов.
  6. 31. Алгоритм метода потенциалов.
  7. Зад. отыскан. кратч. расст. между П. трансп сети методом потенциалов
  8. Проверка на оптимальность невырожденного опорного плана методом потенциалов (второй пункт алгоритма)
  9. Матричный метод решения систем линейных уравнений.
  10. Тема 8. Система антикризисного управления потенциалом предприятия
  11. Система n линейных уравнений с n переменными и матричная форма ее записи. Решение системы. Совместные и несовместные, определенные и неопределенные системы линейных уравнений.
  12. 41. Критерий оптимальности для транспортной задачи в матричной постановке (Теорема).
  13. Матричный метод решения системы линейных алгебраических уравнений.
  14. Вопрос № 31 Моторные потенциалы.
  15. Билет № 19 Постсинаптические потенциалы
  16. Следовые потенциалы
  17. Вопрос 30.Вызванные потенциалы.
  18. Потенциалы действия миокардиоцитов
  19. 40. Методы построения допустимого базисного плана для ТЗ в матричной постановке. Открытая и закрытая модели ТЗ, преобразование открытой модели в закрытую.
- Аналитическая геометрия - Высшая математика - Высшая математика - Вычислительная математика - Вычислительные методы линейной алгебры - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комбинаторика - Комплексное исчисление - Линейная алгебра - Линейная алгебра и аналитическая геометрия - Линейное программирование - Математическая логика - Математическая статистика - Математическая физика - Математический анализ - Метод конечных элементов - Методы оптимизации - Обработка результатов измерений - Общая алгебра - Операционное исчисление - Основы математики - Планирование эксперимента - Пределы - Ряды - Теория вероятностей - Теория графов - Теория игр - Теория конечных автоматов - Теория массового обслуживания - Теория принятия решений - Теория случайных процессов - Теория чисел - Философия математики - Функциональный анализ - Элементарная математика -