Шпаргалка по "Математике"

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

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

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

Мат. Модель задачи – отражение  оригинала( объекта моделирования) в виде ф-ций, уравнений, цифр, и т.д. Мат. Модель задачи включает:

1. Совокупность неизвестных величин

Х=(х1,х2, … ,хj, … ,хn)

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

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

Z=z(x)

Может означать прибыль, объем  затрат проиводства, уровень обслуживания/дефицитности, число комплектов …

3. Условия(система ограничений), которые налагаются на неизв. Величины. Они следуют из ограниченности ресурсов, которыми располагает общество

Нередко потребности превышают  возмодности их удовл-ния.

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

Совокупность всех условий, налагаемых на неизв. величины xj обозначим Ω. В таких обозначениях модель задачи МП примет вид:

Max(min) Z=z(x),   x∈ Ω

Требуется найти план Х=(х1,х2, … ,хj, … ,хn), доставляющий экстрем. Значение цел. Ф-ции Z=z(x).

Max(min) Z=z(х1,х2, … ,хj, … ,хn) при некот. Значениях φ==(х1,х2, … ,хj, … ,хn)<,>,=bi, i=1,m.

Из экономич. Соображений на план задачи или его компоненты(координаты) налагается условие неотрицательности(xj>0, j∈ Ω).иногда условие описывается как целочисленное.

План Х, удовл. Системе ограничений задачи – допустимый. Допустимый план, доставл. Ф-ции цели экстрем. Значение – оптимальный.

X*, z(x*)=Z*

 

 

 

 

 

 

 

 

Классификация методов  МП

В зависимости от особенностей цел. Ф. z(x), от ф-ций, задающих ограничения φi(x), задачи МП делятся на типы:

1. Если Z= z(x) и φi(x) линейны (1 степень) относительно входящ. В систему неизв. хj , тотакой раздел МП – линейное программирование (ЛП).

Методы и модели ЛП применяются  при оптимиз. Пр-сов пр-ва, при разраб. Пр-венной программы предприятия, определения наилучш. Ассортимента выпуск. Продукции, планировании грузоперевозок…

Широкое применение задачи ЛП нашли при решении задач  экономии ресурсов

2. Если в задаче МП цел. Ф-ция или хотябы 1 из φi(x) нелинейны, такой раздел называется нелинейным программирование НЛП. Методы НЛП получили широкое применение при расчете экон-ки выгодных партий запуска деталей в пр-во, при определении экон-ки выгодной партии поставки, размеров запасов, при распределении ограниченны ресурсов …
3. Если на все или некот. Xj наложено условие дискретности (целочисленности),то такие задачи рассм. В дискретном разделе МП, в частности – в целочисленном ЦП.

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

4. Если параметр цел. ф-ции и/или системы ограничен изменениями в времени, или цел. ф-ция имеет аддитивный вид( z(x)=∑Zj(xj) ), или мультипликативный ( z(x)=∏Zj(xj) ), или процесс выработки имеет многошаговый характер, такие задачи решаются методом динамического прогр-ния ДП.

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

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

Имеются численные методы решения задач с бесконечным  числом переменных (бесконечномерное программировние).

Задачи МП с одной цел. ф-цией решаются методами скалярной оптимизации.

 

 

 

 

 

 

 

 

 

 

 

2) Задачи линейного программирования (ЗЛП)

1. задача о наилучшем  использовании ресурсов

Пусть некот. Произв. Ед-ца исходя из своих технич. И технологич. Возможностей может выпускать n различных видов продукции, под номерами j=1,n. Ее будем обозначать Пj. Предприятие при произв.  Этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий и др. произв. Факторами. Виды огранич. Факторов – Rj. Их число равно m,  i=1,m. Они ограничены, их число равно соотв. b1, b2, … ,bn. Таким образом b=( b1, b2, … ,bn) – вектор ресурсов. Известна экономич. Выгода от пр-ва каждого вида продукции, исчислен. По отпускной цене товара, его прибыльности, издержкам производства, степени удовл. Потребителя, …   Примем в качестве такой меры цену Сj , С=(с1,с2,…,сn) – вектор цен.  Известны технологич. Коэф-ты aij, которыеуказывают, сколько треб. Единиц i-го ресурса для пр-ва 1-цы j-той продукции.  Х=(х1,х2, … ,хj, … ,хn) – план пр-ва, показывающий, какие виды товаров П1 … Пn нужно производить в каких количествах, чтобы обеспечить максимальный объем реализации имеющихся ресурсов. Цена реализованных xj единиц – cj*xj, а общий объем реализации –              z= c1*x1 +… +cn*xn – цел. ф-ция, которую нужно максимизировать.  Т.к. aij*xj – расход i-го ресурса на пр-во xj единиц j-той продукции, то просуммировав расход i-го ресурса на выпуск всех  n видов продукции, получим общий его расход, при этом ai1*x1+…+ ain*xn ≤bi.  Чтобы искомый план Х=(х1,х2, … ,хj, … ,хn) был реален, наряду с ограничениями на ресурсы необходимо учесть условие неотрицательности на объемы выпуска xj продукции (xj≥0).  Модель задачи примет вид: max Z =∑ cj*xj       (1)   ;∑ aij*xj≤bi   (2) ;  xj≥0           (3);задача (1) - (3) – задача ЛП, переменные xj входят в ф-цию Z(x), системы ограничения – только 1 степени.

