ВУЗ:
Составители:
Рубрика:
5
Если в задаче линейного программирования, записанной в кано-
нической форме (2.1) – (2.3), число независимых уравнений m больше
числа неизвестных n , то система (2.1) несовместима; если же m = n , то
система имеет единственное решение. Это решение либо недопустимо,
если хотя бы одно из x
i
, i = 1,2,…,n, отрицательно, либо является иско-
мым оптимальным.
Если же m < n , то система (3) имеет бесконечное множество ре-
шений, в котором n – m переменные могут иметь произвольные значе-
ния (свободные или небазисные переменные), а остальные m перемен-
ные выражаются через них (базисные переменные). Этот последний
случай имеет наибольший практический интерес в линейном програм-
мировании.
Определения. Любой набор переменных х
1
, х
2
, …, х
n
, удовле-
творяющий системе уравнений (2.1), называется решением этой систе-
мы. Если x
j
≥ 0, j = 1,…n, то решение является допустимым. Под бази-
сом понимается набор таких переменных, для которых матрица, состав-
ленная из коэффициентов этих переменных в уравнениях (2.1), будет
невырожденной, т.е. ее определитель не равен нулю. Базисным реше-
нием называется такое решение, которое получается, если все небазис-
ные (свободные) переменные приравнять нулю и решить уравнения (2.1)
относительно базисных переменных. Допустимое решение, удовлетво-
ряющее условию (2.3), называется оптимальным.
Справедливы следующие утверждения:
а) если ограничения (2.1) имеют допустимое решение, то они име-
ют и базисное решение;
б) область допустимых решений является выпуклым множеством
U, т.е для любых точек Р
1
и Р
2
этого множества весь отрезок Р
1
Р
2
со-
держится в множестве U;
в) базисные допустимые решения соответствуют вершинам вы-
пуклого множества;
г) если задача (2.1) – (2.3) разрешима, то минимум целевой функ-
ции (2.3) достигается хотя бы в одной из угловых точек допустимого
множества U этой задачи.
6
3. ПОСТАНОВКА И ГРАФИЧЕСКОЕ РЕШЕНИЕ
ЗАДАЧИ 1
Задача 1. Фирма производит изделия двух видов A
1
и A
2
с по-
мощью последовательной обработки каждой из них в трех цехах. Ис-
ходные данные задачи приведены в таблице 3.1.
Таблица 3.1
Нормы затрат времени
на 1 изделие, час/сут
Названия
цехов
изделие А
1
изделие А
2
Объем
ресурсов,
час/сут
В
1
0,1 0,2 12
В
2
0,2 0,1 10
В
3
0,3 0,3 21
Прибыль на 1
изделие, у.е.
65 80
Определить количества x
j
, j = 1,2 , изделий A
j
, которые не-
обходимо изготовить для достижения максимальной прибыли
F = 65·x
1
+ 80·x
2
, (3.1)
т.е. найти оптимальный план суточного выпуска изделий А
1
и
А
2
. Это типичная задача производственного планирования.
Отметим, что значения x
1
и x
2
не могут быть выбраны про-
извольно, так как существуют ограничения на суточное время
работы в цехах. Эти ограничения записываются в виде:
≤+
≤+
≤+
21 0,3·х 0,3·х
10 0,1·х0,2·х
12 0,2·х 0,1·х
21
21
21
(3.2)
Кроме того значения x
1
и x
2
не могут быть отрицательными:
x
1
≥ 0; x
2
≥ 0; (3.3)
Требуется найти такое неотрицательное решение x
1
, x
2
сис-
темы линейных неравенств (3.2), при котором целевая функция
(3.1) принимает максимальное значение.
3.1. Графический метод решения задачи 1
Сформулированной задаче можно дать графическое реше-
ние. Так как переменные x
1
и x
2
неотрицательны (3.3), то множе-
ство точек (x
1
, x
2
), являющихся возможными решениями задачи,
5 6
Если в задаче линейного программирования, записанной в кано- 3. ПОСТАНОВКА И ГРАФИЧЕСКОЕ РЕШЕНИЕ
нической форме (2.1) – (2.3), число независимых уравнений m больше ЗАДАЧИ 1
числа неизвестных n , то система (2.1) несовместима; если же m = n , то Задача 1. Фирма производит изделия двух видов A1 и A2 с по-
система имеет единственное решение. Это решение либо недопустимо, мощью последовательной обработки каждой из них в трех цехах. Ис-
если хотя бы одно из xi , i = 1,2,…,n, отрицательно, либо является иско- ходные данные задачи приведены в таблице 3.1.
мым оптимальным. Таблица 3.1
Если же m < n , то система (3) имеет бесконечное множество ре- Названия Нормы затрат времени Объем
шений, в котором n – m переменные могут иметь произвольные значе- цехов на 1 изделие, час/сут ресурсов,
ния (свободные или небазисные переменные), а остальные m перемен- изделие А1 изделие А2 час/сут
ные выражаются через них (базисные переменные). Этот последний В1 0,1 0,2 12
случай имеет наибольший практический интерес в линейном програм- В2 0,2 0,1 10
мировании. В3 0,3 0,3 21
Определения. Любой набор переменных х1, х2, …, хn , удовле- Прибыль на 1 65 80
творяющий системе уравнений (2.1), называется решением этой систе- изделие, у.е.
мы. Если xj ≥ 0, j = 1,…n, то решение является допустимым. Под бази- Определить количества xj , j = 1,2 , изделий Aj , которые не-
сом понимается набор таких переменных, для которых матрица, состав- обходимо изготовить для достижения максимальной прибыли
ленная из коэффициентов этих переменных в уравнениях (2.1), будет F = 65·x1 + 80·x2, (3.1)
невырожденной, т.е. ее определитель не равен нулю. Базисным реше- т.е. найти оптимальный план суточного выпуска изделий А1 и
нием называется такое решение, которое получается, если все небазис- А2. Это типичная задача производственного планирования.
ные (свободные) переменные приравнять нулю и решить уравнения (2.1) Отметим, что значения x1 и x2 не могут быть выбраны про-
относительно базисных переменных. Допустимое решение, удовлетво- извольно, так как существуют ограничения на суточное время
ряющее условию (2.3), называется оптимальным. работы в цехах. Эти ограничения записываются в виде:
Справедливы следующие утверждения:
а) если ограничения (2.1) имеют допустимое решение, то они име-
0,1·х1 + 0,2·х 2 ≤ 12
(3.2)
ют и базисное решение; 0,2·х1 + 0,1·х 2 ≤ 10
б) область допустимых решений является выпуклым множеством 0,3·х + 0,3·х ≤ 21
U, т.е для любых точек Р1 и Р2 этого множества весь отрезок Р1Р2 со- 1 2
держится в множестве U; Кроме того значения x1 и x2 не могут быть отрицательными:
в) базисные допустимые решения соответствуют вершинам вы- x1 ≥ 0; x2 ≥ 0; (3.3)
пуклого множества; Требуется найти такое неотрицательное решение x1, x2 сис-
г) если задача (2.1) – (2.3) разрешима, то минимум целевой функ- темы линейных неравенств (3.2), при котором целевая функция
ции (2.3) достигается хотя бы в одной из угловых точек допустимого (3.1) принимает максимальное значение.
множества U этой задачи.
3.1. Графический метод решения задачи 1
Сформулированной задаче можно дать графическое реше-
ние. Так как переменные x1 и x2 неотрицательны (3.3), то множе-
ство точек (x1, x2), являющихся возможными решениями задачи,
