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

Приведение открытой ТЗ к закрытой.

Вырожденность в транспортных задачах | Альтернативный оптимум в транспортных задачах | Целочисленное программирование. Метод Гомори (правильное отсечение, правила формирования правильного отсечения). | Пример. | Графический метод решения задачи целочисленного программирования. | Теорема 1.1 | Теорема 1.2 | Графический метод решения задач нелинейного программирования | Нелинейная целевая функция и линейная система ограничений. | Условный экстремум. Метод множителей Лагранжа |


Читайте также:
  1. Итоги XIII открытой научно-практической конференции учащихся
  2. Модели организации как закрытой, открытой, частично открытой системы
  3. Особенности действий сотрудников полиции при задержании вооруженных преступников ы жилом помещении, отдельном строении, общественном месте, автотранспорте и на открытой местности.
  4. Первенство г.Ялуторовска по мини-футбол на открытой площадке сезон 2014г.
  5. Переход итало германских фашистов и милитаристкой Японии к актам открытой агресси 1933-1935
  6. Приведение вторичной обмотки трансформатора
  7. Приведение квадратичных форм к каноническому

1)превышение запасов над потребителями

Вводится «фиктивный» потребитель

Вn+1=

2)превышение потребностей вводим «фиктивный» поставщик

Аin+1=

Теорема 8

Любой опорный план имеет не более чем n+m-1 положительных компонентов.

Док-во:

Исходная система ограничений содержит n+m ограничений типа равенств.

Покажем это для случая m=2 n=3

  в1 в2 в3
а1 X11 C11 X12 C12 X13 C13
а2 X14 C21 X15 C22 X16 C23

а1+a2123

 

 

x11+x12+x131

x21+x22+x23=a2

x11+x211

x12+x222

x13+x233

Сложим (1) и (2) и вычтим из них (3) и (4)

X11+x12+X13+x21+x22+x23-x11-x21-x12-x221+а212

X13+x233, т.е. независимых ограничений, а => базисные переменные не более чем n+m-1

Следствие: Оптимальный план содержит не более чем n+m-1 перевозок.

 

 

7 билет. Определение первоначального опорного плана.

Методы нахождения начального опорного плана

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

Для определения опорного плана существует несколько методов:

· Метод северно-западного угла. При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Обычно рассмотренный метод используется при вычислениях с помощью ЭВМ.

· Метод минимального элемента. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисели,затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

· Метод аппроксимации Фогеля. При определении опорного плана транспортной задачи методом аппроксимации Фогеля находят разность по всем столбцам и по всем строкам между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальная стоимость. Если минимальная стоимость одинакова для нескольких клеток столбца (строки), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными стоимостями, находящимися в данном столбце (строке).

 


Дата добавления: 2015-08-20; просмотров: 134 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Геометрический смысл стандартной ЗЛП. Множество допустимых решений. Графический способ решения.| Билет.метод потенциалов.

mybiblioteka.su - 2015-2024 год. (0.005 сек.)