Методические указания по курсу \"Спецглавы высшей математики\" Под редакцией А. К. Гущина icon

Методические указания по курсу "Спецглавы высшей математики" Под редакцией А. К. Гущина



НазваниеМетодические указания по курсу "Спецглавы высшей математики" Под редакцией А. К. Гущина
А.К.Гущина
Дата конвертации06.11.2012
Размер335.34 Kb.
ТипМетодические указания

Государственный комитет СССР по народному образованию

В.В.Грошев, А.К.Гущин

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Под редакцией А.К.Гущина


Издательство МГТУ

1989


ПОСТАНОВКА ЗАДАЧИ ЛП

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

Пример 1 (оптимальное планирование производства).

Предположим, производственное объединение, состоящее из q предприятий A1 , …, Aq имеет план по выпуску продукции: за время Т выпустить Ni , единиц продукции вида Рi (I=1, 2, 3, …, p). Пусть предприятие Aj производит ajk единиц продукции вида Pk в единицу времени. Расходы, связанные с изготовлением каждого из видов продукции, на том или ином предприятии различны. Цусть Cjk выражает цену единицы рабочего времени предприятия Aj при из­готовлении продукции вида Pk . Требуется составить наиболее рациональный план работы предприятий, т.е. найти, сколько вре­мени каждое из предприятий должно быть занято изготовлением каждого из видов продукции Pk , с тем чтобы стоимость всей про­дукции объединения была минимальной и при этом был бы выполнен план как во времени, так и по номенклатуре. Исходные данные за­дачи можно свести в табл.1.


Таблица 1.





P1

P2

P3

….


Pp

A1

a11

c11

a12

c12

a13

c13

……

a1p

c1p

A2

a21

c21

a22

c22


a23

c23

……

a2p

c2p

…..

……

……

……

……

……

Aq

aq1

cq1


aq2

cq2

aq3

cq3

……

aqp

cqp


Теперь приведем математическую формулировку описанной задачи. Пусть xij –время работы I-го предприятия по изготовлению продукции Pj. Реализация плана по времени озгначает, что выполнены неравенства

 x11+ x12 + …+ x1p  T

……………

 xi1 + xi2 +…+ xip  T (1)

……………

 xq1 + xq2 + …+ xqp  T

Левая часть i-го неравенства выражает общее время работы i-го предприятия Аi . При этом предприятие Аi изготовит аijxij единиц продукции Рi и для обеспечения плана по ассортименту должны выполняться равенства


a11x11 + a21x21+ …+ aq1xq1 = N1

……………………………….. (2)

a1px1p + a2px2p+ …+ aqpxqp = Np


Общая стоимость всей продукции объединения составит


q p

f(x)= c11x11 + c12x12+ …+ cqpxqp =   cijxij

i=1j=1

Таким образом, мы приходим к следующей математической за­даче: найти минимум функции f(x) при ограничениях :

 x11+ x12 + …+ x1p  T

 ……………………..

 xq1 + xq2 + …+ xqp  T

 a11x11 + a21x21+ …+ aq1xq1 = N1

 ………………………………

 a1px1p + a2px2p+ …+ aqpxqp = Np

 xij  0, i=1,… ,p; j=1,….,q


^ ОБЩАЯ, КАНОНИЧЕСКАЯ И ОСНОВНАЯ ЗАДАЧИ ЛП.

Общей называется следующая задача ЛП: найти минимум линей­ной формы

c1x1 + c2x2+ …+ cnxn (3)

при ограничениях-неравенствах

a11x1 + a12x2+ …+ a1nxn b1

……………………………….. (4)

aq1x1 + aq2x2+ …+ aqnxn£ bq


ограничениях-равенствах


aq+1,1x1 + aq+1,2x2+ …+ aq+1,nxn= bq+1



aq+2,1x1 + aq+2,2x2+ …+ aq+2,nxn= bq+2 (5)



aq+3,1x1 + aq+3,2x2+ …+ aq+3,nxn= bq+3

и условиях x1  0 , x2  0, ……., xr  0 , r  n, m  q (6)

