Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Основные задачи приводящие к линейному программированию.





Метод множителя Лагранжа.

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

z=f(x1,x2…xn) max(min); (x1x2…xn)=bi(i=1 )

Эта задача не линейного программирования, и эти задачи называются классическими задачами оптимизации. Их можно решать пот крайне мере, методами дифференциального исчисления. В простейшем случае условным экстремумом функции f(x1x2) называется max(min), достигнутый при условий, что х1 и х2 удовлетворяют дополнительному условию.

 

Основные задачи приводящие к линейному программированию.

Задача о диете.

Для сохранения работоспособности человек в сутки должен потреблять некоторое количество питательных веществ: В1-белки, В2-витамины, В3-жиры, В4-углеводы, В5-вода. Имеется два вида пищи: П1 и П2. Запасы веществ: Вi в пище Пj составляет aij. Стоимость единицы продукции будет П1-С1, П2-С2. Требуется так организовать питание, что бы его стоимость была меньше, а человек получил бы не меньше суточной нормы питания. Составляем математическую модель. Обозначим через х1 и х2-количество продуктов П1 и П2, тогда количество белков в П1-а11х1 в П2-а12х21.

а11х112х2≥в1

а21х122х2≥в2

а31х132х2≥в3

а41х142х2≥в4

а51х152х2≥в5

F=C4x1+C2x2→min

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

Задача об использовании сырья.

Для изготовления двух видов продукции, требуется сырье 5-ти видов. Доход получаемый от реализации продукта П1 и П2, будет соответственно S1 и S2.

а11х1 12 х21

а21 х1 22 х2 2



а31 х1 32 х2 3

а41 х1+ а42 х2 4

а51 х151 х2 5

F=C1x1+C2x2→max

 

Канонический вид задачи линейного программирования.

Не смотря на разнообразие условий (><=) их все можно свести к одной канонической форме, которая имеет вид:

а11х1 + а12х1+…а1n хn1

а21 х1 + а22х2+…а2n хn2

… … … … … … … … … … …(1)

аm1 х1 + аm2х1+…аnm хnm

F=C0 +C1x1+C2x2+…Cnxn→min

В матричном виде это выглядит так:

(А*х)=(В)

F=( C )*(x)→min

Всякое неотрицательное решение системы(1) называется допустимым. Допустимое решение системы точка которая минимизирует F называется оптимальным планом. Оптимальное решение:

-опт. решение

Допустимое решение:
Как правило оптимальное решение бывает единственным.

 

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

Если число переменных равно 2 или 3, то задачу ЛП можно решить геометр. способом, но все ограничения должны иметь вид неравенств. Геометрически задача ЛП задается в виде призмы в основании которого лежит ОДЗ. Но для упрощения призму не рисуют, оставляют только ОДЗ, но тогда для того что бы узнать в какую сторону F убывает или возрастает, находят градиент N.

1.Находим ОДЗ.

2.Находим N.

3.Перпендикулярно N проводим прямую F.

4.Прямую F перемещаем параллельно себе в направлении градиента, первая вершина, в которую входят прямая F-min, последняя вершина которую покидает F-max.

 

Двойственная задача.

Двойственные задачи имеют важное значения:

1.они помогают оценить среднее значение цент на рынке.

2.с их помощью определяется критерий остановки программы расчета задач ЛП.

Решение двойственной задачи равно решению прямой задача, т.е. Fпр.=Fдв.

 

 

7.Нахождение опорного плана тремя методами.

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

Второй способ. Метод наименьшей стоимости состоит в том, что на каждом шаге осуществляется максимально возможная поставка в клетку с минимальным тарифом с ij. Заполнение таблицы начинаем с клетки которой соответствует наименьший элемент с ij из всей матрицы тарифов. Затем остаток по столбцу или строке, которые соотв. по величине с ij и т.д. Другими словами, последовательность заполняемых клеток, определяется по величине с ij, а помещаем в этих клетках величины хij как при решении по правилу С-ЗУ. Может оказаться, что при построении плана, занятых клеток будет меньше, чем m+n-1. В этом случае задача называется вырожденной, тогда в свободную клетку, обычно в ту, которой соответствует наименьший тариф, и в нее помещаем 0, тогда эта клетка считается занятой.

 

