Invest-currency.ru

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

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

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

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

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

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

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

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

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

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) уменьшалась. Но сначала надо найти одну из них.

Лекция 3: Математическое программирование. Линейное программирование. Виды задач линейного программирования. Постановка задач линейного программирования и исследование их структуры. Решение задач линейного программирования симплекс-методом

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

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

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

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

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

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

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

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

2. Понятие линейного программирования. Виды задач линейного программирования

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

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

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

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

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

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

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

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

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

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

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

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

Найти

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

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

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

  • Определение границ системы оптимизации
    • Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается
  • Выбор управляемых переменных
    • «Замораживаем» значения некоторых переменных (неуправляемые переменные). Другие оставляем принимать любые значения из области допустимых решений (управляемые переменные)
  • Определение ограничений на управляемые переменные
    • … (равенства иили неравенства)
  • Выбор числового критерия оптимизации
    • Создаём целевую функцию

История

Задачи линейного программирования были первыми, подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 г. Ж. Фурье и затем в 1947 г. Дж. Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции — симплекс-метод, ставший основным при решении задач линейного программирования.

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

Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 30-м годам ХХ столетия. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман, знаменитый математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя; советский академик, лауреат Нобелевской премии (1975 г.) Л. В. Канторович, сформулировавший ряд задач линейного программирования и предложивший (1939 г.) метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода.

Читать еще:  Запись выражений на языке паскаль

В 1931 г. венгерский математик Б. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название «проблема выбора», метод решения получил название «венгерского метода».

Л. В. Канторовичем совместно с М. К. Гавуриным в 1949 г разработан метод потенциалов, который применяется при решении транспортных задач. В последующих работах Л. В. Канторовича, В. С. Немчинова, В. В. Новожилова, А. Л. Лурье, А. Брудно, А. Г. Аганбегяна, Д. Б. Юдина, Е. Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение её методов к исследованию различных экономических проблем. Методам линейного программирования посвящено много работ зарубежных ученых. В 1941 г. Ф. Л. Хитчкок поставил транспортную задачу. Основной метод решения задач линейного программирования — симплекс-метод — был опубликован в 1949 г Дж. Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Г. Куна (англ.), А. Таккера (англ.), Гасса (Gass S. I.), Чарнеса (Charnes A.), Била (Beale E. M.) и др.

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

Начиная с 1955 г опубликовано много работ, посвященных квадратическому программированию (работы Била, Э. Баранкина (Barankin E.) и Дорфмана (Dorfman R.), Франка (Frank M.) и Вольфа (Wolfe P.), Г. Марковица и др.). В работах Денниса (Dennis J. B.), Розена (Rosen J. B.) и Зонтендейка (Zontendijk G.) разработаны градиентные методы решения задач нелинейного программирования.

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

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

Лекция 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. Задача вероятностного или стохастического программирования – задача оптимизации, содержащая случайные величины.

Ссылка на основную публикацию
ВсеИнструменты 220 Вольт
Adblock
detector