Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

Понятие математического программирования. Классификация задач математического программирования

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

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

Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.

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

В зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:

· задачи линейного программирования,

· задачи нелинейного программирования;

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

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

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программы) для ЭВМ» не имеет, т.к. дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин «линейное программирование» возник в результате неточного перевода английского «linearprogramming». Одно из значений слова «programming» — составление планов, планирование. Следовательно, правильным переводом английского «linearprogramming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термины линейное программирование, нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

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

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

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

Существует несколько методов решения задач ЛП. В данной работе будут рассмотрены некоторые из них, в частности:

Графический метод решения задачи ЛП;

Решение задачи ЛП средствами табличного процессора Excel;

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

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

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

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

Решение задач методами динамического программирования проводится на основе сформулированного Р.Э.Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения.

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

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

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

Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить два типа переменных – переменную состояния S и переменную управления X. Переменная S определяет, в каких состояниях может оказаться система на данном k-м шаге. В зависимости от S на этом шаге можно применить некоторые управления, которые характеризуются переменной X. Применение управления X на k-м шаге приносит некоторый результатWk(S,Xk) и переводит систему в некоторое новое состояние S'(S,Xk). Для каждого возможного состояния на k-м шаге среди всех возможных управлений выбирается оптимальное управление X*k такое, чтобы результат, который достигается за шаги с k-го по n-й, оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана Fk(S) и зависит от номера шага k и состояния системы S.

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

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

В общем виде задача динамического программирования формулируется следующим образом: требуется определить такое управление X*, переводящее систему из начального состояния S0 в конечное состояние Sn, при котором целевая функция F(S0,X*) принимает наибольшее (наименьшее) значение.

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

задача оптимизации формулируется как конечный многошаговый процесс управления;

целевая функция является аддитивной и равна сумме целевых функций каждого шага

выбор управления Xk на каждом шаге зависит только от состояния системы к этому шагу Sk-1 и не влияет на предшествующие шаги (нет обратной связи);

состояние системы Sk после каждого шага управления зависит только от предшествующего состояния системы Sk-1 и этого управляющего воздействия Xk (отсутствие последействия) и может быть записано в виде уравнения состояния:

на каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние системы Sk зависит от конечного числа переменных;

оптимальное управление X* представляет собой вектор, определяемый последовательностью оптимальных пошаговых управлений:

число которых и определяет количество шагов задачи.

Условная оптимизация. Как уже отмечалось выше, на данном этапе отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем n-м шаге найти оптимальное управление X*n и значение функции Беллмана Fn(S) не сложно, так как

где максимум ищется по всем возможным значениям Xn.

Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге:

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый (на первом шаге k=1 состояние системы равно ее начальному состоянию S0), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге X1, применение которого приведет систему в состояние S1(S,x1*), зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнего n-го шага.

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

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ — конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой.

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

Классификация задач математического программирования

Основные понятия математического программирования.

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

В процессе решения задачи оптимизации обычно необходимо найти оптимальные значения некоторых переменных, определяющих данную задачу. Примерами таких переменных являются: численность исполнителей, станков, машин и др. Число переменных (обозначим их X1, X2. Хn, где n — число переменных) характеризует степень сложности задачи оптимизации.

Читать еще:  Предикат в программировании это

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

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

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

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

Обозначим ограничения следующим образом:

Запись означает, что в ходе решения оптимизационной задачи сле­дует найти оптимальное значение «m» переменных с учетом налагаемых на них (m) ограничений. В общем случае как целевая функция, так и ограничения могут быть нелинейными функциями всех или некото­рых из рассматриваемых переменных.

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

1.2. Общая задача математического программирования.

Сформулируем общую задачу математического программирования.

Дадим количественную, математическую постановку этой задачи.

Найти значения «n» переменных X1, X2. Хn , которые неотрицательны

Xi 0, i=1,2,…,n

удовлетворяют «m» ограничениям:

и максимизируют функцию:

Z=F(X1,X2,…,Xn) MAX

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

Классификация задач математического программирования

В основе той или иной классификации лежит признак, по которому объекты разделяются или объединяются в классы.

Признак первой (из двух предлагаемых) классификации задач матема­тического программирования — вид функции цели, вид ограничений и наличие или отсутствие целочисленности переменных, описывающих про­цесс или систему.

Если функция цели и ограничения являются линейными:

Z=F(X1,X2,…,Xn)=C1X1+C2X2+…CnXn MAX;

где (Ci),(Bj),(Aij) — известные постоянные, то данная задача является задачей линейного программирования.

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

Частным случаем задач нелинейного программирования являются задачи целочисленного программирования. От задач линейного программирования они отличаются только наличием условия целочисленности переменных X1, X2. Хn.

Если целевая функция задачи математического программирования квадратичная, но все её ограничения линейны, то такую задачу называют задачей квадратичного программирования. Линейные ограниче­ния, для данной задачи записываются так же как для задачи линейного программирования, а целевая функция имеет вид:

В качества примера рассмотрим следующую задачу квадратичного программирования:

Z=F(X1,X2)=X1*X2 MAX;

Отдельным классом задач математического программирования являются задачи динамического программирования. Эти задачи характеризуются многоэтапным процессом поиска оптимального решения.

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

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

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

— задача управления запасами;

— задачи замены оборудования;

— задача выбора оптимальных режимов движения;

— задача выбора оптимальной структуры.

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

Примерами распределительных задач являются:

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

задача о назначении, в которой рассматривается вопрос об опти­мальном прикреплении производителя работ к объекту производст­ва;

задача о рюкзаке — которая рассматривает оптимальное размещение в нем (рюкзаке) набора взаимозаменяемых предметов (например, за­дача о загрузке самолета, задача о снаряжении экспедиции и др.);

задача o выборе рациона;

задача выбора применения ресурсов;

задача выбора типажа и другие задачи.

Задача управления запасами формулируется следующими образом: имеется некоторое количество запасов, хранение которых связано с расходами. Однако и отсутствие запасов иногда недопустимо или при­водит к расходам. Требуется найти такой размер запасов(или порядок их пополнения), при котором расходы будут минимальными.

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

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

Задача выбора оптимального режима движения заключается в выборе маршрута (координат и скорости), удовлетворяющего заданным ограничениям (по производству, по техническим параметрам движущегося объекта), проходящего в заданных условиях и оптимального по зат­ратам ресурсов (время, топливо, стоимость).

Задача поиска сводится к отысканию оптимального плана поиска объектов. Например: объектов противника, неисправностей, брака, полезных ископаемых и др.

В заключение еще раз подчеркнем большой экономический эффект от применения методов математического программирования на практике.

Общая постановка задачи о принятии решения

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

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

Математическое программирование является одним из разделов исследования операций – прикладного направления кибернетики, используемого для решения практических организационных задач. Задачи математического программирования находят применение в различных областях человеческой деятельности, где необходим выбор одного из возможных образов действий (программ действий).

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

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

Под принятием решений в исследовании операций понимают сложный процесс, в котором можно выделить следующие основные этапы:

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

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

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

3-й этап. Исследование влияния переменных на значение целевой функции. Этот этап предусматривает владение математическим аппаратом для решения математических, задач, возникающих на втором этапе процесса принятия, решения.

Широкий класс задач управления составляют такие экстремальные задачи, в математических моделях которых условия на переменные задаются равенствами и неравенствами. Теория и методы решения этих задач как раз и составляют содержание математического программирования. На третьем этапе, пользуясь математическим аппаратом, находят решение соответствующих экстремальных задач. Обратим внимание на то, что задачи математического программирования, связанные с решением практических вопросов, как правило, имеют большое число переменных и ограничений. Объем вычислительных работ для нахождения соответствующих решений столь велик, что весь процесс не мыслится без применения современных электронных вычислительных машин (ЭВМ), а значит, требует либо создания программ для ЭВМ, реализующих те или иные алгоритмы, либо использования уже имеющихся стандартных программ.

4-й этап. Сопоставление результатов вычислений, полученных на 3-м этапе, с моделируемым объектом, т. е. экспертная проверка результатов (критерий практики). Таким образом, на этом этапе устанавливается степень адекватности модели и моделируемого объекта в пределах точности исходной информации. Здесь возможны два случая:

Читать еще:  Сведение игры к задаче линейного программирования

1-й случай. Если результаты сопоставления неудовлетворительны (обычная ситуация на начальной стадии процесса моделирования), то переходят ко второму циклу процесса. При этом уточняется входная информация о моделируемом объекте и в случае необходимости уточняется постановка задачи (1-й этап), уточняется или строится заново математическая модель (2-й этап), решается соответствующая математическая задача (3-й этап) и, наконец, снова проводится сопоставление (4-й этап).
2-й случай. Если результаты сопоставления удовлетворительны, то модель принимается. Когда речь идет о неоднократном использовании на практике результатов вычислений, возникает задача подготовки модели к эксплуатации. Предположим, например, что целью моделирования является создание календарных планов производственной деятельности предприятия. Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.

В математическом программировании можно выделить два направления.

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

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

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

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

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

Выпуклое программирование – целевая функция выпукла (если рассматривается задача ее минимизации) и выпукло множество, на котором решается экстремальная задача.,

Квадратичное программирование – целевая функция квадратичная, а ограничениями являются линейные равенства и неравенства.

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

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

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

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

Основные задачи математического программирования

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

В общем виде математическая постановка экстремальной за­дачи состоит в определении наибольшего или наименьшего зна­чения целевой функции f (х1, х2, . xn) при условиях gi (х1, х2, . xn) £ b, (i = 1, m), где f и gi – заданные функции, a bi – неко­торые действительные числа.

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

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

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

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

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

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

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

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

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

Выделяют отдельные классы задач стохастического и дина­мического программирования.

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

Задача, процесс нахождения решения которой является мно­гоэтапным, относится к задаче динамического программирова­ния.

3.9. Линейное программирование: экономическое планирование и геометрическая интерпретация

Линейное программирование в соответствии с его происхождением следует подробнее расшифровать так: “Составление оптимальных планов производства на основе линейных экономических моделей”. Из экономики название перешло в общие математические исследования линейных задач оптимизации, т.е. задач об экстремумах линейных целевых функций при ограничениях в виде линейных неравенств и линейных уравнений.

В качестве примера экономической задачи планирования решаемой с помощью линейного программирования рассмотрим завод, вы­пускающий два вида кафельных плиток для настила пола; для изго­товления каждого вида требуется одинаковое количество сырья, т. е. песка, гравия и цемента, но один вид плитки окрашивается и требует некоторого количества красящего вещества. На производство тонны окрашенной плитки требуется два часа машинного времени, три часа рабочего времени и два литра краски. Для производства тонны пли­ток второго типа (без краски) требуется час машинного времени, три часа рабочего времени и не требуется краски. Доход от производства плиток первого типа составляет 3 ф. ст. (фунта стерлингов), а от производства плиток второго типа – 2 ф. ст. Всего в наличии имеется 10 ч. машинного времени, 24 ч. рабочего времени и 8 л кра­ски. Требуется определить, сколько тонн плиток каждого типа следу­ет произвести, чтобы получить максимальную прибыль.

Приведенную выше информацию можно представить в форме таблицы.

Пусть произведено х1 тонн плиток первого типа и х2 тонн – второго типа. Переменные х1 и х2 не могут принимать отрицательные значе­ния и должны удовлетворять условиям

Из первой строки таблицы видно, что для производства x1 тонн плиток первого типа требуется 2×1 часов машинного времени, а для x2 тонн плиток второго типа – x2 часов. Общее количество машинного вре­мени не должно превышать 10 ч. Алгебраически это можно выразить в виде

Для тех же аргументов x1 и x2 из следующих двух строк таблицы получаем:

Таким образом, всего имеется три ограничения:

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

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

Достаточно одного взгляда на ограничения и целевую функцию, чтобы заметить, что они все линейны: ни одно из них не содер­жит обратных величин, произведений или высших степеней х1 или х2. Поэтому задача называется задачей линейного программирования.

Так как в задаче всего две переменные х1 и х2, оптимальную программу можно получить графически. Рассматривая сначала в ограничениях знаки равенства, получаем:

Эти уравнения представляют собой уравнение трех прямых линий (см. рис. 9). Горизонтальная ось этой диаграммы представляет х1, а. вертикальная ось – х2. Прямая АВ, представляющая первое урав­нение из последней системы, пересекает оси координат в точках х1 = 5 и х2 = 10- Пря­мая ЕА, представляющая второе уравнение, пересекает эти оси в точ­ках х1 = 8 и х2 = 8, а линия DB, представляющая третье уравнение, пересекает горизонтальную ось в точке х1 = 4.


Согласно ограничениям (2.5), переменные могут принимать только неотрицательные значения, таким образом, все допустимые решения представлены точками на оси Xi или над ней, а также на оси х^ или справа от нее. Последнее неравенство (2.6) ограничивает допустимые значения Xi точками на линии DB или слева от нее. Аналогично, пер­вые два неравенства запрещают допустимым точкам лежать над пря­мой АВ и справа от прямой ЕА. Эта задача, как говорят, ограничена и граница допустимой области показана на рисунке штриховкой. Мно­жество точек внутри границы является допустимым решением задачи. Однако из этого множества представляет интерес только оптималь­ное решение.

