Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



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




Читайте также:
  1. Amp; Методичні вказівки
  2. Amp; Методичні вказівки
  3. Amp; Методичні вказівки
  4. Amp; Методичні вказівки
  5. Amp; Методичні вказівки
  6. Amp; Методичні вказівки
  7. Amp; Методичні вказівки
  8. B. Искусственная вентиляция легких. Методики проведения искусственной вентиляции легких
  9. Cтруктуры внешней памяти, методы организации индексов
  10. FDDI. Архитектура сети, метод доступа, стек протоколов.

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

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

Теорема. Если план транспортной задачи является оптимальным, то ему соответствует система из m+n чисел и , удовлетворяющих условиям

, ;

,

(i=1,…,m; j=1,…,n)

Числа называются потенциалами соответственно поставщиков и, потребителей.

Действительно, условия

;

определяют m+n ограничений типа «равенство». Каждому равенству i соответствует двойственная переменная Ui. а равенству j - двойственная переменная Vj . В двойственной задаче ограничивающих условий столько, сколько переменных в основной задаче, т.е. mn. В правой части двойственного ограничения - Cij.

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


Дата добавления: 2015-04-16; просмотров: 11; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2022 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты