close

Вход

Забыли?

вход по аккаунту

?

499.Линейная алгебра Бестужева Л П

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство образования и науки Российской Федерации
Ярославский государственный университет им. П. Г. Демидова
Кафедра общей математики
Л. П. Бестужева, Н. Л. Майорова
Линейная алгебра Практикум
Рекомендовано
Научно-методическим советом университета для студентов,
обучающихся по направлениям
Экономика и Менеджмент организации
Ярославль 2011
1
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 512
ББК В143я73+В183.41я73
Б 53
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2010/2011 учебного года
Рецензент
кафедра общей математики Ярославского государственного
университета им. П. Г. Демидова
Бестужева, Л. П. Линейная алгебра: практикум /
Б 53 Л. П. Бестужева, Н. Л. Майорова; Яросл. гос. ун-т
им. П. Г. Демидова. – Ярославль : ЯрГУ, 2011. – 56 с.
Методические указания содержат материалы, необходимые для изучения дисциплины "Линейная алгебра":
теоретические сведения по темам "Системы линейных
уравнений, их решение методом Гаусса и Жордана-Гаусса", "Задача линейного программирования, ее решение
графическим методом и симплекс-методом", контрольные работы, темы практических занятий с перечнем диагностических целей, темы рефератов, список литературы.
Предназначены для студентов, обучающихся по направлениям 080100 Экономика и 080200 Менеджмент
организации (дисциплина «Линейная алгебра», математический цикл (блок ЕН)), очной формы обучения.
УДК 512
ББК В143я73+В183.41я73
 Ярославский государственный
университет им. П. Г. Демидова, 2011
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Линейные уравнения и системы линейных уравнений Линейное уравнение с n переменными (неизвестными)
х1 , х2 ,, хn имеет вид
а1 х1  а2 х2    аn хn  b ,
где а1 , а2 ,, аn – коэффициенты при переменных (неизвестных)
х1 , х2 ,, хn , b – свободный коэффициент. Коротко это уравнение
записывается так:
n
ajxj  b .
j 1
Решение линейного уравнения – это упорядоченный набор n
чисел, при подстановке которых в уравнение получается верное
числовое равенство.
Пример.
2 x1  3 x2  4 x3  6 x4  x5  21, X   1, 2, 0, 5, 1 – решение уравнения.
Линейное уравнение вида 0  x1  0  x2    0  xn  b, b  0
называется противоречивым. Это уравнение не имеет решения.
Линейное уравнение вида 0  x1  0  x2    0  xn  0 называется
тривиальным. Решение этого уравнения – любой набор n чисел.
Система m линейных
уравнений с n неизвестными
(переменными) х1 , х2 ,, хn имеет вид
a11 x1  a12 x2    a1n xn  b1 ,
a x  a x    a x  b ,
 21 1 22 2
2n n
2

          
am1 x1  am 2 x2    amn xn  bm .
Коротко эта система уравнений записывается так:
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
n
 aij x j  bi ,
j 1
i  1, m, j  1, n .
Решение системы линейных уравнений – это упорядоченный
набор n чисел, который является решением каждого уравнения
системы.
Система линейных уравнений называется: совместной, если
она имеет хотя бы одно решение; несовместной, если она не
имеет решений.
Если хотя бы одно уравнение системы линейных уравнений
противоречивое, то система несовместна.
Система линейных уравнений называется: однородной, если
все свободные коэффициенты равны 0; неоднородной, если хотя
бы один из свободных коэффициентов не равен 0.
Однородная система имеет вид
n
 aij x j  0,
i  1, m, j  1, n.
j 1
Однородная система всегда совместна. Она всегда имеет хотя
бы одно решение. Решение X  (0,0,,0) называется тривиальным решением.
Две системы называются равносильными, если они имеют
одни и те же решения. Процесс решения системы линейных уравнений заключается в переходе от одной системы к другой, которая ей равносильна.
Решение системы линейных уравнений Переменная x j называется разрешенной, если она входит в
одно из уравнений системы с коэффициентом 1, а в остальные
уравнения системы входит с коэффициентами, равными 0.
Система линейных уравнений называется разрешенной (приведенной к единичному базису), если каждое уравнение системы
линейных уравнений содержит разрешенную (базисную) пере4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
менную. Разрешенная система линейных уравнений всегда
совместна.
Если все переменные в системе линейных уравнений разрешенные, то система имеет единственное решение. Если в разрешенной системе линейных уравнений не все переменные разрешенные, то остальные переменные называются свободными и
система имеет бесконечное множество решений. Для записи общего решения системы линейных уравнений свободные переменные переносят к свободным коэффициентам, т. е. разрешенные переменные выражают через свободные переменные и
свободные коэффициенты.
Если свободным переменным дать какие-либо числовые
значения и получить соответствующие значения разрешенных
переменных, то получим частное решение системы (одно из
бесконечного множества решений).
Пример 1. Рассмотрим систему трех уравнений, в которой
четыре переменные, с разрешенной переменной x2 .
 4 x3  x4  1,
5 x1

 x1  x2  5 x3  7 x4  2,

 3 x3  x4  1.
6 x1
Пример 2. Рассмотрим систему трех уравнений, в которой
три переменные, и все переменные разрешенные
 1,
 x1

 x2  2,

x3  5.

Такая система имеет единственное решение Х   1, 2, 5  .
Пример 3. Рассмотрим систему двух уравнений, в которой
четыре переменные. Каждое уравнение содержит разрешенную
переменную. Переменные x1 , x3 – разрешенные (базисные).
Переменные x2 , x4 – свободные.
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 6х4  7,
 х1  5х2

3х2  х3  х4  2.

Перенесем свободные переменные вправо к свободным
коэффициентам:
 х1  7  5х2  6х4 ,

 х3  2  3х2  x4 .
Тогда общее решение системы запишется так:
X общ   7  5х2  6х4 , x2 , 2  3х2  x4 , x4  , x2 , x4  R.
Для того, чтобы получить некоторое частное решение системы, дадим свободным переменным числовые значения, наприх2  1, х4  2 . Тогда получим частное решение
мер,
Х частное 1   24, 1,  3,  2  .
Если свободным переменным дать другие числовые
значения, например, х2   1, х4  5 , то получим другое частное
решение Х частное 2   28,  1, 10, 5  .
Если свободным переменным дать нулевые значения
х2 , х4  0 , то получим еще одно частное решение, которое
называется базисным: Х базисное   7, 0, 2, 0  .
Метод Гаусса. Метод Жордана – Гаусса Метод Гаусса – метод исключения переменных. Система
приводится к треугольному виду. Метод Жордана – Гаусса – метод полного исключения переменных. Система приводится к разрешенному виду (если она совместна) с помощью элементарных
преобразований системы: 1) умножение какого-либо уравнения
на число, не равное 0; 2) умножение уравнения системы на любое
число и сложение с другим уравнением; 3) вычеркивание
тривиального уравнения; 4) вычеркивание одного из двух
одинаковых уравнений; 5) вычеркивание одного из двух
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
уравнений с пропорциональными коэффициентами; 6) перемена
местами двух уравнений системы.
С помощью этих преобразований переходят от одной системы линейных уравнений к другой системе, которая ей равносильна.
Решение системы линейных уравнений методом Гаусса или
методом Жордана – Гаусса удобно оформлять в виде таблицы.
Коэффициенты системы записываются в таблицу: столбцы коэффициентов при переменных х1 , х2 ,, хn обозначим A1 , A2 ,, An
соответственно, а столбец свободных коэффициентов обозначим
B . Вышеперечисленные элементарные преобразования уравнений системы можно сформулировать для строк таблицы.
A1
a11
a21
…
am1
A2
a12
a22
…
am2
…
…
…
…
…
An
a1n
a2n
…
amn
B
b1
b2
…
bm
Сформулируем алгоритм пересчета коэффициентов системы
m линейных уравнений с n переменными при ее решении методом Гаусса или методом Жордана – Гаусса. Для этого систему запишем более подробно, выделив строки i , r и переменные j и s :
a11 х1   a1 j x j   a1s xs   a1n xn  b1 ,

......................................................................
ai1 х1    aij x j    ais xs    ain xn  bi ,

......................................................................
a х    a x   a x   a x  b ,
rj j
rs s
rn n
r
 r1 1
.......................................................................

am1 х1    amj x j   ams xs   amn xn  bm .
Коэффициенты системы запишем в таблицу. Пересчитаем
таблицу так, чтобы сделать переменную xs разрешенной. Пересчет проходит в два этапа: 1) выберем в таблице разрешающий
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
элемент ars , ars  0 , который стоит в разрешающей строке r .
Разделим разрешающую строку на разрешающий элемент:
arj 
arj
ars
, j  1, n; br 
br
.
ars
Цель – сделать коэффициент при переменной xs в уравнении
r равным 1.
2. Остальные элементы таблицы пересчитаем по формулам
aij  aij 
bi  bi 
 ais arj
ars

aij  ars  ais  arj
ars
 ais br bi  ars  ais  br

,
ars
ars
,
i  1, m .
Цель – сделать коэффициент при переменной xs в уравнении
i , i  1, m , i  r равным 0, т. е. исключить переменную xs из
уравнения i .
Пересчет наглядно представлен на схеме:
ars … br
aij … ais
arj … ars
ais … bi
Далее рассмотрим три примера решения систем линейных
уравнений. В первом примере система будет решена двумя
методами – методом Гаусса и методом Жордана – Гаусса для
того, чтобы понять, в чем их сходство и различие. Во втором и
третьем примерах системы будут решены только методом
Жордана – Гаусса.
Пример 1. Решить систему трех уравнений, в которой три
переменные:
3х1  2х2  х3  5,

 х1  х2  х3  0,
4х  х  5х  3.
2
3
 1
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Запишем коэффициенты системы в
таблицу и выполним преобразования системы: поменяем местами первую и вторую
строки (первое и второе уравнения системы); исключим переменную x1 из второго и
третьего уравнения; исключим переменную
x2 из третьего уравнения.
Систему привели к треугольному виду:
 х1  х2  х3  0,

х2  4х3  5,


х3  2.

Теперь необходимо сделать обратный
ход:
 х1  3  2,

 х2  5+4  2,
 х  2.
 3
Решим ту же систему методом
Жордана-Гаусса. Запишем коэффициенты
системы в таблицу и выполним преобразования системы: исключим переменную x2 из первого и третьего уравнения;
исключим переменную x1 из второго и
третьего уравнения; исключим переменную x3 из первого и второго уравнения.
Систему привели к виду:
 1,
 x1

 x2  3,

x3  2.

9
A1
3
1
4
1
1
5
1
0
0
1
0
0
1
0
0
A1
A2
A3
B
3
1
4
1
3
4
1
0
0
1
0
0
1
0
0
1
0
0
2
1
-1
1
2
-1
1
-1
-5
1
1
-5
1
1
0
1
1
0
1
-1
5
-1
1
5
-1
4
9
-1
-4
9
-1
-4
-11
-1
-4
1
5
0
3
0
5
3
0
5
3
0
-5
3
0
-5
-22
0
-5
2
A2
2
1
-1
0
1
0
0
1
0
0
1
0
0
1
0
A3
1
-1
5
3
-1
4
3
-4
-11
3
-4
1
0
0
1
B
5
0
3
5
0
3
5
-5
-22
5
-5
2
-1
3
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Ответ: система линейных уравнений имеет единственное
решение Х   1,3,2  .
Пример 2. Решить систему четырех уравнений, в которой
четыре переменные:
 х1  х2  х3  х4  2
 х  2 х  2 х  х  5
 1
2
3
4

2 х1  х2  3 х3  2 х4  1
 х1  2 х2  3 х3  6 х4  10.
Запишем коэффициенты системы
в таблицу и выполним преобразования
системы: исключим переменную x1 из
второго, третьего и четвертого
уравнения; исключим переменную
x2 из первого, второго и четвертого
уравнения; вторая и четвертая строки
пропорциональны,
вычеркнем
четвертую строку, вторую разделим
на 12; исключим переменную x3 из
первого и третьего уравнения.
Систему привели к виду:
 x4  3,
 x1

x3  x4  1,

 x
 x4  2,

2
A1
1
1
2
1
1
0
0
0
1
0
0
0
1
0
0
1
0
0
A2
-1
2
-1
2
-1
3
1
3
0
0
1
0
0
0
1
0
0
1
A3
1
-2
-3
3
1
-3
-5
2
-4
12
-5
17
-4
1
-5
0
1
0
A4
-1
-1
2
-6
-1
0
4
-5
3
-12
4
-17
3
-1
4
-1
-1
-1
B
-2
-5
-1
-10
-2
-3
3
-8
1
-12
3
-17
1
-1
3
-3
-1
-2
где x1 , x2 , x3 – разрешенные (базисные)
переменные, x4 – свободная переменная.
Перенесем свободную переменную вправо к свободным
коэффициентам:
 x1  x4  3,

 x3  x4  1,

 x2  x4  2.
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Ответ: система линейных уравнений имеет бесконечное
множество решений: Х общее   х4  3, х4  2, х4  1, х4  , х4  R .
Пример 3. Решить систему четырех уравнений, в которой
четыре переменные:
6х1  5х2  7х3  8х4

3х1  11х2  2х3  4х4

3х1  2х2  3х3  4х4
 х1  х2  х3
Запишем коэффициенты системы в
таблицу и выполним преобразования
системы: исключим переменную x3 из
первого, второго и третьего уравнения;
исключим переменную x1 из первого,
третьего и четвертого уравнений;
исключим переменную x2 из первого,
второго и четвертого уравнения.
Систему привели к виду, в которой
первое уравнение имеет вид:
0  x1  0  x2  0  x3  0  x4  6 .
Это противоречивое уравнение.
Ответ: система линейных уравнений несовместна (не имеет решений).
 3,
 6,
 1,
 0.
A1
6
3
3
1
-1
1
0
1
0
1
0
0
0
1
0
0
A2
-5
11
2
1
-12
9
-1
1
-3
9
-1
-8
0
0
1
0
A3
7
2
3
1
0
0
0
1
0
0
0
1
0
0
0
1
A4
B
8
3
4
6
4
1
0
0
8
3
4
6
4
1
0
0
12
9
4
6
4
1
-4 -6
0
6
40
3
-4 -1
-38 -14
Переход от одного базисного решения системы к другому Если система линейных уравнений имеет бесконечное множество решений, то можно записать общее решение системы.
Если свободным переменным давать числовые значения и вычислять соответствующие числовые значения базисных (разрешенных) переменных, то будем получать частные решения системы.
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Частное решение называется базисным, если свободным
переменным дать значение, равное 0.
Пример 4. Найти все базисные решения системы
 х1  х2  х3  х4  2
 х  2 х  2 х  х  5
 1
2
3
4

2 х1  х2  3 х3  2 х4  1
 х1  2 х2  3 х3  6 х4  10.
Эта система рассматривалась в примере 2, и ее общее
решение имеет вид:
Х общее 
 х4  3, х4  2, х4  1, х4  , x4  R, Х базисное   3,
 2,  1, 0  .
Вид записи общего решения системы зависит от того, какие
переменные выбираются в качестве базисных (разрешенных) переменных. Если таблицу пересчитать так, чтобы свободная переменная x4 стала базисной (разрешенной) и, следовательно, одна
из базисных (разрешенных) переменных стала свободной, то получим другую запись общего решения системы и другое базисное
решение системы. Результаты пересчета представлены в таблице:
базис B
A1
-3
A2
-2
A3
-1
A4
3
A2
1
A3
2
A4
2
A1
-1
A3
1
A4
1
A1
-2
A2
-1
A1
1
0
0
-1
-1
-1
0
1
0
0
1
0
A2
0
1
0
0
1
0
-1
-1
-1
0
0
1
A3
0
0
1
0
0
1
0
0
1
-1
-1
-1
12
A4
-1
-1
-1
1
0
0
1
0
0
1
0
0
базисное
(-3, -2, -1, 0)
(0, 1, 2, 3)
(-1, 0, 1, 2)
(-2, -1, 0, 1)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Свободной
переменной
последовательно
становятся
x4 , x1 , x2 , x3 . Все базисные решения системы записаны сразу в
таблице без записи общего решения системы.
Переход от одного опорного решения к другому Неотрицательное базисное решение называется опорным.
Среди базисных решений примера 4 опорным является только
одно решение X  (0,1, 2, 3) . Пример 4 демонстрирует один из способов поиска опорных решений системы: находят все базисные
решения системы и среди них отбирают опорные решения
системы. Ясно, что этот способ не является рациональным, т. к.
предполагает перебор всех базисных решений системы.
Пример 5. Найти все опорные решения системы
 x4  3,
 x1

 1,
 x1  x2
 x
 x3
 2.
 1
Запишем коэффициенты системы в таблицу:
Переменные x2 , x3 , x4 – базисные
A1
A2
A3
A4
B
(разрешенные), переменная x1 – свобод-1
0
0
1
3
-1
1
0
0
1
ная. Опорное решение системы имеет
-1
0
1
0
2
вид X  (0,1, 2, 3) . Для того чтобы найти
другое опорное решение системы, надо переменную x1 сделать
базисной (разрешенной). Для этого надо пересчитать таблицу.
Первый пункт в алгоритме пересчета состоит в выборе разрешающего элемента и делении разрешающей строки на разрешающий элемент. Когда речь идет о переходе от одного базисного
решения к другому, то естественно требование: разрешающий
элемент не должен быть равен 0. Если речь идет о переходе от
одного опорного решения к другому, то первое требование:
разрешающий элемент должен быть положительным. Так как в
столбце A1 нет положительных элементов, то указанное опорное
решение будет единственным.
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример 6. Найти все опорные решения системы
 x4
 2,
 x1  2 x2

 2,
2 x1  x2  x3

 x 5  5.
 x1  x2
Запишем коэффициенты системы в таблицу:
Базис В
A4
A3
A5
A1
A3
A5
A1
A3
A2
2
2
5
2
6
3
4
9
1
A1
A2
A3
A4
A5
1
-2
1
1
0
0
1
0
0
-2
1
1
-2
-3
3
0
0
1
0
1
0
0
1
0
0
1
0
1
0
0
1
2
-1
1/3
1
-1/3
0
0
1
0
0
1
2/3
1
1/3
Опорные
решения
(0, 0, 2, 2, 5)
(2, 0, 6, 0, 3)
(4, 1, 9, 0, 0)
Для перехода от первого опорного решения ко второму надо
одну из свободных переменных, например, x1 перевести в базисные (разрешенные) переменные. Для этого надо специальным
образом выбрать разрешающий элемент: 1) разрешающий
элемент, выбираемый в столбце A1 , должен быть положительным.
Поскольку в этом столбце два положительных элемента, то
2) разрешающий элемент тот, на котором достигается минимум
отношения элементов столбца B к положительным элементам
столбца A1 .
Для перехода от второго опорного решения к третьему надо
свободную переменную x2 перевести в базисные (разрешенные)
переменные. Для этого надо специальным образом выбрать разрешающий элемент: 1) разрешающий элемент, выбираемый в
столбце A2 , должен быть положительным. Поскольку в этом
столбце один положительный элемент, то он и будет разрешающим.
Замечание. Требование 1 к выбору разрешающего элемента
при переходе от одного опорного решения к другому очевидно.
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Требование 2 доказывается с использованием формул пересчета
элементов таблицы, приведенных в пункте "Метод Гаусса. Метод
Жордана – Гаусса".
Постановка задачи линейного программирования. Основные определения Математическое программирование – это математическая
дисциплина, изучающая экстремальные задачи и методы их решения. В общем виде математическая постановка экстремальной
задачи состоит в определении наибольшего или наименьшего
f ( x1 , x2 ,..., xn )
при условиях
значения целевой функции
g i ( x1 , x2 ,..., xn )  bi , i  1, m , где f и gi – заданные функции, а bi –
действительные числа. В зависимости от вида и свойств функций
f и gi математическое программирование можно рассматривать
как ряд самостоятельных дисциплин, каждая из которых изучает
и разрабатывает методы решения задач определенного класса.
Если все функции f и gi линейные, то задача является задачей
линейного программирования.
Постановка задачи линейного программирования
(стандартная форма)
Найти вектор-план X  ( x1 , x2 ,..., xn ) , удовлетворяющий условиям
n
a
j 1
ij
x j  b i , i  1, m
xj  0,
j  1, n
(1)
(2)
и на котором функция
n
f ( x1 , x2 ,..., xn )   c j x j
(3)
j 1
принимает максимальное значение.
Задача линейного программирования (каноническая форма).
Найти вектор-план X  ( x1 , x2 ,..., xn ) , удовлетворяющий условиям
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
n
a
x j  b i , i  1, m
(1)
xj  0,
j  1, n
(2)
j 1
ij
и на котором функция
n
f ( x1 , x2 ,..., xn )   c j x j
(3)
j 1
принимает максимальное значение.
Определение 1. Условия (1)–(2) называются ограничениями
задачи. Функция (3) называется целевой функцией.
Определение 2. Вектор-план X  ( x1 , x2 ,..., xn ) , удовлетворяющий
условиям (1) и (2), называется допустимым решением (или
планом). Совокупность всех допустимых решений (или планов)
образует допустимое множество.
Определение 3. Допустимое решение (или план), на котором
целевая функция задачи принимает максимальное значение,
называется оптимальным.
Стандартная и каноническая формы задачи линейного
программирования эквиваленты: каждая из них с помощью
преобразований может быть записана в форме другой.
К задаче линейного программирования сводятся многие
задачи, имеющие экономическое содержание. Рассмотрим
пример такой задачи.
Задача планирования производства Предприятие производит n различных видов продукции.
План производства описывается вектором X  ( x1 , x2 ,..., xn ) , где
каждая компонента x j , j  1, n – количество продукции j -го вида,
выпускаемой по плану, x j  0 .
Для организации производственного процесса предприятие
располагает m видами различных ресурсов. Каждая компонента
bi , i  1, m вектора B  (b1 , b2 ,..., bm ) – количество ресурса i -го вида,
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
отпущенного предприятию для использования в производственном процессе.
Опишем структуру затрат, связанных с производством единицы продукции j -го вида: aij – количество ресурса i -го вида, которое расходуется на производство единицы продукции j -го
вида.
Вектор
 a1 j 


 a2 j 
Aj  
,
... 


 amj 


j  1, n ,
описывает затраты всех ресурсов на
производство единицы j -го вида продукции;
n
a
j 1
ij
x j , i  1, m
–
количество ресурса i -го вида, расходуемое на производство всей
продукции, выпускаемой по плану X  ( x1 , x2 ,..., xn ) ;
n
a x
j 1
ij
j
 bi ,
– требование уложиться в количество отпущенных ресурсов при плане производства X  ( x1 , x2 ,..., xn ) .
Каждая компонента c j , j  1, n , вектора C  (c1 , c2 ,..., cn ) – прибыль,
которую предприятие получает при производстве единицы
i  1, m
продукции j -го вида;
n
 c x – суммарная прибыль, получаемая
j 1
j
j
при реализации плана производства X  ( x1 , x2 ,..., xn )
Основная задача производства – выбор плана производства
X  ( x1 , x2 ,..., xn ) , обеспечивающего получение максимальной прибыли при соблюдении ограничений на расходование ресурса. Таким образом, постановка задачи выглядит следующим образом:
найти план производства X  ( x1 , x2 ,..., xn ) , удовлетворяющий
условиям
n
a
j 1
ij
x j  b i , i  1, m
xj  0,
j  1, n
n
и при котором суммарная прибыль f ( x1 , x2 ,..., xn )   c j x j была бы
j 1
максимальна.
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Графический метод решения задачи линейного программирования Задача. Найти вектор-план
условиям
X  ( x1, x2 ) ,
удовлетворяющий
a11 x1  a12 x2  b1 ,
a x  a x  b ,
2
 21 1 22 2
..........................

am1 x1  am 2 x2  bm ,
 x1  0,

 x2  0,
и на котором функция f ( x1 , x2 )  c1 x1  c2 x2 принимает максимальное или минимальное значение.
Задача задана в стандартной форме, n  2 . Выясним, что
представляет собой допустимое множество задачи.
Уравнение a j1 x1  a j 2 x2  b j определяет множество точек,
лежащих на прямой.
Неравенство a j1 x1  a j 2 x2  b j определяет множество точек,
лежащих в одной из полуплоскостей, на которые эта прямая
делит координатную плоскость X 1OX 2 .
Пример 1. Построить множество точек ( x1 , x2 ) , удовлетворяющих неравенству
2 x1  3x2  6 .
Построим прямую 2 x1  3x2  6 . Прямая делит координатную
плоскость X 1OX 2 на две полуплоскости. Для того чтобы выяснить,
какую полуплоскость определяет данное неравенство, берут
пробную точку и подставляют ее координаты в неравенство. Если
получается верное числовое неравенство, то данное неравенство
определяет полуплоскость, которой взятая пробная точка принадлежит; если получается неверное числовое неравенство, данное
неравенство определяет полуплоскость, которой взятая пробная
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
точка не принадлежит. В данном случае в качестве пробной
точки удобно взять точку O(0, 0) – начало координат.
Пример 2. Построить множество точек ( x1 , x2 ) , удовлетворяющих неравенству
2 x1  4 x2  0 .
Поскольку прямая 2 x1  4 x2  0 проходит через точку O(0, 0) начало координат, то брать ее в качестве пробной нельзя. В
качестве пробной точки можно взять, например, точку (1, 0) .
Неравенство x1  0 определяет множество точек, лежащих в
правой полуплоскости. Неравенство x2  0 определяет множество
точек, лежащих в верхней полуплоскости. Система неравенств
 x1  0,

 x2  0,
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
определяет множество точек, лежащих одновременно в правой и
верхней полуплоскостях, т. е. в первой четверти координатной
плоскости X 1OX 2 .
Допустимое множество задачи – пересечение конечного
числа полуплоскостей.
Пример 3. Построить множество точек ( x1 , x2 ) , удовлетворяющих системе неравенств:
5 x1  4 x2  20,
 2 x  3x  24,
2
 1
 x1  3x2  3,
 x  0,
 1
 x1  0.
Построим каждую из полуплоскостей и найдем их пересечение (общую часть). Множество точек, удовлетворяющих данной системе неравенств – многоугольник OABCD , лежащий в
первой четверти координатной плоскости X 1OX 2 .
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Уравнение f ( x1 , x2 )  const определяет множество точек, лежащих на прямой c1 x1  c2 x2  const , и называется линией уровня
целевой функции задачи. Множество линий уровня, соответствующих различным значениям const , образуют семейство параллельных прямых.
Вектор f  (c1 , c2 ) называется вектором-градиентом; он указывает направление возрастания значений целевой функции
f ( x1 , x2 )  c1 x1  c2 x2 . Вектор-градиент f  (c1 , c2 ) перпендикулярен
линиям уровня целевой функции, т. е. прямым c1 x1  c2 x2  const .
Пример 4. Построить линии уровня функции f ( x1 , x2 )  3x1  2 x2
и вектор-градиент. 3x1  2 x2  const – уравнение линий уровня. В
качестве примера рассмотрим const  0 : 3x1  2 x2  0 и const  6 :
3 x1  2 x2  6 . f  (3, 2) .
Рассмотрим графическое решение задачи линейного
программирования.
Задача 1. Найти вектор-план X  ( x1, x2 ) , удовлетворяющий
системе неравенств
5 x1  4 x2  20,
 2 x  3x  24,
2
 1
 x1  3x2  3,
 x  0,
 1
 x1  0
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
и на котором целевая функция f ( x1 , x2 )  3x1  2 x2 принимает максимальное значение.
Решение.
1. Строим допустимое множество задачи – множество точек
( x1 , x2 ) , удовлетворяющих данной системе неравенств, – это
многоугольник OABCD .
2. Строим линию уровня целевой функции 3x1  2 x2  0 и
вектор-градиент. f  (3, 2)
3. Переходим с одной линии уровня на другую в направлении вектора-градиента до тех пор, пока не будет найдена точка
выхода из допустимого множества. В данном случае точка
C (9, 2) – точка выхода. Задача имеет единственное решение.
Ответ: X  (9, 2) , f max  31 .
Рассмотрим задачу, которая будет отличаться от задачи 1
тем, что в ней будем искать минимальное значение целевой
функции.
Задача 2. Найти вектор – план X  ( x1, x2 ) , удовлетворяющий
системе неравенств
5 x1  4 x2  20,
 2 x  3x  24,
2
 1
 x1  3x2  3,
 x  0,
 1
 x1  0
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
и на котором целевая функция f ( x1 , x2 )  3x1  2 x2 принимает минимальное значение.
Решение. Допустимое множество, линия уровня целевой
функции и вектор-градиент остаются без изменения. Переходим с
одной линии уровня на другую в направлении вектора-градиента
до тех пор, пока не будет найдена точка входа в допустимое
множество. В данном случае точка O(0, 0) - точка входа. Задача
имеет единственное решение.
Ответ: X  (0, 0) , f min  0 .
Изменим условие задачи 1 так, чтобы она имела бесконечное
множество решений. Для этого поменяем целевую функцию так,
чтобы ее линия уровня была параллельна одной из сторон
многоугольника OABCD .
Задача 3. Найти вектор-план X  ( x1, x2 ) , удовлетворяющий
системе неравенств
5 x1  4 x2  20,
 2 x  3 x  24,
2
 1
 x1  3x2  3,
 x  0,
 1
 x1  0
и на котором целевая функция f ( x1 , x2 )  x1  3x2 принимает максимальное значение.
Решение. Допустимое множество останется без изменения.
Строим линию уровня x1  3x2  0 и вектор-градиент f  (1, 3) новой
целевой функции. Замечаем, что линия уровня параллельна
стороне CD многоугольника OABCD .
Переходим с одной линии уровня на другую в направлении
вектора-градиента до тех пор, пока не будет найдена точка выхода из допустимого множества. В данном случае таких точек
будет бесконечно много: точки отрезка CD  – это точки выхода.
Задача имеет бесконечно много решений. Запишем их. Для этого
воспользуемся уравнением отрезка: X   C  (1   ) D, 0    1 , где
C (9, 2) , D  (3, 0) .
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 x1 
9
3
       (1   )   , x1  9  3  3  3  6 , x2  2 .
 2
0
 x2 
Ответ: X  (3  6 , 2 ), 0    1 , f max  31 .
Изменим условие задачи 1 так, чтобы она была неразрешима.
Для этого уберем из системы неравенств задачи второе неравенство.
Задача 4. Найти вектор-план X  ( x1, x2 ) , удовлетворяющий
системе неравенств
5 x1  4 x2  20,

x1  3x2  3,


 x1  0,
 x1  0
и на котором целевая функция f ( x1 , x2 )  3x1  2 x2 принимает максимальное значение.
Решение.
1. Строим допустимое множество задачи – множество точек
( x1 , x2 ) , удовлетворяющих данной системе неравенств, – это неограниченная многоугольная область AOD .
2. Строим линию уровня целевой функции 3x1  2 x2  0 и
вектор-градиент f  (3, 2) .
3. Переходим с одной линии уровня на другую в направлении
вектора-градиента до тех пор, пока не будет найдена точка выхода
из допустимого множества. В данном случае такой точки нет.
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Ответ: задача неразрешима, т. к. целевая функция не ограничена на допустимом множестве.
Причиной неразрешимости задачи может быть также тот
факт, что допустимое множество пустое.
Задача 5. Найти вектор-план X  ( x1, x2 ) , удовлетворяющий
системе неравенств
5 x1  4 x2  20,

x1  3 x2  3,


 x1  0,
 x1  0
и на котором целевая функция f ( x1 , x2 )  3x1  2 x2 принимает максимальное значение.
Решение.
Строим допустимое множество задачи – множество точек
( x1 , x2 ) , удовлетворяющих данной системе неравенств, и обнаруживаем, что это множество пустое.
Ответ: задача неразрешима, т. к. допустимое множество
пусто.
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Решение задачи линейного программирования симплекс­методом с графической иллюстрацией Задача 1. Найти вектор-план X   x1 , x2  , удовлетворяющий
системе неравенств
 5 x1  4 x2  20,
 2 x  3 x  24,

1
2

 x1  3 x2  3,
 x1  0, x2  0
и на котором целевая функция f  3x1  2 x2 принимает максимальное значение.
Задача 1 задана в стандартной форме. Запишем ее в канонической форме. Для этого введем неотрицательные вспомогательные переменные х3 , х4 , х5 .
Задача 2. Найти вектор-план X   x1 , x2 , x3 , x4 , x5  , удовлетворяющий системе уравнений
 20,
5 x1  4 x2  x3

 x4
 24,
 2 x1  3 x2
 x  3x
 x5  3
1
2

xi  0, i  1,5
и неравенств
и на котором целевая функция f  3x1  2 x2  0  x3  0  x4  0  x5 принимает максимальное значение.
Решим задачу симплекс-методом и проиллюстрируем
решение графически. Для этого построим допустимое множество:
26
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Решение задачи 2 симплекс-методом.
Базис B
A3
20
A4
24
A5
f
A3
A4
A1
f
A3
A2
A1
f
3
0
35
18
3
9
57
2
9
31
A1
A2
A3
A4
A5
-5
2
1
-3
0
0
1
0
0
0
1
0
4
3
-3
-2
-11
9
3
-11
0
1
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
11/9
1/9
1/3
11/9
0
0
1
0
5
-2
1
3
23/9
-2/9
1/3
5/9
Комментарий к решению.
1) Запишем коэффициенты системы уравнений в таблицу.
х1 , х2 – свободные переменные, x3 , x4 , x5 – базисные переменные.
Х = (0, 0, 20, 24, 3) – исходное опорное решение соответствует угловой точке О (0, 0).
27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
f  3 х1  2 х2
– целевая функция, выраженная через свободные
переменные.
f  0 – значение целевой функции на опорном решении.
Для того чтобы увеличить значение целевой функции, надо
одну из свободных переменных с положительным коэффициентом, например, x1 , перевести из свободных переменных в
базисные, т. е. перейти к другому опорному решению.
2) x2 , x5 – свободные переменные, x1 , x3 , x4 – базисные
переменные.
Х = (3, 0, 18, 35,0) – новое опорное решение соответствует
угловой точке D (3,0).
f  11х2 – 3 х5  9 – целевая функция, выраженная через
свободные переменные.
f  9 – значение целевой функции на опорном решении.
Для того чтобы увеличить значение целевой функции, надо
свободную переменную х2 с положительным коэффициентом перевести в базисную, т. е. перейти к другому опорному решению.
3) х4 , х5 – свободные переменные, x1 , x2 , x3 – базисные
переменные.
Х = (9, 2, 57, 0, 0) – новое опорное решение соответствует
угловой точке С (9,2).
f 
11
5
x4  x5  31
3
9
– целевая функция, выраженная через
свободные переменные.
f  31 – значение целевой функции на опорном решении.
Увеличить значение целевой функции невозможно, т. к. коэффициенты свободных переменных отрицательны. Задача решена.
Ответ задачи 2. X опт  (9, 2, 57, 0, 0), f max  31 .
Ответ задачи 1. X опт  (9, 2), f max  31 .
Замечание. Коэффициенты целевой функции, выраженной
через свободные переменные, взятые с противоположным знаком, записываются четвертой строкой в таблицу. Дело в том, что
целевая функция рассматривается как еще одно уравнение в
системе:
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
f  3 x1  2 x2  0 в первом случае, f  11х2  3 х5  9
11
5
случае и f  x4  x5  31 в третьем случае.
3
9
во втором
Эта строка называется строкой оценок. Опорный план оптимальный, если все оценки неотрицательны (для задачи на максимум).
Теоретическое обоснование симплекс­метода решения задачи линейного программирования Рассмотрим задачу линейного программирования, заданную
в канонической форме.
Задача. Найти вектор-план X  ( x1 , x2 ,..., xn ) , удовлетворяющий
условиям
n
a
x j  b i , i  1, m
(1)
xj  0,
j  1, n
(2)
j 1
ij
и на котором целевая функция
n
f ( x1 , x2 ,..., xn )   c j x j
(3)
j 1
принимает максимальное значение.
Запишем эту задачу в векторной форме:
найти вектор-план X  ( x1 , x2 ,..., xn ) , удовлетворяющий условиям
(1)
x1 A1  x2 A2  ...  xn An  B
xj  0,
и на котором целевая функция
(2)
j  1, n
n
f ( x1 , x2 ,..., xn )   c j x j
j 1
принимает максимальное значение.
29
(3)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Здесь A1 , A2 ,... An , B – m -мерные векторы-столбцы, составленные из коэффициентов при переменных и свободных коэффициентов системы уравнений (1).
Определение 1. Вектор-план X  ( x1 , x2 ,..., xn ) называется опорным планом (решением) задачи линейного программирования,
заданной в канонической форме, если система векторов A1 , A2 ,... An ,
входящих в разложение x1 A1  x2 A2  ...  xn An  B с положительными коэффициентами x1 , x2 ,..., xn , линейно независима.
Определение 2. Опорный план (решение) называется невырожденным, если он содержит ровно m положительных координат, в противном случае он называется вырожденным.
Определение 3. Пусть X 1 , X 2 ,..., X k – точки пространства R n .
Выпуклой линейной комбинацией этих точек называется сумма
1 X 1   2 X 2  ...   k X k , где 1 ,  2 ,...  k – неотрицательные числа,
сумма которых равна 1:  i  0, i  1, k , 1   2  ...   k  1 .
Определение 4. Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит и их выпуклую линейную комбинацию.
Определение 5. Точка X выпуклого множества называется
угловой, если она не может быть представлена в виде выпуклой
линейной комбинации каких-нибудь двух других различных
точек этого множества.
Теорема 1. Допустимое множество (множество планов)
задачи линейного программирования, заданной в канонической
форме, является выпуклым.
Определение 6. Допустимое множество (множество планов)
задачи линейного программирования, заданной в канонической
форме, называется многогранником решений, а всякая угловая
точка многогранника решений называется его вершиной.
Теорема 2. Если задача линейного программирования имеет
оптимальное решение (оптимальный план), то максимальное значение целевая функция задачи принимает в одной из вершин
многогранника решений. Если максимальное значение целевая
функция задачи принимает более чем в одной вершине, то она
принимает его во всякой точке, которая является выпуклой
линейной комбинацией этих вершин.
30
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Теорема 3. Если система векторов A1 , A2 ,... Ak , (k  n) , в разложении x1 A1  x2 A2  ...  xn An  B линейно независима и такова, что
x1 A1  x2 A2  ...  xk Ak  B , где все xi  0 , то точка X  ( x1 , x2 ,..., xk , 0,..., 0)
является вершиной многогранника решений.
Теорема 4. Если X  ( x1 , x2 ,..., xn ) – вершина многогранника
решений, то векторы Ai , соответствующие положительным xi в
разложении x1 A1  x2 A2  ...  xn An  B , линейно независимы.
Сформулированные теоремы позволяют сделать следующие
выводы. Непустое допустимое множество (множество планов) задачи линейного программирования, заданной в канонической форме, образует выпуклый многогранник. Напомним, что допустимое
множество – это множество неотрицательных решений системы
уравнений (1). Каждой вершине многогранника соответствует
опорное решение системы уравнений (1). В одной из вершин многогранника, т. е. на одном из опорных решений, значение целевой
функции является максимальным (при условии, что целевая функция ограничена сверху на допустимом множестве). Если максимальное значение целевая функция задачи принимает более чем в
одной вершине, то она принимает его во всякой точке, которая
является выпуклой линейной комбинацией этих вершин.
Симплекс­метод решения задачи линейного программирования Для решения задачи линейного программирования симплексметодом задача должна быть записана в канонической форме и
найдено исходное невырожденное опорное решение. Симплексметод заключается в переходе от одного опорного решения к
другому. Этот переход направленный, т. е. новый опорный план
"лучше" предыдущего. Это означает следующее: если задача на
максимум, то значение целевой функции на новом опорном
решении больше, чем на предыдущем; если задача на минимум,
то значение целевой функции на новом опорном решении
меньше, чем на предыдущем. Переход осуществляется до тех
пор, пока не будет найден оптимальный план или не будет решен
вопрос о неразрешимости задачи. Геометрически это означает
31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
переход от одной вершины к другой вершине выпуклой
многогранной области.
Каждый опорный план проверяется на оптимальность с помощью оценок  j векторов Аj . Оценки векторов – это коэффициенты целевой функции, выраженной через свободные переменные и взятые с противоположным знаком.
Сформулируем теоремы для задачи линейного программирования на максимум.
Теорема 1 (признак оптимальности опорного решения).
Опорное решение задачи является оптимальным, если все оценки
 j  0, j  1, n .
Теорема 2. Если оценка  k  0 для некоторого j  k и среди
чисел aik (координат вектора Ak ) нет положительных ( aik  0 ), то
задача не разрешима, т. к. целевая функция задачи не ограничена
на допустимом множестве.
Теорема 3. Если опорное решение X 1 задачи не вырождено и
 k  0 , но среди чисел aik (координат вектора Ak ) есть положительные, то существует опорное решение X 2 такое, что
f ( X 2 )  f ( X 1 ) , т. е. существует опорное решение, которое "лучше"
предыдущего.
Сформулируем теоремы для задачи линейного программирования на минимум.
Теорема 4 (признак оптимальности опорного решения).
Опорное решение задачи является оптимальным, если все оценки
 j  0, j  1, n .
Теорема 5. Если оценка  k  0 для некоторого j  k и среди
чисел aik (координат вектора Ak ) нет положительных ( aik  0 ), то
задача не разрешима, т. к. целевая функция задачи не ограничена
на допустимом множестве.
Теорема 6. Если опорное решение X 1 задачи не вырождено и
 k  0, но среди чисел aik (координат вектора Ak ) есть положительные, то существует опорное решение X 2 такое, что
f ( X 2 )  f ( X 1 ) , т. е. существует опорное решение, которое "лучше"
предыдущего.
Сформулированные теоремы позволяют проверить, является
ли найденное опорное решение оптимальным, и выявить целесо32
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
образность перехода к новому опорному решению. Если задача
имеет вырожденные опорные решения, то при переходе от одного опорного решения к другому значение целевой функции
может оказаться прежним.
Рассмотрим пример решения задачи линейного программирования симплекс-методом.
Задача. Найти вектор-план X  ( x1 , x2 , x3 ) , удовлетворяющий
условиям
 2 x1  x2  x3  4,

 x3  5,
 x1

 3,
 2 x1  2 x2
(1)
xj  0,
(2)
j  1,3
и на котором целевая функция
f ( x1 , x2 , x3 )  2 x1  x2  x3
(3)
принимает максимальное значение.
Обратим внимание на то, что задача задана не в канонической форме. Запишем задачу в канонической форме. Для этого
используем вспомогательные переменные x4, x5 . Новая задача
будет выглядеть так:
Задача. Найти вектор-план X  ( x1 , x2 , x3 , x4 , x5 ) , удовлетворяющий условиям
2 x1  x2  x3
 4,

 x3  x4
 5,
 x1

 x5  3,