Рис.2.9.1. – Графическое решение задачи линейного программирования

Уравнения целевой функции представляют семейство параллельных прямых, и, задавая определенное значение Z, на этой же диаграмме можно получить одну из этих прямых. Например, если положить Z = 12, то полученное в результате уравнение 12 = 3х1 + 2х2 есть прямая линия, пере­секающая горизонтальную ось при х1 = 4, а вертикальную ось – при х2 = 6, как показано на рис. 9. Аналогично получают­ся другие прямые, и чем даль­ше линия от начала координат, тем больше значение целевой функции. В точке В х1 = 4 и х2 = 2. Подставляя эти значе­ния в целевую функцию, получаем Z = 16. Линия, представляющая Z =16, также изображена на рис. 9, причем она, как и следовало ожидать, проходит через точку В. В точке А, где пересекаются линии (1) и (2), х1 = 2 и х2 = 6; подставляя эти значения в целе­вую функцию, получаем Z = 18. Эта линия, очевидно, наиболее удалена от начала координат. Значения Z, представ­ленные линиями, более удаленными от начала координат, чем Z = 18, дают недопустимые решения. Таким образом, максимальная прибыль достигается при производстве 2 т плиток первого типа и 6 т – вто­рого типа при общей прибыли 18 ф. ст.

Читать еще:  Безопасный режим не запускается

Отметим, что из всех точек особое внимание было обращено на узлы В и А. Можно доказать, что в этой и любой другой задаче линей­ного программирования оптимальное программирование всегда лежит в узле, где пересекаются две линии или более. Это возможно только в том случае, если график целевой функции не параллелен ни одной из граничных линий, в противном случае все точки этой линии дают оптимальное решение. Поэтому достаточно свести процесс исследо­вания к рассмотрению этих узлов. На рис. 9 таковыми являются точки О, D, В, А и Е. Начало координат (точка О), где х1 = 0 и х2 = 0, является допустимой точкой, и процесс исследования начинается с нее.

Для того, чтобы выяснить, сколько осталось неиспользованных времени и краски, значения переменных, заданные оптимальной про­граммой, подставляют в ограничения. При х1 = 2 и х2 = 6 левая часть первого неравенства-ограничения становится равной 10, следовательно, все имеющееся в наличии машинное время израсходовано. Аналогично, подстановка этих значений х1 и х2 во второе неравенство показывает, что его левая часть также равна 24 и, таким образом, была использо­вана вся наличная рабочая сила. Говорят, что оба первых ограниче­ния являются действенными, или критическими. Наконец, последнее ограничение показывает, что при производстве 2 т плитки первого типа остаются неиспользованны­ми 4 л краски. .

Рассмотренный пример показывает, что задачи программирова­ния связаны с повседневным промышленным производством. В случае двух переменных задачу можно решить графически, даже если про­граммирование нелинейно. Однако в большинстве случаев на прак­тике в задаче содержится более двух переменных и необходимо применять аналитические методы их решения.

При решении задачи ЛП возможны различные случаи (см, рис. 10 – ), необходимо уметь в них разбираться. Нестандартные ситуации, отсутствие решения могут возникнуть из-за неправиль­ной, неполной постановки задачи, из-за ошибок в подготовке данных на ЭВМ и т. д. Программы для ЭВМ должны определять такие ситуации и сообщать о них пользователю, а пользователь должен понимать эти сообщения.

Рис. 2.9.2. – Плоское графическое изображение условий задачи ЛП. Изо­бражение ограничений такое же, как на рис. 1. Целевая функция изобра­жена пиниями одинакового уровня z = 30, z = 42, z = 18 и др. По ним видно, что min z на множестве W достигается в точке D на пересечении прямых 4 и 6. Треугольник ОBЕ – первый симплекс, рассматриваемый при поиске допустимой точки симплекс-методом

Для решения задач ЛП чаще всего применяют симплекс-метод* (СМ), основанный на их алгебраизации, разработанной Дж. Данцигом и его школой. Это, подобно методу Гаусса решения линейных систем уравнений, конечный процесс, в прин­ципе дающий точный результат за конечное число вычислительных операций. Однако исследования сложности алгоритма СМ пока­зывают, что иногда это число может быть астрономически большим, и тогда решение недоступно никаким ЭВМ. Хотя расчетный опыт показывает, что такие «плохие» задачи почти не встречаются, в математике ведутся разработки более быстрых способов. Ока­зывается, для больших задач быстрее работают методы последова­тельных приближений и др. Несмотря на это, СМ в различных вариантах остается самым популярным для задач ЛП, особенно небольшой размерности.

