Графический метод решения задач лин прогр

Виды моделирования

В силу многозначности понятия «модель» в науке и технике не существует единой классификации видов моделирования: классификацию можно проводить по характеру моделей, по характеру моделируемых объектов, по сферам приложения моделирования (в технике, физических науках, кибернетике и т. д.). Например, можно выделить следующие виды моделирования:

Информац-ое, Компьютерное Матем-ое Математико-картографическое Молекулярное Цифровое Логическое Педагогическое Психологическое Статистическое Структурное Физическое Экономико-математическое Имитационное Эволюционное Историческое Нечеткое Модельное

Статистическое модели́рование — исследование объектов познания на их статистических моделях; моделирование ситуаций с использованием статистических закономерностей, присущих рассматриваемому явлению. Оценка парам-ов таких моделей производится с помощью статистическиx методов

. Напр: метод максимального правдоподобия, метод наим-х квадратов, метод моментов.

Статистическое моделирование — базовый метод моделирования, заключающийся в том, что модель испытывается множеством случайных сигналов с заданной плотностью вероятности. Целью является статистическое определение выходных результатов. В основе статистического моделирования лежит метод Монте-Карло. Напомним, что имитацию используют тогда, когда другие методы применить невозможно.

Задачи модел делятся на две категории: прямые и обратные.

Прямые отв-т на вопрос, что будет, если при заданных усл-х мы выберем какое-то решение из множества допустимых решений. В частности, чему будет равен, при выбранном реш-и критерий эффектив-и.

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

Модели принятия оптим-х решений отл-я универсальностью. Классиф как задачи минимизации (максимизации) критерия эффективности, компоненты которого удовлетв-ют системе огран-ий - неравенств.

дел на: прин-е реш-й в усл-х определенности–исх данные- детермин-ые; прин-е реш-й в усл-х неопред-и – исх. данные – случ-е вел-ы.

по критерию эффективности:1.одноцелевое принятие решений (1 критерий эффективности); 2. многоцелевое (неск-о критериев).

В общем виде обратная детерминированная задача выглядеть: При заданном комплексе ограничений найти такое оптимальное решение, принадлежащее множеству допустимых решений, которое обращает критерий эффективности в максимум (минимум).

Метод поиска экстремума и опт-о решения должен всегда исходить из особенности критерия эффект и вида ограничений. Очень часто задачи содержат - неизвестные факторы. Тогда обратную задачу можно сформулировать: При заданном комплексе огранич, с учетом неизв-х факт-в, найти такое оптим-е реш-е, принадл-ее мн-ву допуст-х реш-й, кот-е, по возможности, обеспеч-ет макс- (мин-) зн-е критерия эфф.

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

Пример: Организ-я система профилактич-о и аварийного ремонта техн-х устройств с целью уменьш-ия простоя техники за счет неисправностей и ремонтов. Отказы техники, длительность ремонта и профилактик носят случайный хар-р. Характ-и всех случайных фак-ов могут быть получены, если собрать соответств-ую статистику.

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

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

 

Графический метод решения задач лин прогр

этапы: 1. Сост-е модели линейного программ-я, включающей систему линейных равенств или неравенств и целевую функцию.2. Нахождение оптимального плана задачи.3. Анализ полученных результатов.

Алгоритм графического метода решения задач ЛП:

1.Построить область допустимых решений.

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

3. Если область допустимых решений является непустым множеством, построить нормаль линий уровня n = (c1,c2) и одну из линий уровня, имеющую общие точки с этой областью.

4. Линию уровня переместить до опорной прямой в задаче на максимум в направлении нормали, в задаче на минимум- в противоп-м направлении.

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

6. Если задача имеет оптим реш-е, то для его нахождения решить совместно Ур-я прямых, ограничив-х область допустимых реш-й и им-х общие точки c соответств-й опорной прямой. Если целевая фу-я задачи достигает экстремума в двух угловых точках, то задача имеет бесконечное множество реш-й. Оптимальным реш-м явл-я любая выпуклая линейная комбинация этих точек. После нахождения оптимальных решений вычислить значение целевой функции на этих решениях.

Задача линейного прогр формулир:

Требуется при данных ресурсах выпустить такую комбинацию продукции П1 и П2, при которой доход предприятия оказался бы максимальным- И- требуется найти такое неотриц-е решение сист-ы лин-х неравенств,при кот-м линейная фу-я принимает наиб-е значение (максим).

Пример задачи ЛП

Зав д выпускает изделия из газобетона и газозолобетон (кремнезёмистый компонент – зол-унос ТЭЦ) на смешанном вяжущем – цементе+ известь. Ресурсы цемента, алюминиевой пудры и золы ограничены. Определить оптимальные объёмы производства каждого вида продукции, но так, чтобы общий объём выпуска изделий был наибольшим. Выявить узкие места в производстве и внести обоснованные и наиболее рациональные предложения по их устранению.

х1, х2 – газо газозоло, огр вресурсах каждого 90000000 280000

Составляем модель линейного программирования.

При условии X1³0 и X2³0.

Симплекс метод.

Этот метод является универсальным. Система ограничений здесь – система линейных уравнений, в которых количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. К такому виду можно привести любую совместную систему, например метод Гаусса. Первые r неизвестных не всегда можно выразить через остальные. Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называют базисными, остальные переменные – свободными. Особые решения, которые получаются, когда свободные переменные равны нулю. Такие решения называют базисными. Базисное решение называется допустимым базисным решением, или опорным решением, если в нём значения переменных неотрицательны.

Транспортная задача

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

Транспортная задача считается закрытой (замкнутой),если:

а) все запасы должны быть вывезены;

б) все потребности должны быть удовлетворены;

в) суммарные запасы равны суммарным потребностям.

 

Общая стоимость перевозок выч-я по формуле:

Для отыскания первого базисного решения (опорного плана) закрытой транспортной задачи существуют следующие способы:

1) метод «северо-западного» угла;

2) метод наименьшей стоимости («минимального элемента»);

3) распределительный метод;

4) симплекс-метод;

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