2 x1  2 x2
xj  0,
j  1,5
(1)
(2)
и на котором целевая функция
f ( x1 , x2 , x3 )  2 x1  x2  x3  0  x4  0  x5
принимает максимальное значение.
33
(3)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Заметим, что система уравнений задачи такова, что исходное
опорное решение надо найти.
Базис
A3
A4
A1
A3
A4
A2
A5
A4
A2
Опорное
решение
B
A1 A2 A3 A4 A5
4
5
3
4
13
3
1
11/2
3/2
2
1
2
2
5
2
0
0
1
1
0
2
1
2
2
-1
-3
1
-4
1
11/2
3/2
0
0
0
1
-2 0 0 0
-1 1 0 1
-3 0 1 5/2
1 0 0 -1/2
-1
5
5
4
2
2
1
2
0 0 0
0 2 0
0 -2 1
1 1 0
-1
1
0
0
4
4
0
0
1
-2
0
1
0
0
1
0
0
2
0
1
0
0
1
0
0
1
0
0
0
0
-1
0
0
-1
1
5/2
-1/2
X 1   3 2 , 0,1,11 2 , 0
X 2   0, 3 2, 5 2,10,
X 3   0, 4, 0,5, 5 
Ответ: X опт.  (0; 4; 0; 5; 5), f max  4 .
Для того чтобы получить ответ для исходной задачи, надо
отбросить вспомогательные переменные.
Ответ: X опт.  (0; 4; 0), f max  4 .
Комментарий к решению.
Решение задачи начали с поиска опорного решения системы
уравнений. Опорное решение X 1  (3 2, 0, 5,5, 0) – исходное опорное решение для решения задачи симплекс-методом. Проверим
это решение на оптимальность с помощью оценок. Для этого выразим базисные переменные x1 , x3 , x4 через свободные переменные x2 , x5 и подставим их в целевую функцию. Получим
f ( x2 , x5 )  2 x2  0  x5  4 . Коэффициенты целевой функции, выра-
34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
женной через свободные переменные и взятые с противоположным знаком, запишем в строку оценок.
Так как вектор A2 имеет отрицательную оценку, то опорное
решение X 1  (1,5; 0; 5,5; 0) не является оптимальным, и надо перейти к другому опорному решению, сделав переменную x2 базисной.
Строку оценок будем пересчитывать как еще одну строку в
таблице с целью сделать оценку вектора A2 равной 0.
Так как вектор A5 имеет отрицательную оценку, то новое
опорное решение X 2  (0;1,5; 2,5;10; 0) не является оптимальным, и
надо перейти к другому опорному решению, сделав переменную
x5 базисной. Строку оценок будем пересчитывать как еще одну
строку в таблице с целью сделать оценку вектора A5 равной 0.
Новое опорное решение X 3  (0; 4; 0; 5; 5) является оптимальным, т. к. все оценки неотрицательны.
Обратим внимание на тот факт, что значение целевой
функции на каждом новом опорном решении было больше, чем
на предыдущем. Действительно, f ( X 1 )  4 , f ( X 2 )  1 , f ( X 3 )  4 .
Замечание. Для поиска исходного опорного решения задачи
можно использовать метод искусственного базиса.
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Контрольные работы Контрольная работа № 1
Решить систему линейных уравнений методом ЖорданаГаусса
1.
5 x1  12 x2  5 x3  3 x4  10,

4 x1  3 x2  x3  3 x4  2,
11x  11x  4 x  8 x  8.
2
3
4
 1
3.
 x1  x2  3 x3  x4  6,

7 x1  5 x2  7 x3  x4  8,
 x  8 x  18 x  5 x  6.
2
3
4
 1
4.
5.
3 x1  2 x2  x3  6 x4  0,

4 x1  x2  x3  4 x4  0,
 x  4 x  3 x  2 x  0.
2
3
4
 1
3 x1  2 x2  x3  x4  4,
6. 2 x1  5 x2  3x3  2 x4  1,
3 x  4 x  2 x  x  2.
2
3
4
 1
7.
2 x1  7 x2  3 x3  x4  12 x5  0,

 x1  6 x2  4 x3  2 x4  10 x5  0,
3 x  10 x  4 x  2 x  21x  0.
2
3
4
5
 1
3 x1  x2  4 x3  2 x4  7,
8. 5 x1  2 x2  7 x3  x4  9,

3 x1  2 x2  5 x3  5 x4  19.
9.
2 x1  x2  x3  x4  3 x5  3,

5 x1  4 x2  4 x3  4 x4  15 x5  9,
3 x  2 x  x  2 x  7 x  5.
2
3
4
5
 1
11.
 x1  x2  x3  x4  x5  1,

 x1  x2  3 x3  2 x4  x5  8,
 x  x  5 x  x  2 x  10.
3
4
5
 1 2
13.
 x1  2 x2  3 x3  4 x4  4,
2 x  3 x  4 x  5 x  4,
 1
2
3
4

 x1  x2  2 x3  2 x4  2,
4 x1  3 x2  4 x3  6 x4  3.
 x1  x2  3 x3  4 x4  1,
2. 2 x1  2 x2  2 x3  3x4  2,
 x  x  13 x  18 x  1.
3
4
 1 2
36
 x1  3 x2  3 x3  2,

4 x1  4 x2  4 x3  5,
 x  5 x  7 x  1.
2
3
 1
10.
7 x1  2 x2  2 x3  2 x4  3x5  12,

2 x1  x2  x3  x4  3 x5  3,
 x  x  x  x  6 x  3.
4
5
 1 2 3
12.
 x1  2 x2  3 x3  0,
2 x  3 x  4 x  0,
 1
2
3

2 x1  x2  x3  1,
2 x1  2 x2  3 x3  1.
14.
 x1  2 x2  2 x3  x4  3,

2 x1  3 x2  3 x3  5 x4  3,

 x1  x2  x3  2,
2 x1  x2  x3  3 x4  4.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
15.
2 x1  x2  4 x3  x4  9,
 x  2 x  3 x  x  1,
 1
2
3
4

2 x1  x2  4 x3  x4  11,
3 x1  2 x2  x3  x4  9.
17.
2 x1  x2  3 x3  2 x4  x5  2,
 x  x  x  x  x  3,
 1 2
3
4
5

3 x1  2 x2  x3  x4  4 x5  4,
4 x1  x2  4 x3  4 x4  5 x5  9.
19.
7 x1  9 x2  4 x3  2 x4  2,
2 x  2 x  x  x  6,
 1
2
3
4

5 x1  6 x2  3 x3  2 x4  3,
2 x1  3 x2  x3  x4  0.
21.
6 x1  5 x2  2 x3  4 x4  4,
9 x  x  4 x  x  13,
 1 2
3
4

3 x1  4 x2  2 x3  2 x4  1,
3 x1  9 x2  2 x4  11.
23.
2 x1  x2  6 x3  3 x4  1,
7 x  4 x  2 x  15 x  32,
 1
2
3
4

 x1  2 x2  4 x3  9 x4  5,
 x1  x2  2 x3  6 x4  8.
25.
16.
2 x1  x2  3 x3  2 x4  x5  3,
4 x  x  9 x  7 x  6,
 1 2
3
5

 x1  3 x2  10 x3  4 x4  6 x5  3,
3 x1  6 x3  x4  4 x5  4.
18.
 x1  2 x2  3 x3  x4  0,
 x  x  x  x  6,
 1 2 3 4

2 x1  x2  x3  x4  1,
2 x1  2 x2  3 x3  x4  7.
20.
2 x1  3 x2  3 x3  2 x4  3,
6 x  9 x  2 x  x  4,
 1
2
3
4

10 x1  3 x2  3 x3  2 x4  3,
8 x1  6 x2  x3  3 x4  7.
22.
4 x1  3 x2  x3  5 x4  7,
 x  2 x  2 x  3 x  3,
 1
2
3
4

3 x1  x2  2 x3  1,
2 x1  3 x2  2 x3  8 x4  7.
24.
 x1  2 x2  3 x3  2 x4
2 x  x  2 x  3x
 1 2
3
4

3 x1  2 x2  x3  2 x4
2 x1  3 x2  2 x3  x4
 1,
 2,
 5,
 11.
2 x1  x2  3 x3  5 x4  1,
 x  x  5 x  2,
 1 2
3

3 x1  2 x2  2 x3  5 x4  3,
7 x1  5 x2  9 x3  10 x4  8.
Контрольная работа № 2
Записать данные задачи в таблицу. Построить математическую модель задачи. Решить задачу графически и симплексметодом.
1. Для производства изделий A и B используется три вида
станков. На производство одного изделия A требуется 6 часов
работы станка первого вида, 4 часа работы станка второго вида и
3 часа работы станка третьего вида. На производство одного
37
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
изделия B требуется 2 часа работы станка первого вида, 3 часа
работы станка второго вида и 4 часа работы станка третьего вида.
Месячный ресурс работы всех станков первого вида, имеющихся
на заводе, равен 600 часов, всех станков второго вида –520 часов
и всех станков третьего вида – 600 часов. Прибыль от реализации
одного изделия А равна 6 млн руб., изделия В – 3 млн руб.
Данные задачи записать в таблицу. Найти план производства на
месяц, обеспечивающий максимальную прибыль предприятию.
Составить математическую модель задачи и решить ее.
2. На ферме разводят нутрий и кроликов. В недельный
рацион нутрии входят 17 кг белков, 11 кг углеводов и 5 кг жиров,
а для кролика эти нормы соответственно равны 13 кг, 15 кг и 7 кг.
Доход от реализации одного кролика 15 тыс. руб., а от
реализации одной нутрии 25 тыс. руб. Ферма не может
расходовать в неделю более 184 кг белков, 152 кг углеводов и
70 кг жиров. Данные задачи записать в таблицу. Найти план
разведения животных, обеспечивающий ферме максимальный
доход. Составить математическую модель задачи и решить ее.
3. Для изготовления изделий А и В предприятие использует
три вида сырья. На производство одного изделия А требуется
12 кг сырья первого вида, 10 – второго и 3 – третьего, а на производство одного изделия В, соответственно, 3 кг, 5 кг и 6 кг. Производство обеспечено сырьем первого вида в количестве 684 кг,
второго – 690 кг и третьего 558 кг. Одно изделие А дает предприятию 6 млн руб. прибыли, изделие В – 2 млн руб. Данные
задачи записать в таблицу. Найти план производства, обеспечивающий максимальную прибыль предприятию. Составить
математическую модель задачи и решить ее.
4. Мастерская ремонтирует трактора двух типов: 1 – мощностью 300 л. с. и 2 – мощностью 200 л. с. За неделю мастерская
может отремонтировать не более 150 тракторов. За ремонт
трактора 1-го типа получают 2 тыс. руб., 2-го типа – 1 тыс. руб.
Найти недельный план ремонта тракторов, при котором мастерская получит не менее 200 тыс. руб. и суммарная мощность
отремонтированных тракторов будет наибольшей, если надо
отремонтировать не менее 50 тракторов 2-го типа. Данные задачи
записать в таблицу. Составить математическую модель задачи и
решить ее.
38
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
5. Для производства изделий А и В используется три вида
оборудования. На производство одного изделия А оборудование
первого вида используется в течение 5 ч, второго вида – 4 ч и
третьего вида – 3 ч. На производство одного изделия В нормы
соответственно равны 3 ч, 3 ч и 4 ч. В месяц оборудование
первого вида может быть использовано в течение 750 ч, второго –
630 ч, третьего – 700 ч. Прибыль от реализации одного изделия А
равна 50 тыс. руб., В – 60 тыс. руб. Данные задачи записать в таблицу. Найти план производства, обеспечивающий максимальную
прибыль предприятию. Составить математическую модель задачи
и решить ее.
6. Завод выпускает два вида редукторов. На изготовление одного редуктора первого вида расходуется 3 т чугуна и 1 т стали, а
на изготовление одного редуктора второго вида 1 т чугуна и 2 т
стали. Завод располагает на месяц 160 т чугуна и 120 т стали и
имеет обязательное задание – изготовить не менее 60 редукторов
обоих видов вместе. Прибыль от продажи одного редуктора
первого вида равна 40 тыс. руб., а второго – 10 тыс. руб. Данные
задачи записать в таблицу. Найти месячный план производства
редукторов, обеспечивающий заводу максимальную прибыль.
Составить математическую модель задачи и решить ее.
7. Для изготовления изделий А и В используется три вида
сырья. На производство одного изделия А затрачивается 10 кг
сырья первого вида, 5 кг второго и 4 кг третьего. На производство
одного изделия В соответственно затрачивается 9 кг, 11 кг и
15 кг. Производство обеспечено сырьем первого вида в количестве 1 870 кг на неделю, сырьем второго вида – 1 455 кг и сырьем
третьего вида – 1 815 кг. Прибыль от реализации одного изделия
А равна 70 тыс. руб., В – 90 тыс. руб. Данные задачи записать в
таблицу. Найти план производства, обеспечивающий предприятию максимальную прибыль. Составить математическую модель
задачи и решить ее.
8. Фабрика выпускает вязаные костюмы и кофты, используя
шерстяную и синтетическую пряжу. На один костюм идет 1 300 г
шерсти и 100 г синтетики, а на одну кофту 500 г шерсти и 200 г
синтетики. Фабрика имеет на неделю 75 кг шерсти и 22 кг
синтетики. Общее количество выпущенных за неделю изделий
должно быть не менее 70 штук. Костюм дает 40 руб., кофта –
39
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
10 руб. прибыли. Данные задачи записать в таблицу. Какое
количество костюмов и кофт должна выпускать фабрика, чтоб
обеспечить себе прибыль? Составить математическую модель
задачи и решить ее.
9. В мастерской при изготовлении шкафа механическая пила
используется в течение 8 часов, строгальный станок – 6 часов,
сверлильный станок – 3 часа. При изготовлении стола нормы
соответственно равны 2 часа, 3 часа и 2 часа. Недельный фонд
времени механических пил, имеющихся в мастерской – 840 часов, строгальных станков – 870 часов и сверлильных станков –
560 часов. Прибыль от реализации шкафа 600 тыс. руб., стола
200 тыс. руб. Данные задачи записать в таблицу. Какое количество шкафов и столов должна выпускать мастерская, чтобы
обеспечить себе прибыль? Составить математическую модель
задачи и решить ее.
10. Сельхозпредприятие располагает удобрениями двух видов: М и N. В одной тонне удобрения М содержится 3 000 ед.
вещества В1, 6 000 ед. вещества В2 и 9 000 ед. вещества В3, а в
1 тонне удобрения N соответственно 1 000, 6 000 и 15 000 ед. На
1 га должно быть внесено не более 20 000 ед. вещества В1,
60 000 ед. В2 и 120 000 ед. В3. При соблюдении этих норм прибавка урожая от внесения одной тонны удобрения М составит
4 500 кг, удобрения N – 3 500 кг. Данные задачи записать в таблицу. Какие количества удобрений М и N надо внести на 1 га,
чтобы прибавка урожая была наибольшей? Составить математическую модель задачи и решить ее.
11. Для производства двух видов изделий А и В предприятие
использует три типа оборудования. Время обработки изделия А
на оборудовании 1-го типа составляет 2 часа, на оборудовании 2го типа – 1 час, на оборудовании 3-го типа –— 12 часов. Время
обработки изделия В на оборудовании 1-го типа составляет
8 часов, на оборудовании 2-го типа – 1 час, на оборудовании 3-го
типа – 3 часа. Оборудование 1-го и 3-го типов предприятие
может использовать не более 22 часов и 52 часов соответственно,
а оборудование 2-го типа целесообразно использовать не менее
4 часов. Прибыль, получаемая от одного изделия вида А – 2 у. е.,
а вида В – 3 у. е. Данные задачи записать в таблицу. Найти план
40
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
производства, обеспечивающий максимальную прибыль. Составить математическую модель задачи и решить ее.
12. Мебельная фабрика специализируется на выпуске
письменных столов и книжных шкафов. При изготовлении этой
продукции требуются сосновые и березовые доски. Для изготовления одного стола требуется 0,15 куб. м сосновых досок и
0,2 куб. м березовых досок, а для изготовления шкафа – 0,2 куб. м
сосновых досок и 0,1 куб. м березовых досок. В сутки поступает
не более 60 куб. м сосновых досок и не более 40 куб. м березовых
досок. Прибыль от реализации одного стола составляет 12 руб., а
шкафа – 15 руб. Данные задачи записать в таблицу. Найти план
выпуска мебели, обеспечивающий максимальную прибыль
фабрике. Составить математическую модель задачи и решить ее.
13. Мастерская шьет женские и мужские костюмы. На женский костюм требуется 1 м шерсти, 2 м шелка и 1 человеко-день
трудозатрат. На мужской костюм требуется 3,5 м шерсти, 1 м
шелка и 1 человеко-день трудозатрат. Мастерская располагает
запасами шерсти в количестве 1 700 м и запасами шелка в
количестве 1000 м. По плану предусматривается выпуск не менее
110 костюмов. Себестоимость изготовления одного женского
костюма 3 000 руб., мужского – 4 000 руб., а заказчики платят
4 000 руб. и 5 500 руб. соответственно. Данные задачи записать в
таблицу. Какое количество женских и мужских костюмов должна
шить мастерская, чтобы обеспечить себе максимальную прибыль.
Составить математическую модель задачи и решить ее.
14. Для шитья простыней и наволочек швее отпускается не
более 80 м бязи в неделю. На простыню расходуется 2 м бязи, а
на наволочку – 1м бязи. Рынок обеспечивает сбыт не более
30 простыней и не более 40 наволочек в неделю. Продажа одной
простыни дает 5 руб. прибыли, продажа 1 наволочки – 3 руб.
Данные задачи записать в таблицу. Какое количество простыней
и наволочек должна шить швея в неделю, чтобы обеспечить себе
максимальную прибыль. Составить математическую модель
задачи и решить ее.
15. Для кормления кошки используется два вида корма:
«Вискас» и «Доктор Клаудер». В дневном рационе кошки должно
быть не менее 6 единиц питательного вещества А, не менее 12
единиц вещества В и не менее 4 единиц вещества С. В 100 г
41
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
корма «Вискас» содержится 2 единицы вещества А, 2 единицы
вещества В, а вещество С не содержится. В 100 г корма «Доктор
Клаудер» содержится 1 единица вещества А, 4 единицы вещества
В, 4 единицы вещества С. Цена 100 г корма «Вискас» – 5 руб., а
корма «Доктор Клаудер» – 6 руб. Данные задачи записать в
таблицу. Какое количество корма каждого вида надо покупать
кошке, чтобы затраты на ее питание были минимальны.
Составить математическую модель задачи и решить ее.
16. Фабрика выпускает два вида продукции А и В, для чего
использует три вида сырья, недельный запас которых составляет
20, 50, и 60 единиц соответственно. На единицу продукции вида
А затрачивается 2 единицы сырья 1-го вида, 8 единиц сырья 2-го
вида, 5 единиц сырья 3-го вида. На единицу продукции вида В
затрачивается 5 единиц сырья 1-го вида, 5 единиц сырья 2-го вида, 6 единиц сырья 3-го вида. Прибыль, получаемая от реализации единицы продукции вида А, составляет 50 руб., а прибыль,
получаемая от реализации единицы продукции вида В, составляет
40 руб. Данные задачи записать в таблицу. Найти план выпуска
продукции, обеспечивающий максимальную прибыль фабрике.
Составить математическую модель задачи и решить ее.
17. Ателье шьет вечерние и нарядные платья, используя для
этого бархат, шелковую ткань и кружево. Расход бархата, шелка
и кружева на одно вечернее платье составляет 12 м, 4 м и 3 м
соответственно. Расход бархата, шелка и кружева на одно нарядное платье составляет 4 м, 4 м и 12 м соответственно. В ателье
300 м бархата, 120 м шелка и 252 м кружева. Прибыль от реализации одного вечернего платья составляет 30 у. е, нарядного
платья – 40 у. е. Данные задачи записать в таблицу. Сколько
вечерних и нарядных платьев должно сшить ателье, чтобы
получить максимальную прибыль? Составить математическую
модель задачи и решить ее.
18. Ателье шьет платья и костюмы, используя для этого шелковую и шерстяную ткань. Расход шелка и шерсти на одно платье
составляет 3 м и 1 м соответственно. Расход шелка и шерсти на
один костюм составляет 1 м и 4 м соответственно. Недельный
запас материалов в ателье – 70 м шелка и 50 м шерсти. Рынок
обеспечивает сбыт не более 22 платьев и не более 15 костюмов в
неделю. Прибыль от реализации одного платья составляет 30 у. е,
42
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
костюма – 40 у. е. Данные задачи записать в таблицу. Сколько
платьев и костюмов должно сшить ателье, чтобы получить максимальную прибыль? Составить математическую модель задачи
и решить ее.
19. Предприятие электронной промышленности выпускает
две модели телевизоров, причем каждая модель производится на
отдельной технологической линии. Мощность первой линии не
более 60 телевизоров в сутки, мощность второй – не более
75 телевизоров. На телевизор первой модели расходуется 10 однотипных элементов электронных схем, на телевизор второй
модели – 8 таких же элементов. Максимальный суточный запас
элементов составляет 800 единиц. Прибыль от реализации одного
телевизора первой и второй моделей составляет 300 и 200 у.е.
соответственно. Данные задачи записать в таблицу. Найти план
выпуска телевизоров, обеспечивающий максимальную прибыль
предприятию. Составить математическую модель задачи и
решить ее.
20. Предприятие имеет возможность рекламировать свою
продукцию, используя местные радио- и телевизионную сети.
Затраты на рекламу в бюджете предприятия ограничены 1100 у.е.
в месяц. Каждая минута радиорекламы обходится в 5 у.е., а
каждая минута телерекламы – в 100 у.е. Предприятие хотело бы
использовать радио по крайней мере в 2 раза чаще, чем телевидение. Маркетинговые исследования показали, что объем сбыта,
обеспечиваемый каждой минутой телерекламы, в 25 раз больше
объема сбыта, обеспечиваемого каждой минутой радиорекламы.
Данные задачи записать в таблицу. Найти оптимальное распределение финансовых средств, ежемесячно отпускаемых на рекламу,
между радио- и телерекламой. Составить математическую модель
задачи и решить ее.
21. Предприятие производит два вида продукции А и В.
Объем сбыта продукции вида А составляет не менее 60% общего
объема реализации продукции обоих видов. Для изготовления
продукции А и В используется одно и то же сырье, суточный
запас которого на предприятии ограничен величиной 140 кг.
Расход сырья на единицу продукции вида А составляет 2 кг, а на
единицу продукции вида В – 4 кг. Прибыль от реализации
продукции А и В – 10 и 30 у. е. соответственно. Данные задачи
43
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
записать в таблицу. Найти план выпуска продукции, обеспечивающий максимальную прибыль предприятию. Составить математическую модель задачи и решить ее.
22. Фабрика выпускает шапки и шляпы. Суточный объем
сбыта головных уборов ограничен диапазоном от 150 до
220 штук. Предприятие хотело бы выпускать шапок по крайней
мере в два раза больше, чем шляп, что обусловлено наличием
соответствующего сырья и квалификацией работников предприятиия. Прибыль, получаемая от продажи шапки – 20 руб., а от продажи шляпы – 30 руб. Найти план выпуска продукции, обеспечивающий максимальную прибыль фабрике. Составить математическую модель задачи и решить ее.
23. Дачник покупает удобрения двух видов: А и В. В одном
пакете удобрения вида А содержится 3 усл. ед. химического
вещества а, 2 усл. ед. вещества в , 1 усл. ед. вещества с. В одном
пакете удобрения вида В содержится 1 усл. ед. химического
вещества А, 1 усл. ед. вещества В, 1 усл. ед. вещества С. На одну
сотку необходимо внести не менее 9 усл. ед. вещества А, 8 усл.
ед. вещества В, 6 усл. ед. вещества С. Цена пакета удобрения
вида А – 30 руб., вида В – 20 руб. Данные задачи записать в
таблицу. Найти наиболее экономичный план закупки удобрений
(в расчете на одну сотку). Составить математическую модель
задачи и решить ее.
24. Машинистка выполняет два вида печатных работ. Стоимость страницы первого вида – 25 руб., а одной страницы второго вида – 30 руб. Затраты времени на одну страницу работ
первого и второго вида составляют соответственно 15 и 20 минут.
Ей надо напечатать не менее 15 страниц первого вида и не менее
10 страниц второго вида. Данные задачи записать в таблицу.
Сколько страниц каждого вида надо напечатать машинистке, чтобы ее заработок был максимальным? Составить математическую
модель задачи и решить ее.
25. На приобретение оборудования для нового производственного участка выделено 20 млн руб. Оборудование надо
разместить на площади, не превышающей 72 кв. м. Предприятие
может заказать оборудование двух типов: мощные машины типа
А, каждая из которых стоит 5 млн руб., занимает 6 кв. м. и дает за
смену 7 тыс. ед. продукции и менее мощные машины типа В,
44
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
каждая из которых стоит 2 млн руб., занимает 12 кв. м. и дает за
смену 4 тыс. ед. продукции. Данные задачи записать в таблицу.
Найти оптимальный план приобретения оборудования. Составить
математическую модель задачи и решить ее.
Контрольная работа № 3
Дана задача линейного программирования. Решить задачу
графическим способом. Записать ответ.
Если задача имеет единственное решение, то видоизменить
задачу так, чтобы она: а) имела бесконечное множество решений
и решить ее; б) была неразрешима.
Если задача имеет бесконечное множество решений, то
видоизменить задачу так, чтобы она: а) имела единственное
решение и решить ее; б) была неразрешима.
Если задача неразрешима, то видоизменить задачу так, чтобы
она: а) имела единственное решение и решить ее; б) имела
бесконечное множество решений и решить ее.
1. f  2 x1  3 x2
(min)
2. f  2 x1  3 x2
4 x1  5 x2  20,

 2 x1  x2  6,

 5 x1  x2  45,
 x  x  6,
