7. Общий вид задач лин-го программир-я (лп).

Они явл-ся наиболее простыми среди задач исследования операций, где выбор показ-лей эф-ти (целевой f-ции) W достаточно явно диктуется целевой направлен-тью задачи, а ее усл-я – известны заранее (детерминирован.случай). W=W (,x), где  - факторы, налагаемые на эл-ты решения х некоторые огранич-я. Wmax (min). Трудности, возникающие при решении задач мат.программир-я, зависят: ф)от вида f-ной завис-ти, связывающей W с эл-тами решения; б)от «размер-ти» задачи, т.е.от кол-ва эл-тов решения х₁, х₂, …, х_n; в)от вида и кол-ва огранич-й, наложенных на эл-ты решения. Д/задач ЛП хар-но: 1)показ-ль эф-ти (цел.f-я) W линейно зависит от эл-тов решения х₁, х₂, …, х_n; 2)огранич-я, налагаемые на эл-ты решения, имеют вид лин.нерав-в или ур-й относ-но х₁, х₂, …, х_n. К задачам ЛП относ-ся задачи распред-я ресурсов, планирования произв-ва, орг-ции работы транспорта.

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

Обратные задачи отвечают на вопрос: как выбрать решение х д/того, чтобы показ-ль эф-ти W обратился в мах? Если число возможных вариантов решения, образующих множ-во Х, невелико, то можно попросту вычислить величину W д/каждого из них, сравнить между собой получ-е знач-я и непоср-венно указать 1 или неск-ко опт.вариантов, д/ктр W достигает мах. Такой способ нахожд-я опт.решения наз-ся «простым перебором». Сейчас мы ограничимся постановкой задачи опти­мизации решения (обратной задачи исследования опе­раций) в самой общей форме. Пусть имеется некот-я операция Q, , па успех ко­т-й мы можем в какой-то мере влиять, выбирая тем или другим способом реш-е х (напомним, что х — не число, а целая группа параметров). Пусть эффек­тив-ть операции характер-ся одним показат-м W  max. Возьмем самый простой, так назыв-й «детерми­нированный» случай, когда все условия операции пол­ностью известны заранее, т. е. не содержат неопреде­л-ти. Тогда все факторы, от которых зависит ус­пех опер-и, делятся на две группы: 1) заданные, заранее известные факторы (условия выпол-я опер-и), кот-е мы д/краткости обозначим одной буквой а; 2) зависящие от нас элем-ты реш-я, образую­щие в своей совок-ти реш-е х. Заметим, что первая группа факт-в содержит, в частности, и огранич-я, налаг-е на реш-е, т. е. определяет область возм-х решений X. Показ-ль эффект-ти W зависит от обеих групп факторов W=W(,x), как х, так и а в общем случае — не числа, а сово­купности чисел (векторы), функции в т. д. В числе за­данных условий ее обычно присутствуют огран-я, налагаемые на эл-ты реш-я, имеющие вид ра­венств или неравенств. При заданном комплексе условий а. найти такое ре­шение х = х*, которое обращает показатель эффект-сти W в максимум. Эта задача принадлежит к классу так называемых «вариационных задач», хорошо разработ-х в мате­матике. Самые простые аз таких задач («задачи на максимум и минимум») знакомы каждому инженеру. Чтобы найти максимум или минимум (короче, «экстре­мум») ф-я многих аргументов, надо продифферен­цировать ее по всем аргументам (в данной случае — элементам решения), приравнять производные нулю и решить полученную сис-му уравн-й. Метод поиска экстремума и связанного с ним опти­м-го решения х* должен всегда выбираться исхо­дя из особен-й функции W и вида ограни-й, накладыв-х на реш-е. #, если фун-я W линейно зависит от элем-в реш-я X₁, Х₂, ..., а огран-я, налагаемые на X₁, Х_2,.. имеют вид линейных равенств или неравенств, возникает ставшая классич-й задача лин-го программи­р-я, кот-я решается сравн-но простыми, а главное, станд-ми методами. Д/оптимизации управл-я многоэтапными опер-ми примен-ся метод динамического програм-я . Наконец, сущ-ет целый набор чис­л-х методов отыскания экстремумов, специально приспособленных для реализации на ЭВМ; некот-е из них включают элемент «случайного поиска», кото­рый д/многомерных задач нередко оказывается эф­фективнее упорядоченного перебора. Т. О., задача нахождения оптимал-го реш-я в простейшем, детерминированном случае есть чисто математ-я задача, принадл-я к классу вариационных (при отсутствии или наличия ограничений), кот-я может представить вычислит-е, но не принцип-е трудности. В предыдущем мы рассмотрели обратную задачу исследования опер-й в детерминированном случае, когда показатель эффективности W зависит только от двух групп факторов: заданных, заранее из­вестных а и элементов решения х. Реальные задачи исслед-я опер-й чаще всего содержат помимо этих двух групп еще одну — неизвес-е факторы, кот-е в совок-ти мы обозначим одной буквой . Итак, показатель эффект-ти W зависит от всех трех групп факторов: W=W(, х, ). Так как величина W зависит от неизв-х фак­торов, то даже при заданных а и х она уже не мо­жет быть выч-на, остается неопред-й. Задача поиска оптимал-го реш-я тоже теряет определ-ть. # 1: планируется ассортимент товаров на распродажи на ярмарке. Желат-но было бы максимиз-ть прибыль. Однако заранее неизвестно ни кол-во покуп-й, кот-е придут на ярмарку, ни потр-ти каждого покуп-ля. # 2: Проект-ся сис-ма сооруж-й, оберегающих район от паводков. Ни моменты их наступления, ни размеры заранее не известны. # 3: разрабатывается план вооружения страны на несколько лет вперед, но неизвестны ни конкретный противник, ни вооружения, кот-м он будет располагаться. Д/того, чтобы такие решения принимать современная наука располагает рядом приемов. Каким из них воспольз-ся — зависит от того, какова приро­да неизвестных факторов , откуда они возникают и кем контрол-ся. Классифицировать неопредел-ти по «родам» и «сортам». «Доброкачественный» вид неопредел-ти - это случай, когда неизв-е факторы  предст-т собой обычные объекты изу­чения теории вероятн-й — случайные велич-ны (или случайные фун-и), статистические харак­тер-ки кот-х нам известны или в принципе могут быть получены к нужному сроку. Такие задачи иссле­д-я операций мы будем называть стохастиче­скими задачами, а присущую им неопредел-ть — стохастической неопределен-ю. Возьмем самый гру­бый пример: пусть мы ведем обстрел какой-то цели, стремясь во что бы то ни стало попасть в нее. Произ­в-ся несколько выстрелов. Давайте заменим все случайные координаты точек попадания их математи­ческим ожиданием — центром цели. Получится, что любой выстрел с гарантией попадет в цель, что заве­домо неверно. Гораздо хуже обстоит дело, когда неизвестные факторы  не могут быть изучены и описаны статистич-ми методами. Это бывает в 2 случаях: либо распред-е вероятн-й д/параме-в  в принципе сущ-ет, но к моменту принятия решения не может быть получена. Либо распределение вероятн-й вообще не сущ-т. Пример ситуации типа а): проектируется информ-но вычислит-я система (ИВС), предназначен­ная д/обслужив-я каких-то случайных потоков требов-й (запросов). Вероятн-е характеристики этих потоков требов-й в принципе могли бы быть получены из статистики, если бы данная ИВС (или аналогичная ей) уже существ-ла и функционир-ла достаточно долгое время. Но к моменту создания проекта такой инф-и нет.