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

Билет.метод потенциалов.

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


Пусть получен первоначальный опорный план и пусть этот план невырожденный. После построения исходного опорного плана все переменные разбиты на 2 группы: базисные и свободные. Рассмотрим случай, когда m=n. для проверки плана на оптимальность выразим базисные переменные и функцию цели через свободные. Коэффициенты ∂ при свободной переменной в выражении ф-ии цели через свободные переменные называются оценками соотв. свободных клеток.

Теорема критерий оптимальности. Опорный план оптимален тогда и только тогда,когда оценки всех свободных клеток неотриц. док-во: Если ∂12<0. То F можно увеличить за счет увеличения X12. Если же наоборот ∂>0, то увеличение x12 не уменьшит F, т.е. план оптимальный. Для нахождения коэффициента ∂12 при свободных переменных составим каждому поставщику А некоторую величину U, которую назовем потенциалом поставщика. Каждому потребителю В поставим величину V- потенциал потребителя. Свяжем эти величины соотношением U+V=C. можно доказать,что совокупность уравнений U+V=C, составленных для всех базисных переменных явл совместной системой из m+n-1 уравнений с m+n неизвестными. значение одной из переменной можно задать произвольно, тогда остальные значения найдутся из системы однозначно. Составим систему потенциалов. Обозначим для свободных переменных xpq сумму соотв.потенциалов через Сpq. Таким образом, для того,чтобы опорный план был оптимальным, необходимо и достаточно, чтобы 1) U+V≤Cpq(для всех свободных клеток) 2) U+V=0(для занятых клеток)

Если хотя бы одной из свободных клеток оценка отрицательна, то план неоптимален и его можно улучшить, вводя в базис переменную, соотв. Клетке с отриц. Оценкой. Для этого строят цикл пересчета, т.е цикл в таблице с опорным планом, одна из вершин которой лежит в свободной клетке с отриц.оценкой, а остальные в занятых клетках. Цикл, в вершинах которого проставлены знаки, называется означенным. Для каждой свободной клетки существует единственный план пересчета, причем операция означивания явл конкретной. Чтобы найти перераспределяемый объем перевозок, находим Ө0=minxij. Где х- перевозки, стоящие в вершинах цикла, отмеченные знаком «– «. Значение Ө0 определяет сколько единиц можно распределить по найденному циклу.это значение записываем в свободную клетку со знаком + и далее, двигаяссь по циклу, вычитаем Ө0 из объемов, помеченный знаком – и прибавляет к объему со знаком +.

Алгоритм: 1) найдем опорный план методом северо-западного угла. 2) проверка на оптимальность- составим систему потенциалов 3) найдем оценки свободных клеток 4) перейдем к новому опорному плану

 


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


<== предыдущая страница | следующая страница ==>
Приведение открытой ТЗ к закрытой.| Вырожденность в транспортных задачах

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