Ограничения (4)...(6) выделяют в n -мерном пространстве множество точек, которое называется областью допустимых значений неизвестных. Функцию f(x) , т.е. линейную форму (3), будем назы­вать целевой. Решением задачи (3)...(6) называется точка области допустимых значений, в которой целевая функция достигает наименьшего значения. Соответствующие значения неизвестных x1*,…., xn* (координаты указанной точки) и значение целевой функции f*=f(x1*,…., xn*) называются оптимальным. Поскольку max f(x)= min (-f(x)), то к задаче (3)...(6) сводится и задача нахождения наибольшего значения функции f(x). Кроме того, функция (3) может иметь вид

n

f(x) =  ckxk + c0

k=1

В этом случае сначала исследуем функцию (x) =f(x) - c0и если min0, то min f(x) =0+c0. Ограничение-неравенство

n

aijxj  di

j=1

всегда можно привести к виду (4), умножив обе его части на –1, т.е. получим

n

-aijxj  - di

j=1


Канонической называют задачу (3)...(6), если в ней:

нет ограничений-неравенств (q=0);

свободные члены в ограниче­ниях-равенствах не отрицательны;

все неизвестные не отрица­тельны (r=n) Векторно-матричная запись ее имеет вид

f(х)=<с,х>, Ax=b, x 0, (7)


где <с,х>=  cixi , i=1,…,n- скалярное произведение в Rn векторов c=(c1,….,cn) и x=(x1,…,xn); А - матрица (m*n) коэффициентов aij при неизвестных в ограничениях-равенствах x    xi   , i=1,…,n.

Любая задача ЛП может быть преобразована в эквивалентную каноническую следующим образом:

Задача о нахождении максимума f заменяется задачей нахождения минимума (x) = - f(x)

Ограничения-равенства о отрицательными правыми частями умножаются на (-1).

3. Ограничения-неравенства заменяются ограничениями-равенствами и условиями неотрицательности вспомогательных переменны х:

неравенство ai1x1 + ai2x2+ …+ ainxn bi

заменяем равенством ai1x1 + ai2x2+ …+ ainxn+ xn+1=bi где xn+1= bi – (ai1x1 + +ai2x2+ …+ ainxn) 0


Так можно избавиться от всех ограничений-неравенств.

4. Переменные, на которые не наложено условие неотрицатель­ности, заменяются разностями новых неотрицательных переменных.

Основной называют задачу (3)…. (6), если в ней отсутствуют ограничения-равенства (q=т) и все переменные не отрицательны (r=n). В векторном виде основная задача выглядит так:

f(х)=<с,х>, Ax

Любая задача ЛП может быть преобразована в эквивалентную основную. Для этого, например, достаточно каждое из ограничений-равенств заменить парой неравенств: wi=bi  wibi , wi bi . Однако удобнее использовать другой метод преобразования, при котором уменьшается число независимых переменных. Рассмотрим

его.

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

x1=1,r+1xr+1 +…+ 1,nxn +1

…………………………… (8)

xr=r,r+1xr+1 +…+ r,nxn +r


где r- ранг матрицы коэффициентов системы (5). Подставляя выражения x1,…,xr в функцию f, получаем f= c0’+ c’r+1xr+1+…+ c’nxn

Подставим эти выражения в условия неотрицательности x1,…, xr. Таким образом, вместо системы линейных равенств (5) получим систему r линейных неравенств с (r-n) неизвестными xr+1,…, xn:

1,r+1xr+1 +…+ 1,nxn +1  

……………………………

r,r+1xr+1 +…+ r,nxn +r  


и линейную функцию от этих же неизвестных. Если в исходной за­даче были кроме равенств (которые мы уже заменили на неравен­ства) и неравенства (4), то они сохраняются, но в них тоже нужно заменить неизвестные x1,…,xr их выражениями (8) от неизвестных xr+1,…,xn.

Полученная задача эквивалентна исходной. В самом деле, если мы нашли решение x0r+1,…,x0n новой задачи, то, получив по формулам (8) неотрицательные значения x01,…,x0r, мы имеем систему чисел x01,…,x0r x0r+1,…,x0n, которая служит ре­шением задачи (3)…(6).

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