Поясним идею СМ применительно к стандартной задаче ЛП (см. рис. 10). Очевидно, минимум или максимум линейной функ­ции z достигается в одной из вершин многогранника допустимых точек SI (возможно, в двух или нескольких вершинах — тогда нам нужна одна из них). Поиск точки минимума сводится к це­ленаправленному перебору вершин итак, чтобы функция z(x) уменьшалась. Но сначала надо найти одну из них.

Математическое программирование

Лекция 1,2.

Профессиональный отбор

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

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

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

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

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

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

Понятие об оптимизационных задачах. Задача линейного программирования (ЗЛП). Графический метод решения ЗЛП.

Вопросы:

1. Предмет – математическое программирование, краткая классификация методов.

2. Основные понятия теории оптимизации.

3. Постановка ЗЛП, различные формы записи. Примеры экономических задач.

4. Графический метод решения ЗЛП. Основные свойства ЗЛП.

1. Предмет – математическое программирование.

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

Современные промышленные предприятия, предприятия бытового обслуживания, транспортные агентства, научно-технические организации представляют собой сложные системы «человек-машина». Эффективность работы таких систем зависит от качества организационного управления. Чтобы добиться качества современному руководителю не всегда бывает достаточно личного опыта, интуиции и организаторских способностей в их традиционном понимании. При формировании стратегических и тактических решений руководитель должен учитывать множество подчас противоречивых соображений, опираться на сложные критерии эффективности путей достижения конечных целей. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику. Такие методы объединяются под общим названием – математическое программирование.

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

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

— в экономике – для решения больших макроэкономических моделей (типа модели Леонтьева и др.), микроэкономических моделей или моделей предпринимательства, для оптимизации технико-экономических систем (планирование, эконометрика), транспортные задачи, в теории принятия решений, теории игр и т.п.;

— в технике – управление размерами и оптимизация структур, оптимальное планирование сложных технических систем, как информационные системы, сети компьютеров, транспортные и телекоммуникационные сети и др.;

— в автоматике – распознавание систем и объектов, оптимальное управление системами, фильтрация, роботы, автоматизированные линии и т.п.;

— в медицине, политике, социологии и т.п., и т.д.

Дадим ряд определений.

— Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием оптимальности.

— Экономические возможности формализуются в виде системы ограничений.

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

— совокупность неизвестных величин х = (х1, х2, …, хn), действуя на которые систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, стратегией, поведением и т.п.);

— целевую функцию, которая позволяет выбрать наилучший вариант из множества возможных. Целевая функция обозначается F(x). Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности и т.д.;

— условия (система ограничений), налагаемые на неизвестные величины. Эти условия следуют из ограниченности ресурсов, которыми располагает общество, из необходимости удовлетворения насущных потребностей, из условий производственных и технологических процессов. Математически ограничения выражаются в виде уравнений и неравенств. Их совокупность образует область допустимых решений.

Т.о., модель задачи математического программирования примет вид:

Найти план х = (х1, х2, …, хn), доставляющий экстремальное значение целевой функции F(x)max(min), при ограничениях gi(x) ≤ (=, ≥) bi, i=.

Из экономических или физических соображений на план задачи или некоторые его компоненты, как правило, налагаются условия неотрицательности, хj≥ 0, иногда – целочисленности.

План х, удовлетворяющий системе ограничений задачи, называют допустимым. Допустимый план, доставляющий целевой функции экстремальное значение, называют оптимальным.Оптимальный план обозначают х*, экстремальное значение функции F(x*) = F*.

В зависимости от особенностей целевой функции F(x) и функций ограничений gi(x), задачи математического программирования делятся на ряд типов.

1. Задача линейного программирования (ЗЛП) – задача оптимизации линейной функции при линейных ограничениях.

2. Задача нелинейного программирования (ЗНП) – задача оптимизации нелинейной функции при ограничениях или без них (когда или F(x) и/или gi(x) нелинейны).

3. Задача дискретного (в частности целочисленного) программирования – Задача оптимизации, в которой на переменные наложено дополнительное требование принимать лишь дискретные (в частности целочисленные) значения.

4. Задача динамического программирования – задача оптимизации динамических систем (т.е. развивающихся с течением времени).

5. Задача вероятностного или стохастического программирования – задача оптимизации, содержащая случайные величины.

Ссылка на основную публикацию
Adblock
detector