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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

20)Двойственный  симплекс-метод

Алгоритм двойственного  симплекс-метода

Этап 1

1) Просматриваем коэффициенты  f-ой строки, если все они неотрицательные то переходим к пункту 1 этапа 2

2) если в f строке имеется отрицательный коэффициент то выделяем столбец содержащий этот коэффициент.

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

4) вычисляют двойственное  отношение (отношение элементов  f строки к элементам разрешающей строки). Наименьшее из отношений определяет разрешающий столбец.

5) с найденным разрешающим  элементом делают шаг обыкновен. жордановых исключений. Анализ новой таблицы делают из п. 1

Этап 2.

1) Просматривают столбец  свободных членов, если все элементы  столбца неотрицательные то оптимальное решение достигнуто.

2) Если в столбце свободных  членов есть отрицательные элементы  то среди них находят наименьший . Этот элемент определяет разрешающую строку.

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

4) С найденным разрешающим  элементом делают один шаг  обыкновенных жордановых исключений.

Замечание : что бы найти макс. ф-ии следует произвести замену

F(x) = -f(x) и искать минимум полученной ф-ии.

 

 

 

21)ШПАК

 

 

 

 

 

 

 

 

 

22. Постановка  и математическая модель транспортной (ТЗ) по критерию стоимости в  матричной форме.

В m пунктов отправления А1, А2, …, Аm сосредоточен груз a1,a2,…,am.

Груз необходимо доставить  потребителям B1,B2,…,Bn; спрос потребителей b1,b2,…,bn.   Известна стоимость Cij перевозки ед. груза из i-того пункта отправления в j-ый пункт назначения. (i=1,m; j=1,n).   Составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе при этом суммарные транспортные издержки минимальны. Экономико-математическая модель (ТЗ)-транспортной задачи:,   xij- кол-во единиц груза, которе необходимо доставить из i-того пункта отправления в j-тый пункты назначения.   -матрица перевозок  

Удельные транспортные расходы  формируются в виде матрицы  и называются матрицей тарифов. Транспортная задача представляется в виде таблицы которая называется распределительной или матричной моделью транспортной задачи. В Математической форме ограничительные условия ТЗ:

поставщики	потребитель				Запас груза, ai
	В1	В2	…	Bn
	Затраты на перевозку ед. груза, доставка
А1	C11      x11	C12      x12	…	C1n      x1n	a1
А2	C21      x21	C22      x22	…	C2n      x2n	a2
…	…	…	…	…	…
Аn	Cm1      xm1	Cm2      xm2	…	Cmnxmn	am
потребность в грузе, bj	b1	b2	…	bn

Цель транспортной задачи min-ть общие затраты на реализацию плана перевозок.

 

Среди множества решений  системы (5.1) требуется найти такое  решение при котором линейная функция (5.3) или f принимает min значение.

Будем называть план перевозок допустимым если он удовлетворяет условиям (5.1) и (5.2).

Допустимый план перевозок  доставл-ийmin целевой ф-ии (5.3) наз-сяоптимальным.

 

 

23. Теорема о  существовании допустимого плана  ТЗ.

Для того чтобы ТЗ имела  допустимые планы необходимо и достаточно выполнение равенства:

(5.4)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

24. Закрытая и  открытая модели ТЗ. Теорема о  ранге матрицы ТЗ.

Модель ТЗ называется закрытой если суммарный объем груза имеющийся у поставщиков равен суммарному спросу потребителей.

 

Если для транспортной задачи вып-ся одно из условий:

(5.6)

, то модель  ТЗ называется открытой.

Для разрешимости ТЗ с открытой моделью необходимо преобразовать  ее в закрытую. При выполнении 1-ого условия необходимо ввести фиктивный (n+1)-й пункт назначения , т.е. в матрице ТЗ появится дополнительный столбец. Тогда спрос фиктивного потребителя полагают равным не балансу.

 

Все тарифы полагаются одинаковыми, но чаще всего равными 0.

Аналогично при выполнении 2-ого условия вводится фиктивный  поставщик  запас груза у которого равен