Пример 2. Найти максимум функции f(x1,x2)= x1+2x2 при огра­ничениях 2x1+x2   , -x1-x2, x2  , x1, x2.

Решение. Каждое из пяти ограничений-неравенств определяет полуплоскость на плоскости Ox1x2. Многоугольник G (рис.1), являющийся пересечением этих полуплоскостей, определяет множе­ство допустимых значений неизвестных (допустимое множе­ство). Градиентом функции f(x1,x2) является вектор c={1,2}, а линиями уровня будут прямые, задаваемые уравнениями x1+2x2= (при различных значениях ), Так как градиент функции направлен в сторону ее возрастания и перпендикулярен линии уровня, то для получения решения нужно двигать линию уровня x1+2x2= в на­правлении вектора с (это соответствует увеличению значения  функции f ) до тех пор, пока она имеет общие точки с множест­вом G. Очевидно, крайнее положение, при котором прямая еще содержит точку из G, будет соответствовать точке (1,2). Ко­ординаты этой точки и являются оптимальными значениями неизвестных.. Наибольшее значение функции f достигается в ней и равно f*=1+2*2=5.

Пример 3. Найти минимум функции f(x)= x1-3x2-x3+2x4-2x5+x6 при ограничениях x1, x2 , x3 , x4 , x5 , x6 , x1+3x2-x6=6, x2+x5-x6=1, x3-x5-x6=1, x4+x5=3.

Решение. Выражая переменные x1,x2,x3,x4 из ограничений-равенств получаем ограничения-неравенства:

x1=6-3x2+x6 

x2 =1-x5+x6 ,

x3 =1+x5+x6 ³0,

x4 =3-x5 ³0

и новую функции f(x1,x2)= 6-3x2+x6-3(1-x5+x6)-( 1+x5+x6)+2(3-x5) -2x5+x6 .

Кроме того, x5 , x6 . . Тем самым мы получили эквивалентную исходной основную задачу уже с двумя неизвестными. Допустимое множество G не ограничено (рис.2). Градиентом функции f яв­ляется вектор c={-5,2}Значит, вектор -с ={5,-2} направлен в сторону скорейшего убывания функции f. Перемещая прямую (линию уровня, задаваемую уравнением 8- 5x5-2x6 =) в направлении вектора {-5,2}, видим, что эта прямая при указанном движении постоянно будет иметь общие точки с множеством G . Следовательно, функция f не ограничена снизу на G , т.е. не имеет минимума.



Рис.1




Пример 4. При ограничениях примера 2 (см.рис.2) найти мак­симум функции

f(x)= x5-2x6 .

Решение. Вектор {1,2} показывает направление скорейшего возрастания функции f Значит, в точке (1,0) целевая функция f достигает наибольшего значения и оно равно f*(1,0)=1-2*0=1. Из рис.2 видно также, что если, например, искать наибольшее значение функции f(x)= x5-x6 на том же множестве, то оно дости­гается в каждой точке отрезка, соединяющего точки (1,0) и (2,5;1,5).

^ ПОНЯТИЕ О СИМПЛЕКС-МЕТОДЕ.

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

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

Допустимое множество ^ G является выпуклым "многогран­ником" (возможно, неограниченным), так как получается при пере­сеченна положительного октанта (x1,…, xn) с гиперплос­костями, задаваемыми ограничениями-равенствами. Число вершин допустимого множества конечно.

Поскольку целевая функция линейна, то ее частные произ­водные постоянны (и не все равны нулю, иначе f=^ 0 и задача тривиальна), а, значит, ее наименьшее значение (если она огра­ничена снизу на G ) достигается в вершине многогранника.

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

Основная идея симплекс-метода состоит в направленном пере­боре вершин допустимого множества. Этот метод, разработанные в 1949 г. Д.Данцигом. получил свое название из-за допустимого множества, которое рассматривалось в упрощенном варианте задачи. Множество представляло собой симплекс ( n-мерный многогранник, являющийся выпуклой оболочкой n+1 точек — вершин симплекса, которые не лежат в (n-1) -мерной плоскости). При п=0,1,2,3 симплексом будет соответственно точка, отрезок., треугольник, тетраэдр. Грани симплекса являются симплексами меньшей размер­ности, В дальнейвем метод был обобщен на случай более общих множеств, но название сохранилось. Иногда этот метод называют в литературе методом последовательного улучшения плана.

С геометрической точки зрения симплекс-метод можно описать следующим образом. Сначала находится одна из вершин допустимого многогранника (это можно сделать и аналитически, решая систему уравнений, описывающих ограничения задачи ЛП в канонической форме). Далее рассматриваются все ребра, сходящиеся в этой вер­шине. Если целевая функция не улучшается, т.е. не убывает в задаче минимизации, при передвижении вдоль любого из этих ребер, то данная вершина является "локальным", а следовательно, и гло­бальным экстремумом. Если же целевая функция улучшается вдоль одного из ребер, то мы переходим по этому ребру к вершине, рас­положенной на другом его конце, и затем повторяем тот же процесс, Так как на каждом шаге происходит улучшение функции, то через одну и ту же вершину нельзя пройти дважды, А поскольку число вершин конечно, то через конечное число шагов мы придем к реше­нию (или же за относительно небольшое число шагов выясним, что задача не имеет решения). Поясним на следующем примере,

Пример 5. Найти наибольшее значение функции f=2x+y при условиях x , y, 2x+2y  3, x  0, y 0.

Решение. Допустимое множество, соответствующее ограничениям задачи, представлено на рис.3. Для начала движения можно брать любую допустимую вершину. Возьмем точку (0,0),. "наиболее простую" для нахождения. В ней сходятся два ребра, причем f улучшается вдоль любого ребра, но значение f в (1,0) "лучше", чем в (0,1) , так как f(0,1)=1, f(0,1)=2. В точке (1,0) проверим ре­бро, идущее к точке (1,1\2). Получим, что f возрастает. Но далее находим, что f лишь убывает вдоль обоих ребер, сходя­щихся в точке (1,1\2). Значит, точка (1,1\2) является решением.

Перейдем теперь к описанию алгоритма симплекс-метода. Как уже отмечалось, для применения этого метода задача ЛП должна быть записана в каноническом виде: найти минимум функции f=c0 +c1x1+….+cnxn при ограничениях xi  0, где i=1,..,n




a11x1 + a12x2+ …+ a1nxn b1

……………………………….. (9)

am1x1 + am2x2+ …+ amnxn£ bm


(рис. 3)


Прежде всего, необходимо устано­вить, совместна ли система уравне­ний (9). Если несовместна, то наша задача ЛП не имеет решения. Теорема Кронекера - Капелли дает ответ на этот вопрос: если ранг мат­рицы системы равен рангу расширенной матрицы, то система сов­местна. Затем надо исключить из системы (9) все те уравнения, которые являются линейными комбинациями остальных. Будем далее считать, что ранг r матрицы {aij} системы (9) равен m (mn). Предположим, что система (9) разрешима относительно x1,….,xr:

x1= 1-(1,r+1xr+1 +…+ 1,nxn)

…………………………… (10)

xr= r –(r,r+1xr+1 +…+ r,nxn),

где x1,….,xr – базисные переменные; xr+1,….,xn – свободные переменные. Следует отметить, что не всегда именно r переменных будут базисными, однако можно произвести перенумерацию переменных.

Функция f(x) также может быть выражена через свободные переменные при помощи соотношений (10):

f(x) = 0-( r+1xr+1+…+ nxn) (11)

Будем называть базисным такое решение системы (9), которое получается при нулевых значениях свободных переменных. Найдем из (10) значения базисных неизвестных, полагая, что xr+1=….=xn =0. Получим x1 =1,…,xr=r .

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

1,…, r,0 .....0.

Базисное решение, состоящее из неотрицательных чисел, будем называть допустимым базисным решением.. Значит, базисное решение 1,…, r, …… .....0 будет допустимым тогда и только тогда, когда свободные члены i в системе (10) не отрицательны.

В симплекс-методе всегда предполагается, что в системе (10) все свободные члены не отрицательны, т.е. базисное решение является допустимым, В противном случае необходимо изменить разбиение множества переменных x1,….,xn на два подмножества базисных и свободных переменных так. чтобы в системе (10) все свободные члены били неотрицательными (i , i=1,….,r). Если такое разбиение невозможно, то это означает, что задача ЛИ не имеет решения.

Итак, рассмотрим случай применения симплекс-метода, когда система ограничений приведена к базису, т.е. предположим, что i , i=1,….,r.

Составим таблицу по полученным соотношениям (10),(11). Это будет симплекс-таблица, которая отождествляется с нашей задачей (10),(11).



Таблица 2.






1

Xr+1

……

Xj

….

xn

X1

1

1,r+1

……

1,j



1,n

…..

…..…



……








xi

i

i,r+1

………

I,j



I,n

….



………

………

……

……………

……

xr

r

r, r+1

……

r,j



r,n

f

0

r+1



j



n


Главное удобство такой схемы в том, что она позволяет из­бежать повторения переменных x1,….,xn и тем самым упрощает вались. Каждая строка табл, 2 соответствует уравнению, выражаю­щему базисные неизвестные через свободные. Последняя строка соответствует линейной форме f. Каждый столбец (кроме пер­вого) отвечает некоторой свободной неизвестной, первый стол­бец - свободным членам. Теперь рассмотрим собственно симплекс-алгоритм.

Проверка оптимальности:

если  j  0 для всех j=r+1, ….,n, то допустимое базисное решение 1,…, r,0....0,..., 0 является оптимальным и задача решена, fmin=0 (для любых xr+1,….,xn, f = 0-( r+1xr+1+…+ nxn)  0;

если в симплекс-таблице найдется хотя бы одно  j , причем столбец, содержащий это j ,не имеет положительных чисел, т.е.ij для i=1,….,n, то функция f' не ог­раничена снизу на множестве допустимых значений. Задача не имеет решения.

Пусть рассмотренные в п.1 ситуации не имеют места. Тогда переходим к следующему шагу

Выбор ведущего столбца:

выберем и зафиксируем один из положительных элементов j . Содержащий этот элемент j столбец симплекс-таблицы будет называться ведущим столбцом.

Выбор ведущей строки;

так как не выполнено условие "б" из п.1, то в выбранном ведущем столбце имеются положительные элементы ij . Выделим их и составим для них отношения s/sj ; найдем среди этих дробей наименьшую по величине. Пусть


i/ij= min (bs/asj)

s: asj

Тогда i-я строка называется ведущей. Элемент ij , располо­женный на пересечении ведущей строки и ведущего столбца, назы­вается ведущим. Удобно ведущий элемент в симплекс-таблице под­черкнуть.

Переход от старой симплекс-таблицы к новой:

новая таблица совершенно идентична старой. Ее элементы бу­дем обозначать теми же буквами, но со штрихом ’i , a’ij, ’j . При этом:

а) переменные xi и xj меняют местами, а остальные остав­ляют на прежних местах. Это означает, что переменную xi пере­водят из числа базисных в число свободных, а переменную xj, наоборот, из свободных в базисные. Геометрически это означает переход к соседней вершине;

б) в клетку, расположенную на пересечении ведущей строки и ведущего столбца, записывают число 1/ aij (aij - ведущий элемент)

в) в свободные клетки ведущей строки записывают числа, ко­торые уже есть в соответствующих клетках симплекс-таблицы , разделив их на ведущий элемент:

a'iq = a’iq / aij qj.

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

a'qj = - ( a’qq / aij ) qi.


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

¦ ¦

p-ая строка       - - -  pq - - - - - - - - -  pj- - - - - -

¦ ¦

ведущая строка  - - - - - - iq - - - - - - - - - ij - - - - - -

q-ый столбец ведущий столбец

Тогда элемент ’ pq вычисляется по формуле ’ pq =( a pqij - iqpj) .

При заполнении последней строки используется формула

’l lij il j aij .

5. После заполнения новой таблицы по правилам, изложенным в п. 4., переходим к п.1 и проводим проверку оптимальности.


Пример 6. Найти наибольшее значение функции f = x2 + x3 при ограничениях

x1- x2 + x3 = 1, x2 - 2x3+x4 = 2.

Решение. Запишем расширенную матрицу системы ограничений

 1 –1 1 0  1 

 0 1 -2 1  2 .

Легко проверить, что ранг матрицы равен рангу расширенной мат­рицы. Значит, множество допустимых планов не пусто. Рассмотрим новую целевую функцию

f1(x) = - f(x) = -x2 - x3  min

Примем за базисные переменные x1 и x4.

Составил симплекс-таблицу нашей задачи (табл.3). Находим ведущий столбец, ведущую строку и ведущий элемент, Согласно алгоритму, переходим к новой симплекс-таблице (табл,4).







x2

x3

x1

1


-1


1


x4.

2


1


-2


f1


0


1


1


Таблица 3.


Таблица 4







x4.


x3

x1

3


1


-1


x2

2


1


-2


f1


-2


1


3


Поскольку 3 = 3  0 , а 13= -1 0, 23 = -2  0, то в соответствии с п.1b) симплекс –алгоритма, имеем f1min = -  ; fmax = - f1min = + .

Пример 7. Найти наибольшее значение функции f = x4 + x5 при ограничениях

x1+ x4 -2 x5 = 1 , x2-2 x4+ x5 =2, x3 + 3x4 +x5 = 3.

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


 1 0 0 1 -2 1

 0 1 0 -2 1 2 

 0 0 1 3 1  3

Рассмотрим главный минор третьего порядка:

 1 0 0 

 0 1 0  = 1  0

 0 0 1 

Значит, ранг равен трем.

Очевидно, x1, x2, x3 являются базисными переменными. Вы­разим их через свободные переменные x4 и x5:

x1 = 1 – (x4 - 2x5)

x2 = 2 – ( -2x4 +x5)

x3 = 3 – ( 3x4 +x5)

Задача нахождения максимума f = -x4 + x5 ,очевидно, эквивалент­на задаче

f1(x) = -f(x) = - ( - x4 + x5) min.

В данном случае линейная форма f1 уже выражена через свобод­ные переменные. Итак, f1 = -( - x4 + x5), и все данные задачи можно представить в виде симплекс-таблицы (табл.5.)

Согласно алгоритму, переходим к. последующим таблицам (табл.6.7).


Таблица 5. Таблица 6.







x4


x5

x1

1


1


-2


x2

2


-2


1


x3

3


3


1


f1

0


-1


1











x4

x2

x1

5


-3


2


x5

2


-2


1


x3

1


5


-1


f1

-2


1


-1




Таблица 6.


Таблица 7.







x3

x4

x1

28



5

3





7



5

x5

12



5

2



5

3



5

x4

1



5

1



5

1



5

f1

-11

¾

5

-1

¾

5

-4

¾

5

Так как все ’i   в табл.7, то оптимальный план найден:


fmax = f1min = 11/5 при x1 =28/5, x2= x3 = 0, x4= 1/5, x5 = 12/5.


Пример 8. Найти наибольшее значение f =2 x1- 3 x2+ x4  max при ограничениях:


4 x1+ 2 x2 -5 x3+ 3 x4 = 2,

3 x1 + x2 - 4 x3 + 7 x4 = 5,

-6 x1 - 4 x2+ 7 x3+ 5 x4 =3.


Решение. Вычислим ранг расширенной матрицы элементарными преобразованиями строк матрицы.

 4 2 -5 3  2  -2 0 3 -11  -8   -2 0 3 -11  -8 

 3 1 -4 7  5  ( -2) ( 4)   3 1 –4 7  5  ( 3)   3 1 –4 7  5 

 -6 -4 7 5  3   6 0 –9 33  23  0 0 0 0 -1 

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

По теореме Кронекера- Капелли, система ограничений не имеет решения. Таким образом, задача не имеет решения.


^ ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ.

Предприятие производит два вида продукции (А и В). Объем сбыта А составляет не менее 60% общего объема реализации про­дукции обоих видов. Для изготовления (А и В) используется одно и то же сырье, суточный запас которого ограничен величиной 100 кг. Расход сырья на единицу продукции А составляет 2 кг, а на единицу продукции В - 4 кг. Цены продукции A и В - соответ­ственно 20 и 40 руб. Определить оптимальное распределение сырья для изготовления продукции А и В.

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

