|
|
Основные задачи приводящие к линейному программированию.Стр 1 из 2Следующая ⇒ Метод множителя Лагранжа. В мат. анализе существуют задачи на условный экстремум, если среди ограничений нет неравенств при условиях неотрицательности, то тогда задача приводится к виду: z=f(x1,x2…xn) max(min); Эта задача не линейного программирования, и эти задачи называются классическими задачами оптимизации. Их можно решать пот крайне мере, методами дифференциального исчисления. В простейшем случае условным экстремумом функции 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х1+а12х2≥в1 а21х1+а22х2≥в2 а31х1+а32х2≥в3 а41х1+а42х2≥в4 а51х1+а52х2≥в5 F=C4x1+C2x2→min К этому же виду приводится задача на смеси: бензин различных сортов получают путем смешивания нефти продуктов, имеющих разные химические характеристики, но их количество должно выдерживаться точно. Задача об использовании сырья. Для изготовления двух видов продукции, требуется сырье 5-ти видов. Доход получаемый от реализации продукта П1 и П2, будет соответственно S1 и S2. а11х1 +а12 х2=в1 а21 х1 +а22 х2 =в2 а31 х1 +а32 х2 =в3 а41 х1+ а42 х2 =в4 а51 х1+а51 х2 =в5 F=C1x1+C2x2→max
Канонический вид задачи линейного программирования. Не смотря на разнообразие условий (><=) их все можно свести к одной канонической форме, которая имеет вид: а11х1 + а12х1+…а1n хn=в1 а21 х1 + а22х2+…а2n хn =в2 … … … … … … … … … … …(1) аm1 х1 + аm2х1+…аnm хn =вm 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 и для каждой их них вычисляется оценка:
Классификация ЗУЗ. 1.по кол-ву управляемых периодов на однопериодные и многопериодные. Если пополнение запасов произв-ся один раз-однопериодная, если много-многопериодная. 2.по характеру пополнения запасов, мгновенная после подачи заявки и с задержки. 3.по учету хар-ра спроса: на детерминированные и вероятность. 4.по кол-ву типов ресурсов-на однопродуктовые и многопродуктовые. Если запас включает несколько видов продукции, то имеем многопродуктовую задачу, в противном случае однопродуктувую. Если в задаче помимо базиса будем учитывать расход масла, то это многопродуктовая задача. 5.По виду целевой функции на задачу с пропорционными и не пропорциональными затратами. Так затраты не 1км. Машины могут быть пропорциональными.
Метод множителя Лагранжа. В мат. анализе существуют задачи на условный экстремум, если среди ограничений нет неравенств при условиях неотрицательности, то тогда задача приводится к виду: z=f(x1,x2…xn) max(min); Эта задача не линейного программирования, и эти задачи называются классическими задачами оптимизации. Их можно решать пот крайне мере, методами дифференциального исчисления. В простейшем случае условным экстремумом функции 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х1+а12х2≥в1 а21х1+а22х2≥в2 а31х1+а32х2≥в3 а41х1+а42х2≥в4 а51х1+а52х2≥в5 F=C4x1+C2x2→min К этому же виду приводится задача на смеси: бензин различных сортов получают путем смешивания нефти продуктов, имеющих разные химические характеристики, но их количество должно выдерживаться точно. Задача об использовании сырья. Для изготовления двух видов продукции, требуется сырье 5-ти видов. Доход получаемый от реализации продукта П1 и П2, будет соответственно S1 и S2. а11х1 +а12 х2=в1 а21 х1 +а22 х2 =в2 а31 х1 +а32 х2 =в3 а41 х1+ а42 х2 =в4 а51 х1+а51 х2 =в5 F=C1x1+C2x2→max
  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...  Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
(x1x2…xn)=bi(i=1 
)
-опт. решение
Если хотя бы для одного цикла она отрицательна, то план можно улучшить.
. План оптимален, если для каждой свобод. клетки Sij≥0. Если есть отрицательные оценки, то переходят к новому плану по правилам распределительного метода. В новом плане определяется потенциалы строк и столбцов. Вычисляются оценки для всех свободных клеток. Когда среди оценок не окажется отрицательных полученный план будет оптимальным.