Тарифы дополнительной строки распределительной таблицы =0. (

Теорема 5.2 (О ранге  матрицы)

Ранг матрицы A ТЗ на 1 меньше числа уравнений r(A)=m+n-1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

25. Построение  исходного опорного плана ТЗ.  Правило «северо-западного угла»  и «минимального элемента» 

 

Построение производится в распределительной таблице.

Если в плане перевозок  перемен.хin а≠0, то это число записывается в клетку с адресом (i,k) и считаем ее занятой или базисной.

Если значение хik=0, то клетку оставляем свободной.

При этом число занятых  опорных планом клеток в которые с теорем 5.2 должно быть равно m+n-1, а остальные m*n-(m+n-1)=(m-1)(n-1)

Правило северо-западного  угла

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

В клетку (1.1) занесем меньшее из чисел

х11=min(а1, b1)

а1>b1→x11=b1

b1-полностью удовлетворен

в дальнейшем хi1=0 i=2,m

Двигаясь вправо по первой строке заносим в соседнюю клетку меньшее из чисел (a1-b1  и b2)

x12=min(a1-b1, b2)

Еслиa1-b1<b, то запасы 1 поставщика исчерпаны m 1 строка табл. в расчет не принимаем

Переходим к аналогичному 2 поставщику b1>a1

x11=min(b1,a1)=a1

при этом запас 1 поставщика будет исчерпан

x1k=0     k=2,n

1 строка из расчетов  исключается 

Переходим к распределению  запасов 2 поставщика

Заполнив таким образом клетку (1,2) (2,1) переходим к загрузке сл. клетки по 2 строке или по 2 столбцу

процесс распределения по 2,3, стр. ( столб) аналогичен.до тех пор, пока не исчерпаются ресурсы послзапол. (m,n)

Пример. Составит план перевозок зерна А1, А2, А3, А4  в которых запасы составл. соот. 800, 700,1000,500тыс.  перевезти на 3 элеватора В1, В2, В3 мощностью 1000, 1100, 900 тыс.ц Затраты на перевозку 1ц из прев.  в табл.

Район	Элеватор			Запас
	В1	В2	В3
	Затраты на перевозку
А1	3	5	6	800
А2	7	2	4	700
А3	4	3	5	1000
А4	6	4	7	500
Мощность элеватора	1000	1100	900	3000

 

 

Закрытая модель

 

 

	B1	B2	B3	ai
А1	800              3	5	6	800
А2	200              7	500               2	4	700
А3	4	600                3	400               5	1000
А4	6	4	500                7	500
bj	1000	1100	900

f(x1)=3*800+7*200+2*500+3*600+5*400+7*500=12100 ден.ед.

 

Правило минимального элемента

Просмотрев тарифы в заданной табл. и в первую очередь заполняется  клетка с мин значением тарифа. При этом в клетку записывается макс возможное значение поставки. Из рассмотрения исключаем строку, соот. поставщику, запасы которого израсходованы.или столбец соот. потребителя, спрос которого полностью удовлетворен.  Из оставшихся клеток слева выбираем клетку с найм. тарифом. Процесс распределения заканчивается когда все запасы исчерпаны, а спрос потребителя полностью удовлетворен. В результате получим опорный план, который должен содержать m+n-1 загруж. клеток. В процессе заполнения табл.могут одновременно исключатся строка и столбец, когда исчерпается запас груза и удовлетворен потребитель. То есть задача вырождается. В этом случае в свободную клетку необх. записывать число 0. Выполнить ноль-загрузку, условно считая, клетку занятой. Число 0 записывается в свободные клетки, которые не образуют цикла с ранее занятыми клетками.

Решим  предшествующую задачу по правилу мин. элемента.

Найменшие затраты соот. маршруту – А2В2

В клетку (2,2) – х22=мин(700,1000)=700

2 строка в дальнешем в расчет не принимается, так как запас зерна 700 полностью доставлен.

найм. тарифы имеют клетки (1,1) и (3,2)

С11=С32=3

х11=мин(800,1000)=800

х32=мин(1000,1100-700)=400

С31=С23=С42=4

х31=(1000-800, 1000-400)=200

х33=мин(1000-400-200=400

х43=500

План Х2=3*800+2*700+4*200+3*400+5*400+7*500=11300 ден. ед.

Х1=12100 де.ед .

 

 

26. Теорема о  потенциалах. Алгоритм решения  ТЗ методом потенциалов 

В соответствии с введением  понятиями потенциалов и с  учетом связей двойственных задач каждому  поставщику ограничение по запасам  поставим  в соответствие потенциал  ui(i=1,m) , потребителю (ограничение по спросу) потенциал vj(j=1,n)

По теореме о потенциалах  будет соответствовать уравнение ui+ vj=Сij

Т.к. занятых клеток должно быть m+n-1 на 1меньше число потенциалов, для опред. чисел необ. решить систему из m+n-1 cm+nнеизв. сист. неопред.

Для того чтобы найти част.одному из потенциалов прид. произведение величину, тогда ост. опред. одноз (обычно =0)

Для исслед. плана на оптимальность по каждой свободной клетке проверяетс условие ui+ vj<Сij

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

Sij=Cij-(ui+vj)<0

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

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

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

В результате баланс цикла  сохраняется.

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

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