Распределительный метод.

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

1.Сост-тся опорный план. Опорный план проверяется на вырожденность. Кол-во занятых клеток должно быть равно m+n-1. Если меньше, то в любую другую свободную клетку заносится 0 ед. груза и клетка считается занятой.

2. Для всех свободных клеток составляются циклы во всех клетках цикла начиная со свободной поочередно ставятся знаки «+» «-»

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

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

 

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

После нахождения опорного плана перевозок каждому поставщику Ai (в каждой строке) ставится в соответствии некоторое число Ui, а каждому потребителю( каждому столбцу ) Bi ставится в соответствии некоторое число Vj. Числа Ui и Vj наз-ся потенциалами и выбираются так, чтобы в любой загруженной клетке их сумма равнялась тарифу этой клетке. Ui+Vj=Cij. Т.к. всех потенциалов m+n, а число занятых клеток m+n-1, то одному из неизвестных можно придать произвольное значение. И найти все оставшиеся потенциалы. Затем для проверки оптимальности просматриваются свободные клетки ij и для каждой их них вычисляется оценка:

. План оптимален, если для каждой свобод. клетки Sij≥0. Если есть отрицательные оценки, то переходят к новому плану по правилам распределительного метода. В новом плане определяется потенциалы строк и столбцов. Вычисляются оценки для всех свободных клеток. Когда среди оценок не окажется отрицательных полученный план будет оптимальным.

 

Классификация ЗУЗ.

1.по кол-ву управляемых периодов на однопериодные и многопериодные. Если пополнение запасов произв-ся один раз-однопериодная, если много-многопериодная.

2.по характеру пополнения запасов, мгновенная после подачи заявки и с задержки.

3.по учету хар-ра спроса: на детерминированные и вероятность.

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

5.По виду целевой функции на задачу с пропорционными и не пропорциональными затратами. Так затраты не 1км. Машины могут быть пропорциональными.

 

Метод множителя Лагранжа.

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

z=f(x1,x2…xn) max(min); (x1x2…xn)=bi(i=1 )

Эта задача не линейного программирования, и эти задачи называются классическими задачами оптимизации. Их можно решать пот крайне мере, методами дифференциального исчисления. В простейшем случае условным экстремумом функции f(x1x2) называется max(min), достигнутый при условий, что х1 и х2 удовлетворяют дополнительному условию.

 

Основные задачи приводящие к линейному программированию.

Задача о диете.

Для сохранения работоспособности человек в сутки должен потреблять некоторое количество питательных веществ: В1-белки, В2-витамины, В3-жиры, В4-углеводы, В5-вода. Имеется два вида пищи: П1 и П2. Запасы веществ: Вi в пище Пj составляет aij. Стоимость единицы продукции будет П1-С1, П2-С2. Требуется так организовать питание, что бы его стоимость была меньше, а человек получил бы не меньше суточной нормы питания. Составляем математическую модель. Обозначим через х1 и х2-количество продуктов П1 и П2, тогда количество белков в П1-а11х1 в П2-а12х21.

а11х112х2≥в1

а21х122х2≥в2

а31х132х2≥в3

а41х142х2≥в4

а51х152х2≥в5

F=C4x1+C2x2→min

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

Задача об использовании сырья.

Для изготовления двух видов продукции, требуется сырье 5-ти видов. Доход получаемый от реализации продукта П1 и П2, будет соответственно S1 и S2.

а11х1 12 х21

а21 х1 22 х2 2

а31 х1 32 х2 3

а41 х1+ а42 х2 4

а51 х151 х2 5

F=C1x1+C2x2→max

 









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2019 zdamsam.ru Размещенные материалы защищены законодательством РФ.