1
2

 x1  0, x2  0.
 x1  x2  4,
 2 x  x  4,
1
2

 x1  5 x2  5,
 0  x  3,
1


0  x2  3.
4. f  x1  x2
5. f  x1  x2
(max)
2 x1  x2  2,
 2 x  x  4,
 1
2

 x1  3 x2  3,
 x1  0, x2  0.
(min)
3. f  x1  x2
(min)
3 x1  4 x2  12,
 5 x  2 x  10,
 1
2

4 x1  3 x2  12,
 x1  0, x2  0.
(max)
 x1  2 x2  4,
 5 x  2 x  10,
2
 1
 4 x1  3 x2  12,
7 x  4 x  28,
2
 1
 x1  0, x2  0.
45
6. f  x1  2 x2
4 x1  x2  4,
 x  2 x  4,
 1
2

 x1  x2  3,
 x1  0, x2  0.
(min)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
7. f  4 x1  3 x2
(max)
 x1  x2  2,

 5 x1  3 x2  15,

 x1  2 x2  2,

 x1  0,
0  x2  2,5.
10. f  x1  x2
8. f  x1  2 x2
(max)
 2 x1  x2  4,
 x  x  1,
2
 1
 2 x1  x2  1,

 2 x1  3 x2  6,
0  x1  1,

 x2  0.
(min)
11. f  x1  x2
(min)
 x1  2 x2  4,
 2 x  x  4,
 1
2

 x1  x2  1
 x1  0, x2  0.
13. f  x1  x2
14. f  x1  2 x2
 x1  x2  5,
 x  x  1,
2
 1
 x1  x2  1,
0  x  2,
1

 x2  0.
16. f  2 x1  x2
 x1  x2  1,

 x1  x2  3,
 x1  x2  8,
2  x  3,
1

1  x2  4.
17. f  x1  2 x2
 x1  2 x2  4,
  x  2 x  4,
2
 1
 x1  2 x2  6,
 x  0,
 1
 x2  0.
46
12. f  x1  x2
(min)
2 x1  3 x2  6,
 x  3 x  3,
2
 1
3 x1  8 x2  24,
0  x  10,
1

 x2  0.
(max)
 x1  x2  1,
  x  x  1,
2
 1
 x1  x2  3,
0  x  2,
1

 x2  0.
(max)
(min)
4 x1  5 x2  20,
 2 x  x  10,
 1
2

3 x1  x2  12
 x1  0, x2  0.
 x1  5 x2  5,
 x  x  2,
 1
2

 x1  x2  2
 x1  0, x2  0.
(max)
9. f  x1  x2
15. f  x1  2 x2
(max)
 x1  x2  1,
  2 x  x  2,
1
2

 x1  x2  4,
0  x  3,
1

 x2  0.
(max)
18. f  3 x1  4 x2
3 x1  2 x2  6,
 3 x  2 x  7,
2
 1
2 x1  4 x2  8,
 x  1,
 1
 x2  0.
(max)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
19. f  x1  3 x2
(min)
(min)
 x1  x2  4
  2 x  6 x  12,
1
2

 x1  x2  2,
 x  2,
 1
 x2  0.
25. f   x1  x2
(min)
 x1  2 x2  4,
 2 x  x  4,
2
 1
 x1  x2  4

 x1  x2  6,
0  x1  4,

 x2  0.
 x1  2 x2  2,
 x  2 x  3,
2
 1
 x1  2 x2  6
x  x  0
 1 2
 x1  0, x2  0.
22. f  2 x1  6 x2
20. f  x1  x2
23. f  x1  x2
 x1  x2  15,
 3 x  6 x  12,
2
 1
2 x1  5 x2  50,

 x1  5 x2  0,
 x1  0,

 x2  0.
21. f  x1  x2
(min)
 x1  x2  6
 x  2 x  0,
2
 1
 x1  x2  3,
1  x  3,
1

 x2  0.
(max)
24. f  2 x1  x2
(max)
 x1  x2  3,
 3 x  6 x  20,
2
 1
 x1  2 x2  0,

 x1  x2  1,
 x1  0,

 x2  0.
(min)
 x1  x2  4,

 4 x1  x2  24,
 x1  2 x2  0,

 x1  x2  1,
 x1  0,

 x2  0.
Контрольная работа № 4
Решить задачу линейного программирования симплексметодом.
2. f  x1  4 x2  3x3  10 x4 (max)
1. f  x1  x2  x3  x4  x5 (max)
2 x  3 x  5 x  7 x  9 x  19,
2
3
4
5
 1
+ x4  2 x5  2,
 x1  x2

 x j  0, j  1, 5.
 x  x  3 x  x  0,
2
3
4
 1
 x1  14 x2 +10x3  10 x4  11,

 x j  0, j  1, 4.
47
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3. f  8 x1  6 x2  5 x3  2 x4 (max)
4. f  2 x1  x2  3x3  x4 (max)
 x  4 x  x  x  0,
2
3
4
 1
4 x1  6 x2 +3x3  7 x4  20,

 x j  0, j  1, 4.
 x  2 x  5 x  x  0,
2
3
4
 1
 x1  x2  x3  2 x4  1,

 x j  0, j  1, 4.
5. f  x1  x2  x3  x4 (max)
6. f  x1  5 x2  x3  x4 (max)
 x  3 x  7 x  x  6,
2
3
4
 1
 x1  x2  x3  3 x4  2,

 x j  0, j  1, 4.
 x  3 x  3 x  x  3,
2
3
4
 1
 3 x3  x4  4,
2 x1

 x j  0, j  1, 4.
7. f  x1  4 x2  x3  4 x4 (max)
8. f  x1  3x2  5 x3  x4 (max)
 x  x  x  x  0,
2
3
4
 1
 x1  8 x2  2 x3  5 x4  3,

 x j  0, j  1, 4.
 x  4 x  4 x  x  5,
2
3
4
 1
2 x1  7 x2  8 x3  2 x4  9,

 x j  0, j  1, 4.
9. f  2 x1  3x2  2 x3  2 x4 (max)
10. f  6 x1  x2  4 x3  5 x4 (max)
 5 x  24 x  7 x  x  41,
2
3
4
 1
 x1  2 x2  7 x3  3 x4  3,

 x j  0, j  1, 4.
3 x  4 x  x  x  4,
2
3
4
 1
5 x1  x2  x3  x4  4,

 x j  0, j  1, 4.
11. f  x1  2 x2  3x3  4 x4 (max)
12. f  x1  8 x2  x3  4 x4 (max)
x  x
 x3  x4  2,
2
 1
 x1  14 x2  10 x3  10 x4  24,

 x j  0, j  1, 4.
 x  x  x  x  0,
 1 2 3 4
 x1  8 x2  2 x3  5 x4  3,

 x j  0, j  1, 4.
13. f  x1  2 x2  x3  x4 (max)
14. f  3x1  7 x2  6 x3  5 x4 (max)
 x  x  2 x  3 x  1,
3
4
 1 2
2 x1  x2  x3  3 x4  2,

 x j  0, j  1, 4.
4 x  3 x  2 x  x  7,
2
3
4
 1
 x1  2 x2  5 x3  3 x4  12,

 x j  0, j  1, 4.
48
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
15. f  x1  2 x2  3x3  x4 (max)
16. f  x1  x2  x3  x4 (max)
 x  3 x  x  2 x  4,
2
3
4
 1
 x1  x2  x3  0,

 x j  0, j  1, 4.
 x  3 x  x  2 x  5,
2
3
4
 1
2 x1  x2  x3  x4  1,

 x j  0, j  1, 4.
17. f  x1  x2  2 x3  x4  x5  x6 (max)
18. f  x1  x2  3x3  2 x4  x5 (max)
 x  3 x  x  3 x  4 x  x  6,
2
3
4
5
6
 1
 x1  x2  x3  x4  x6  2,

 x j  0, j  1, 6.
3 x  x  2 x  x  x  2,
3
4
5
 1 2
2 x1  x2  x3  x4  4 x5  3,

 x j  0, j  1, 5.
19. f  2 x1  x2  x3  x4  4 x5  x6 (max)
3 x  x  2 x  6 x  9 x  3 x  15,
3
4
5
6
 1 2
 x1  2 x2  x3  2 x4  x6  5,

 x j  0, j  1, 6.
20. f  x1  x2  3x3  2 x4  x5 (max)
3 x  x  2 x  x  x  2,
3
4
5
 1 2
2 x1  x2  x3  x4  4 x5  3,

 x j  0, j  1, 5.
21. f  x1  x2  x3  x4 (max)
22. f  x1  4 x2  x3  x4  x5 (max)
 x1  x2  x3  3 x4  3,
 x  x  x  x  1,