Таблица 8.

Изделие


Время обработки одного изделия

на станке, мин


Удельная

прибыль, руб.


П 1

10'


6


8


2


П 2

5


20


15


3



Дана совокупность ограничений:

x1 + 7 x2 + 3 x3 + 7 x4  4 ,

3x1 - x2 + x3 + x4 £ 8,

2x1 + 3x2- x3 + x4 £ 10.

Решите задачу ЛП симплекс-методом при следующих целевых функ­циях:

f = 2 x1 + x2 -3 x3 +5 x4  max,

f = -2 x1+ 6 x2 + 3x3 - 2x4  max,

f = 3x1 - x2 + 3x3 + 4x4 ® max,

f = 5x1 - 4x2 + 6x3 + 8x4 ® min,

f = 3x1 - 6x2 - 2x3 + 4x4 ® min.

f = 20x1 + 10 x2 + x3 ® max при ограничениях:

3x1 - 3x2 + 5x3 £ 50,

x1 - x3 £ 10,

x1 - x2 + 4x3 £20,

x1, x2, x3  0.

f = 12x1 +5x2 + 3x4 ® min при ограничениях:

4x1 + 3x2 + x3 = 180,

4x2 + 9x3 + 12x4 = 900.

f = -x1 - 2x2 - 3x3 ® max при ограничениях:

4x1 + 3x2 + x3  -1,

2x1 - x2 - x3 £ -1.

f = 2x1 + 4x2 + 4x3 –3 x4 ® max при ограничениях:

x1 + x2 + x3 = 4,

x1 + 2x2 + x4 =8,

x1, x2, x3, x4 ³ 0.

Найти оптимальное решение, используя в начальном базисном ре­шении переменные x3 и x4.


^ НЕКОТОРЫЕ ЗАМЕЧАНИЯ О СИМПЛЕКС-МЕТОДЕ.

Замечание 1. В описанном алгоритме симплекс-метода мы по­лагали, что допустимое базисное решение уже найдено. Если это не так, то надо уметь находить его.

Покажем, как можно систему ограничений вида

n

 akj xj = bk (k=1, …,m) (12)

j = 1

привести к системе вида

n

xk = k -  akj xj (bk ³ 0, k =1, …,r)

j =r + 1

т.е. выяснить, когда переменные x1,…, x2 образуют допусти­мый базис. Система (12) совместна тогда и только тогда, когда ранг матрицы А :


 a11 ….. a1n

A = …………… 

 am1 …… amn


равен рангу расширенной матрицы B:

a11…………a1n b1

B= ………………… … 

 am1 ……… amn bm


Пусть r= ранг А равен рангу В. Тогда можно выбрать r уравне­ний исходной системы, таких, что всякое решение системы, состоя­щей из этих r уравнений, есть решение исходной системы с мат­рицей А. Без ограничения общности можно считать, что r = m  n. Можно также добиться путем перенумерации переменных,


 a11 ….. a1n

 = …………… 

am1 …… amn

Утверждение. Для того чтобы неизвестные x1 ,.,..xm из си­стемы (12) образовали допустимое базисное решение, необходимо и достаточно выполнение следующих условий:

i /   0 для каждого I = 1, … , m,

где i - определитель, получающийся из определителя  заме­ной i -го столбца столбцом свободных членов системы (12).

Другой способ приведения к базису заключается в том, что вводятся искусственные переменные xn+1, xn+2,…., xn+m и предварительно решается следующая задача: найти наименьшее зна­чение функции  (x) = xn+1+ xn+2 + xn+m при ограниче­ниях:

a11x1 + a12x2 + …..+ a1nxn + xn+1 = b1,

a21x2 + a22x2 + …..+ a2nxn + xn+2 = b2,

………………………………………,

amnx1 + amnx2 + …..+ amnxn + xn+m = bm.