2.Задача о выборе оптимальных  технологий

В этой задаче определяется оптимальный план выпуска продукции. Пусть при пр-ве  продукта использ. n технологий, при этом требуется m видов ресурсов, которые заданы объемами bi , i=1,m. Эффективность технологий по j-той технологии обозначим cj. Пусть aij – расход i-го ресурса в ед. времени по j-той технологии. В качестве неизвестного xj примем интенсивность использования j-той технологии. Пренебрегая временем переналадок, необходимых, необх. Для перехода от одной технологии к другой, получим мат. модель задачи: найти план интенсивности исп-ния технологий  Х=(х1,х2,…,хj,…,хn), обеспечивающий максимум выпуска продукции в стоимостном выражении:  max Z =∑ cj*xj   ; 

∑ aij*xj≤bi    ; xj≥0

3.Задача о смесях

Задача: получить продукцию  с заданными свойствами при наименьших затратах на исходные сырьевые материалы.  Модель такой задачи рассм. На примере задачи о диете:Имеются пищевые продукты № 1,…,n. Они содержат различные питат. Вещества 1,…,m. Единица j-го продукта содержит aij единиц i-го вещества. В нормальной жизнедеятельности в задан. Промежутках времени нужно потреблять не менее bi единиц питат. В-ва. Обозначим сj – стоимость единицы продукции j-го вида. Необходимо выбрать рацион минимальной стоимости, содерж. Необходимое количество пит. Вещ-в. План задачи – кол-во xj продуктов каждого вида, которое обеспечит необходимое количество питат. Вещ-в при миним. Затратах.  Мат модель:min Z =∑ cj*xj ;∑ aij*xj≥bi ;xj≥0

3)обыкновенные  и модифицированные жордановы  исключения

На числовом примере рассмотрим алгебраическое преобразование, ледащее  в основе удобного вычисления аппарата, используемого в МП

Пусть систему лин. Ф-ций

y1=2*x1-5*x2+4*x3

y2=8x1+2x2-3x3

зависящих от x1 ,x2, требуется преобразовать так, чтобы какие-либо две переменные (y2 b x3) поменялись ролями, т.е. y2 стала независимой, a x3 – зависимой переменными.

План: второе равенство разрешим относительно x3. Полученное выражение подставим вместо х3 в первое равенство, затем произведем упрощение. Система примет вид:

у1=((2(-3)-4*8)/-3)х1  +  (((-5)(-3)-4*2)/-3)х2   +  4у2/-3

х3=-8х1/-3  -  2х2/-3  +  у2/-3

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

	Х1	Х2	Х3
У1	2	-5	4
У2	8	2	-3

 

	Х1	Х2	У3
У1	=((2(-3)-4*8)/-3)	(((-5)(-3)-4*2)/-3)	4/-3
Х3	-8/-3	2/-3	1/-3

Опишем суть жорданова  исключения

Пусть дана система m ф-ций у1…ym от n неизвестных х1…хn,                  yi=∑ aij*xj   (10). aij – постоянные величины. Представим систему в форме таблицы:

	х1	…	xj	…	xs	…	xn
y1	a11	…	a1j	…	a1s	…	a1n
…	…	…	…	…	…	…	…
yi	ai1	…	aij	…	ais	…	ain
…	…	…	…	…	…	…	…
yk	ak1	…	akj	…	aks	…	akn
…	…	…	…	…	…	…	…
ym	am1	…	amj	…	ams	…	amn

Жорданова таблица

Выберем из (10) какое-либо уравнение (k-тое).

yi=∑ akj*xj     (11)

Предположим, что хs в (11) отличен от 0, зн. aks≠0. Представим себе систематизир. Алгебраич. Операцию перераспределения ролей между зависимой переем. Yk и независимой xs.

          (12)

Подстановки (12) во все остальные уравнения системы (10) приведение подобных членов и записи преобразованной таким образом системы в виде жордановой таблицы – шаг обыкновенного жорданового сключения, произведенный над таблицей 3 с разрешающим элементом aks.

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

       (13)

Обозначим в системе (13):

,  i≠k, j≠s.    (14)

Тогда (13) запишется в виде:

 

Преобразованную систему  запишем в виде жордановой таблицы:

	X1	…	yk	…	xn
Y1	B11	…	Ais/aks	…	bin
…	….	…	…	…	…
xs	-Ak1/aks	…	1/aks	…	-Akn/aks
…	…	…	…	…	…
ym	Bm1	…	Ais/aks	…	bmn

Вывод: один шаг обыкновенных жордановых исключений с разрешабщим элементом aks переводит табл.3 в табл.4 по схеме:

1. Разрешающий элемент заменяется обратной величиной
2. Остальные элементы разрешающей строки делятся на разрешающий элемент и меняют знаки
3. Остальные элементы разрешающего столбца делятся на разрешающий элемент
4. Прочие элементы вычисляются по (14)

На практике удобно использовать правило прямоугольника:

Рассм. Фрагмент табл.3 содержащий элементы, входящие в (14):

	aij		ais
	akj		[aks]