4
 1 2 3
 x  x  x  x  1,
3
4
 1 2
 x  0, j  1, 4.
 j
5 x1  5 x2  x3  2 x4  x5  28,

 x1  2 x2  x4  2,
3 x  4 x  x  12,
2
5
 1
 x  0, j  1, 5.
 j
24. f  6 x1  2 x2  x3  x4  x5 (max)
23. f  39 x3  9 x5  15 (max)
 x1  x2  2 x3  7,
 x  6 x  x  1,
3
4
 2
 x  5 x  x  1,
3
5
 2
 x  0, j  1, 5.
 j
9 x1  x2  x3  x4  2 x5  26,

4 x1  3 x2  x4  12,
3 x  2 x  x  6,
2
5
 1
 x  0, j  1, 5.
 j
25. f  2 x1  x2  3x3  2 x4  x5 (max)
 x1  x2  x3  1,

 x1  x2  x4  1,
 x  x  x  2,
5
 1 2
 x  0, j  1, 5.
 j
49
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Практические занятия Тема № 1. Метод Жордана – Гаусса решения системы
линейных уравнений (СЛУ)
Цель занятия – изучение студентами метода Жордана –
Гаусса решения СЛУ при различных вариантах ее решения.
Дидактическая задача: Практическое усвоение студентами
алгоритма решения СЛУ методом Жордана – Гаусса.
Диагностируемые цели:
Студент должен: знать определение решения СЛУ и
понимать, как использовать это определение для проверки
правильности своего решения; уметь записывать СЛУ в таблицу
и восстанавливать СЛУ по таблице; знать определение
равносильности
СЛУ;
формулировать
равносильные
преобразования СЛУ как в форме терминов системы, так и в
форме
терминов
таблицы;
выполнять
равносильные
преобразования СЛУ, записанной как в развернутом виде, так и в
виде таблицы; понимать цель равносильных преобразований для
получения решения СЛУ; знать, чем отличается метод Гаусса
(исключения переменных) от метода Жордана – Гаусса (полного
исключения переменных); понимать, как СЛУ выглядит в
результате преобразований в случае единственного решения, и
уметь записывать ответ; понимать, как СЛУ выглядит в
результате преобразований в случае бесконечного множества
решений, и уметь записывать ответ; понимать, что вид записи
общего решения системы зависит от распределения переменных
на базисные и свободные, что, в свою очередь, зависит от выбора
разрешающего коэффициента, а сам выбор, как правило,
диктуется удобством пересчета коэффициентов СЛУ; уметь
находить частные решения СЛУ; знать и уметь использовать
признак
несовместности
СЛУ;
уметь
конструировать
разрешенные системы с заданным количеством уравнений,
переменных и видом ответа; аккуратно заполнять таблицу; быть
внимательным и терпеливым в вычислениях; понимать, как
выбор разрешающего элемента влияет на трудоемкость
вычислений; видеть за вычислениями в таблице преобразования
СЛУ в развернутом виде
50
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Тема № 2. Базисные и опорные решения системы
линейных уравнений (СЛУ)
Цель занятия – изучение студентами способов поиска всех
базисных и опорных решений СЛУ.
Дидактическая задача: практическое усвоение студентами
алгоритма перехода от одного базисного решения к другому и
перехода от одного опорного решения к другому.
Диагностируемые цели:
Студент должен: знать определение базисного решения
СЛУ; знать требование к выбору разрешающего элемента при
переходе от одного базисного решения к другому; владеть
навыками пересчета таблицы при поиске всех базисных решений
СЛУ; уметь выписывать базисные решения системы из таблицы,
не прибегая к развернутой записи СЛУ; знать определение
опорного решения СЛУ; знать требования к выбору
разрешающего элемента при переходе от одного опорного
решения к другому; владеть навыками пересчета таблицы при
поиске всех опорных решений СЛУ; уметь выписывать опорные
решения системы из таблицы, не прибегая к развернутой записи
СЛУ.
Тема № 3. Графическое решение задачи линейного
программирования (ЗЛП)
Цель занятия – Изучение студентами графического способа
решения ЗЛП и на этом примере знакомство с методологией
получения нового математического знания.
Дидактическая задача: практическое усвоение студентами
графического способа решения ЗЛП.
Диагностируемые цели:
Студент должен: иметь представление о математическом моделировании; строить математическую модель учебной экономической задачи; иметь представление о постановке задачи оптимизации; формулировать ЗЛП; видеть структуру ЗЛП и выделять ее
элементы; знать определение допустимого плана; знать определение допустимого множества; знать определение оптимального
плана; знать требования к ЗЛП, позволяющие решать ее графически; строить допустимое множество; уметь находить координаты вершин допустимого множества; знать определение линии
51
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
уровня функции; знать определение вектора-градиента; уметь
записывать уравнение линии уровня целевой функции ЗЛП и
строить линию ее; уметь записывать координаты вектора-градиента и строить его; знать алгоритм решения ЗЛП графическим способом и уметь его использовать для решения ЗЛП на максимум и
минимум; аккуратно строить чертеж; понимать, какие виды ответов на вопрос ЗЛП возможны; знать уравнение отрезка; грамотно
записывать ответ на вопрос ЗЛП; уметь видоизменять ЗЛП с
целью получения решений разных типов; видеть закономерности,
возникающие при решении ЗЛП с двумя переменными; выдвигать
гипотезы для решения ЗЛП с n переменными;
Тема № 4. Симплекс-метод решения задачи линейного
программирования (ЗЛП)
Цель занятия – изучение студентами симплекс-метода
решения ЗЛП.
Дидактическая задача: практическое усвоение студентами
симплекс-метода решения ЗЛП.
Диагностируемые цели:
Студент должен: знать, каким требованиям должна удовлетворять ЗЛП, чтобы решать ее симплекс-методом; распознавать форму ЗЛП; владеть приемами представления ЗЛП в канонической форме; иметь представление о геометрической интерпретации допустимого множества для ЗЛП с n переменными; знать
алгебраическую интерпретацию угловой точки допустимого
множества; знать алгоритм симплекс-метода и уметь его использовать для решения ЗЛП; понимать смысл оценок для проверки
опорного решения на оптимальность; уметь использовать критерий оптимальности опорного решения для продолжения или завершения решения ЗЛП; грамотно записывать ответ в случае
единственного решения ЗЛП; распознавать случай существования альтернативных решений ЗЛП и грамотно записывать ответ в
этом случае; знать признак неограниченности целевой функции
на допустимом множестве и уметь его распознавать при решении
ЗЛП; грамотно записывать ответ, если ЗЛП не разрешима с указанием причины неразрешимости; аккуратно заполнять симплекстаблицу; внимательно и терпеливо вычислять, доводя решение
ЗЛП до конца.
52
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Темы рефератов. 1. Анализ ЗЛП на чувствительность.
2. Теория двойственности в линейном программировании.
3. Целочисленное программирование.
4. Транспортная задача.
5. Задачи теории игр и линейное программирование.
6. Л. В. Канторович и линейное программирование.
7. Задачи линейной алгебры, при решении которых
используется метод Гаусса.
53
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Литература 1. Акулич, И. Л. Математическое программирование в
примерах и задачах: учеб. пособие для студентов эконом. спец.
вузов / И. Л. Акулич. – М.: Высшая школа, 1986.
2. Белых, А. А. История российских экономико-математических исследований (первые сто лет) / А. А. Белых. – СПб.: издво ЛКИ, 2007.
3. Красс, М. С. Математика для экономического бакалавриата: учебник для вузов / М. С. Красс, Б. П. Чупрынов. – М.:
Дело, 2005.
4. Красс, М. С. Основы математики и ее приложения в экономическом образовании: учебник / М. С. Красс, Б. П. Чупрынов. – М.:
5. Красс, М. С. Математика в экономике. Математические
методы и модели: учебник / М. С. Красс, Б. П. Чупрынов. – М.:
Финансы и статистика, 2007.
6. Кремер, Н. Ш. Исследование операций в экономике: учеб
пособие для вузов / Н. Ш. Кремер и др. / под ред. Н. Ш, Кремера. – М.: ЮНИТИ, 2006.
7. Кремер, Н. Ш. Математика для экономических специальностей. Ч. 1: Учебник. Ч. 2: Задачник / Н. Ш. Кремер; под ред.
Н. Ш. Кремера. – М.: Высшее образование, 2009.
8. Шикин, Е. В. Математические методы и модели в
управлении / Е. В. Шикин, А. Г. Чхартишвили. – М.: Дело, 2000.
9. Кузнецов, Б. Т. Математика: учебник для студентов вузов,
обучающихся по специальностям экономики и управления /
Б. Т. Кузнецов. – М.:ЮНИТИ-ДАНА, 2004.
10. Кузнецов, Б. Т. Математические методы и модели
исследования операций / Б. Т. Кузнецов. – М.: Юнити, 2005.
11. Таха, Х. А. Введение в исследование операций / Х. А. Таха. – М.: Вильямс, 2005.
54
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Оглавление
Линейные уравнения и системы линейных уравнений ......................... 3
Решение системы линейных уравнений .................................................. 4
Метод Гаусса. Метод Жордана – Гаусса ................................................. 6
Переход от одного базисного решения системы к другому ................ 11
Переход от одного опорного решения к другому................................ 13
Постановка задачи линейного программирования.
Основные определения ............................................................... 15
Задача планирования производства ....................................................... 16
Графический метод решения задачи линейного
программирования ...................................................................... 18
Решение задачи линейного программирования симплекс-методом
с графической иллюстрацией ..................................................... 26
Теоретическое обоснование симплекс-метода решения задачи
линейного программирования .................................................... 29
Симплекс-метод решения задачи линейного программирования ...... 31
Контрольные работы ............................................................................... 36
Практические занятия ............................................................................. 50
Тема № 1. Метод Жордана – Гаусса решения системы
линейных уравнений (СЛУ) ....................................................... 50
Тема № 2. Базисные и опорные решения системы
линейных уравнений (СЛУ) ....................................................... 51
Тема № 3. Графическое решение задачи линейного
программирования (ЗЛП) ........................................................... 51
Тема № 4. Симплекс-метод решения задачи линейного
программирования (ЗЛП) ........................................................... 52
Темы рефератов. ...................................................................................... 53
Литература ............................................................................................... 54
55
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Учебное издание
Бестужева Людмила Петровна
Майорова Наталья Львовна
Линейная алгебра Практикум
Редактор, корректор М. В. Никулина
Верстка И. Н. Ианова
Подписано в печать 28.06.2011. Формат 6084 1/16.
Бум. офсетная. Гарнитура "Times New Roman".
Усл. печ. л. 3,25. Уч.-изд. л. 2,36.
Тираж 75 экз. Заказ
.
Оригинал-макет подготовлен
в редакционно-издательском отделе Ярославского
государственного университета им. П. Г. Демидова.
Отпечатано на ризографе.
Ярославский государственный университет им. П. Г. Демидова.
150000, Ярославль, ул. Советская, 14.
56
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
57
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Л. П. Бестужева Н. Л. Майорова Линейная алгебра 58
Документ
Категория
Без категории
Просмотров
84
Размер файла
543 Кб
Теги
линейная, 499, алгебра, бестужевых
1/--страниц
Пожаловаться на содержимое документа