Задача эта приведена к базису и, следовательно, может быть решена с помощью описанного нами симплекс-алгоритма. Решение этой вспомогательной задачи составляет первый этап общей проце­дуру симплекс-метода. Очевидно, наименьшее значение линейной формы  (x) = xn+1+ xn+2 + xn+m равно нулю и достигается при нулевых значениях искусственных переменных. Поэтому, если в си­стеме ограничений (которая соответствует заключительной симплекс- таблице вспомогательной задачи) отбросить искусственные переменные, то получится система, эквивалентная системе ограничений-равенств исходной задачи и приведенная к базису. На втором этапе симплекс-алгоритм применяется к нашей задаче, уже приведенной к базису.

Замечание 2. Следует отметить также особые случая, которые могут встретиться при использовании симплекс-алгоритма:

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

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


ЛИТЕРАТУРА.

1. Ашманов С.А. Линейное программирование. - М.: Наука, 1981.

2. Данциг Г. Линейное программирование. - М.: Прогресс, 1966.

3. Карманов В.Г. Математическое программирование. - М.: На­ука, 1975.

4. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. - М.: Наука, 1969.


СОДЕРЖАНИЕ.




Похожие:

Методические указания по курсу \"Спецглавы высшей математики\" Под редакцией А. К. Гущина iconМетодические указания и контрольные задания по курсу «Бухгалтерская финансовая отчетность» для студентов специальности 080109 «Бухгалтерский учет, анализ и аудит»
Методические указания предназначены для студентов дневной и вечерней форм обучения
Методические указания по курсу \"Спецглавы высшей математики\" Под редакцией А. К. Гущина iconМетодические указания для самостоятельной работы студентов по курсу
Методические указания для самостоятельной работы по курсу «Бухгалтерский финансовый учет» тема «Учет операций по налогообложению...
Методические указания по курсу \"Спецглавы высшей математики\" Под редакцией А. К. Гущина iconМетодические указания по бухгалтерскому учету мпз методические указания по бухгалтерскому учету материально-производственных запасов (утв. Приказом Минфина России от 28 декабря 2001 г. N 119н)
Эти Методические указания для налоговых целей не применяются, торговые организации вправе использовать их для целей бухгалтерского...
Методические указания по курсу \"Спецглавы высшей математики\" Под редакцией А. К. Гущина iconМетодические указания к лабораторным работам по курсу «Электроника» пенза 2006
В лабораторных работах исследуются основные характеристики и параметры полупроводниковых диодов
Методические указания по курсу \"Спецглавы высшей математики\" Под редакцией А. К. Гущина iconМинимум задач по курсу высшей математики
Найдите общее решение и фундаментальную систему решений следующей системы линейных уравнений
Методические указания по курсу \"Спецглавы высшей математики\" Под редакцией А. К. Гущина iconМетодические указания по подготовке курсовых работ Москва 2002 утверждено
Методические указания подготовлены для студентов, обучающихся по специальности 350 800 "Документоведение и документационное обеспечение...
Методические указания по курсу \"Спецглавы высшей математики\" Под редакцией А. К. Гущина iconБиблиографический список
Элементы интерфейса, стандартные и прикладные программы ос windows: Методические указания к практическим занятиям по курсу «Информатика»/...
Методические указания по курсу \"Спецглавы высшей математики\" Под редакцией А. К. Гущина iconС. В. Молчанов В. К. Волкова Н. А. Молчанова Методические указания
Методические указания предназначены для студентов всех форм обучения, изучающих курсы «Химия» («Общая химия»), «Органическая химия»...
Методические указания по курсу \"Спецглавы высшей математики\" Под редакцией А. К. Гущина iconМетодические указания по подготовке, выполнению, оформлению и защите дипломной работы, по ее рецензи­рованию
Методические указания по выполнению дипломных работ для студен­тов специальности "Мировая экономика" / Сост. Л. В. Левченко. Самара:...
Методические указания по курсу \"Спецглавы высшей математики\" Под редакцией А. К. Гущина iconМетодические указания для выполнения контрольной работы по курсу «Финансовая бухгалтерская отчетность» для студентов специальности 080109 «Бухгалтерский учет, анализ и аудит». Спб.: Изд-во Спбгуэф, 2010. 37 с
Рабочая программа и методические указания для выполнения контрольной работы по курсу «Финансовая бухгалтерская отчетность» для студентов...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов