Лекция методы исследования операций

Страница 2 из 6

16. Третья теорема двойственности и ее экономическое содержание.

1). Двойственная оценка пропорциональна изменению целевой функции при изменении соответствующего ресурса на единицу. Их часто называют скрытыми, теневыми или маргинальными оценками ресурсов.

2). Двойственная оценка обратно пропорциональна изменению целевой функции при изменении соответствующего ресурса на единицу.

3). Скрытые, теневые или маргинальные оценки ресурсов численно равны значениям множителей функции Лагранжа.

4). Скрытые, теневые или маргинальные оценки ресурсов – это ничем не связанные друг с другом понятия.

5). Двойственные оценки показывают приращение целевой функции, вызванные малыми изменениями свободного члена соответствующего ограничения задачи линейного программирования, то есть

17. Анализ чувствительности математической модели и диапазоны устойчивости.

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

2). В силу своей линейности ЗЛП обладает свойством сохранять оптимальность и допустимость решения при изменении (в некотором диапазоне) параметров задачи. Диапазоном устойчивости называют область изменения параметра ЗЛП, в которой базис остается оптимальным и допустимым. Определение диапазонов устойчивости называют иногда анализом чувствительности

3). При изменении коэффициента целевой функции хотя бы при одной из небазисных переменных – изменяется относительная оценка всех небазисных переменных.

4). При изменении коэффициента функции при базисной переменной изменяются относительные оценки всех базисных переменных.

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

18. Диапазон изменения элемента вектора свободных членов.

1). Ограничение активно. Изменение свободного члена ограничений равносильно изменению дополнительной переменной, при котором происходит изменение всех базисных переменных.

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

3). Если то изменится только относительная оценка небазисной переменной . Из условия сохранения оптимальности, то есть не отрицательности этой оценки: если если

4). Если ограничение является неравенством типа “”, то соответствующие диапазоны имеют следующие значения: дополнительная переменная – небазисная: дополнительная переменная –базисная:

5). Если ограничение является неравенством, то диапазона изменения свободного члена нет и любое его изменение приводит к необходимости преобразования базиса.

19. Специальные классы задач линейного программирования. Транспортная задача.

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

2). Существуют различные подходы в решении Т-задачи. В частности к ручным методам вычисления оптимального плана относятся распределительный метод и так называемый Венгерский метод.

3). В пунктах производства имеются запасы какого-то продукта в количествах единиц соответственно. Необходимость в этом продукте в пунктах потребления выражается соответственно величинами Из каждого пункта производства возможна транспортировка продукта в любой пункт потребления. Транспортные издержки на перевозку единицы продукции (груза) из пункта и заданы и составляют Так называемую матрицу издержек. Задача состоит в том, чтобы отыскать такой план перевозок, при котором весь продукт из пунктов производства будет вывезен, запросы потребителей полностью удовлетворены и суммарные транспортные издержки – минимальны.

4). Т-задачи можно решать и с использованием вычислительной техники с помощью методов потенциалов и так называемого метода дифференциальных рент.

5). Существующий алгоритм решения транспортных задач (метод потенциалов) предполагает, что ЦФ стремится к максимуму.

20. Транспортная задача. Метод Северо-Западного угла.

Имеются 3 поставщика () однородной продукции с объемами: . Необходимо продукцию перевезти в 4 пункта поставки () с объемами потребления: . Определите план перевозок, составленный методом северо-западного угла:

1).		70	90	120	20	2).		70	90	120	20
	100	70	30				100		90	10
	150		60	90			150	70		80
	50			30	20		50			30	20

3).		70	90	120	20	4).		70	90	120	20
	100		20	60	20		100	50	50
	150	20	70	60			150	20	40	90
	50	50					50			30	20

5).		70	90	120	20
	100	70	30
	150		10	120	20
	50		50

21. Транспортная задача. Метод минимального элемента.

1).		125	90	130	100	2).		125	90	130	100
	210		45	130	35		210		90	120
	170	125	45				170	125		10	35
	65				65		65				65

3).		125	90	130	100	4).		125	90	130	100
	210			110	100		210	65	90	55
	170	60	90	20			170	60		75	35
	65	65					65				65

5).		125	90	130	100
	210	125	85
	170		5	130	35
	65				65

22. Транспортная задача. Метод минимального элемента.

1).		125	90	130	100	2).		125	90	130	100
	210			110	100		210		90	120
	170	125	25	20			170	125		10	35
	65		65				65				65

3).		125	90	130	100	4).		125	90	130	100
	210			110	100		210	65	90	55
	170	60	90	20			170	60		75	35
	65	65					65				65

5).		125	90	130	100
	210	125	85
	170		5	130	35
	65				65

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

1). Предварительные потенциалы выбирают таким образом, чтобы для связанных коммуникациями пар пунктов, для которых в плане , сумма потенциалов была равна : Существует единственный набор таких потенциалов.

2). В парах связанных коммуникациями пунктах, для которых в плане , высчитываются новые значения .

3). Переходы к другим смежным решениям Т-задачи, как задачи ЛП методом потенциалов, идея которого состоит в улучшении начального опорного плана до тех пор, пока не будет удовлетворяться признак оптимальности. Алгоритм метода потенциалов решения Т-задачи состоит из предварительного этапа и конечного числа итераций.

4). Критерий оптимальности: все , когда, выстроенный план перевозок – оптимальный.

5). Новые итерации, в случае, если план оказался неоптимальным, осуществляются методом элементарных преобразований строк матрицы издержек.

24. Общая распределительная задача линейного программирования.

1). Исходные параметры модели РЗ: количество исполнителей, количество видов выполняемых работ, запас рабочего ресурса исполнителей, планируемая загрузка исполнителей при выполнении работ, количество работ, которые должен будет произвести исполнитель.

2). Общая распределительная задача ЛП – это РЗ, в которой работы и ресурсы (исполнители) выражаются в различных единицах измерения. Типичным примером такой задачи является организация выпуска разнородной продукции на оборудовании различных типов.

3). Искомые параметры модели РЗ: планируемая загрузка исполнителей при выполнении работ, общие расходы на выполнение всего запланированного объема работ, интенсивность выполнения работ исполнителями.

4). Этапы построения модели: определение переменных, построение распределительной матрицы, задание целевой функции, задание ограничений.

5). Этапы решения РЗ: преобразование распределительной задачи в транспортную не осуществляется, несмотря на то, что она и является ее частным случаем.

25. Целочисленные задачи линейного программирования.

1). Существует единственный метод, позволяющий привести к целочисленному решению задачи – это метод отсекающих плоскостей.

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

3). Если исходная система ограничений совместна и целевая функция ограничена на множестве решений, тогда можно приступить к отысканию оптимального решения, не отбрасывая на начальном этапе условие целочисленности решения.

4). Метод отсекающих плоскостей состоит в том, что для Й переменной, имеющей нецелочисленное значение, формируется дополнительное ограничение, которое имеет вид: Здесь число есть дробная часть числа

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

26. Этапы решения целочисленной задачи методом отсекающих плоскостей.

1). Важно отметить, что целочисленные точки, а равно и оптимальное целочисленное решение задачи, является внутренней точкой ОДР. Тогда, очевидно, геометрически, получение целочисленного решения, означает движение по линиям уровня целевой функции в направлении, обратном . Поэтому, для дальнейшего решения задачи необходимо применить технику двойственного симплекс-метода.

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

3). Если на предварительном этапе после применения симплекс-метода без учета условия целочисленности переменных, полученное решение содержит несколько нецелочисленных компонент, то для отсечения выбирается та, которая имеет минимальную дробную часть

4). При формировании правильного отсечения важно помнить, что выбор строки по критерию минимума дробной части осуществляется по всем не целочисленным переменным.

5). Задача считается решенной, а оптимальное целочисленное решение полученным в том случае, если в столбце свободных членов элементы, соответствующие истинным переменным задачи, – целые.

«В начало Назад123456Вперёд В конец»