Казанский институт (филиал)
Российского государственного торгово-экономического университета
_______________________________________________________
кафедра информатики и высшей математики
ТАЛЫЗИН В.А.
МАТЕМАТИКА-3
учебное пособие
КАЗАНЬ-2004г.
Стр.1
Тема 1. Линейное программирование
Задача 1. Предприятие выпускает два вида продукции А и В, для производства которых
используется сырьё трех типов. На изготовление единицы изделия А требуется затратить сырья
каждого типа
11,
12 ,
13
21,
22 ,
23
2 ,
Производство обеспеченно сырьем каждого типа в количестве b b b3 кг соответственно.
Стоимость единицы изделия А составляет руб., а единицы изделия В - руб. Требуется составить
план производства изделий А и В, обеспечивающий максимальную стоимость готовой
продукции. Числовые данные параметров приведены в следующей таблице.
a11
2
a12
3
a13
1
a21
1
a22
4
a23
3
b1
b2
b3
b1
400 900 600 200
b2
b
3
100 -150 60 40
1. Решить задачу симплекс – методом.
2. Сформулировать двойственную задачу и привести её решение.
3. Найти многогранник и интервалы устойчивости двойственных оценок.
4. Оценить стоимость готовой продукции, если запасы сырья каждого типа на производстве
изменились на величину
b b b1,
2,
3 кг соответственно.
5. Решить исходную задачу графическим методом.
Решение. 1. Составим математическую модель задачи. Пусть 1
1
1x2
a a a кг соответственно, а для единицы изделия В – a a a кг.
1 ,
x , 2
x - количество производимых
изделий вида A и В соответственно. Тогда на их производство будет израсходовано
(
2x ) сырья 1-го типа. По условию это количество не должно превосходить располагаемого
объема этого сырья в количестве 400 единиц, т.е. 2x1 2x
действия с другими типами сырья, окончательно получим систему ограничений:
2x1 1x 400,
2
2
3x1 x 900,
1x1 3x 600,
4 2
2
которые называются нетривиальными ограничениями задачи.
Количество изделий
(1)
400 . Выполняя аналогичные
x1, x физически является неотрицательными величинами (нельзя
произвести отрицательное количество изделий), что при формализации дает тривиальные
ограничения задачи:
x1 0,
x 0.
2
Z 60x1 40x ,
(2)
Целевая функция задачи представляет собой общую стоимость произведенной продукции
2
(3)
для которой требуется найти максимальное значение в поставленных ограничениях.
Стр.2
Для решения задачи симплекс–методом приведем задачу (1)-(3) к каноническому виду,
введя дополнительные балансовые переменные x x x5 . Неравенства (1) преобразуются в
3 ,
4 ,
уравнения путем добавления указанных переменных по одной в каждое неравенство (другими
словами, левые части неравенств становятся сбалансированными с правыми частями):
400,
2x1
3x1
1x1
1x2
x4 2
x3 2
3 ,
x3
x4
x5
4 ,
900,
600.
(4)
Физически переменные x x x5 представляют собой остатки сырья соответственно 1го,
2-го и 3-го типов, остающиеся неиспользованными при произвольном плане выпуска продукции
A и В в количестве
2
система неравенств в итоге принимает вид:
j
x 0, j = 5,1 .
Z 60x1 40x2 x x 0x .
0 3
0 4
(5)
Введем балансовые переменные в целевую функцию с коэффициентами, равными 0:
5
Перенесем слагаемые с переменными в левую часть полученного выражения и запишем
целевую функцию в виде уравнения:
Z 60x1 40x2 x x x 0 .
0 3
0 4
0 5
(6)
Задача в форме (4)-(6) называется канонической моделью.
Для решения задачи (4)-(6) симплекс-методом необходимо иметь исходный опорный
план, т.е. базисное решение системы уравнений (4), которое удовлетворяет условиям (5). Для
этого все переменные системы надо разделить на две группы – базисные и свободные. Сначала
выбирают базисные. Поскольку уравнений всего три, то и базисных переменных будет также
три. Переменные могут быть базисными, если матрица коэффициентов при них является невырожденной,
т.е. её определитель не равен нулю. В качестве базисных переменных целесообразно
выбрать балансовые переменные
x x x5 , каждое из которых входит только в одно
3 ,
4 ,
уравнение системы (4) и поэтому матрица коэффициентов при них будет единичной, и, стало
быть, невырожденной. Остальные переменные ( 1
x и 2
x ) будут свободными. Если систему (4)
разрешить относительно выбранных базисных переменных, то тем самым найдется общее решение
системы. Базисное решение получается как частный случай общего решения, когда все
свободные переменные в общем решении системы (4) приравниваются нулю. Подставив в (4)
2 0
x1 x
, легко получаем значения базисных переменных:
3
x = 400;
4
x = 900; 5x = 600,
которые удовлетворяют ограничениям (5). Тем самым найден исходный опорный план, который
в векторном виде запишется:
x1, x единиц. Поэтому они также неотрицательны и тривиальная
Стр.3
x0= ( 0 ; 0 ; 400 ; 900 ; 600 ).
Подставив компоненты 0x в целевую функцию (3), получим её значение для этого плана:
)
Z( 0x =0.
Теперь составим первоначальную симплексную таблицу:
1
x
2
3
1
-60
x2
1
4
3
- 40
x3
1
0
0
0
1
x4
0
1
0
0
5
x5
0
0
1
0
b
400
900
600
0
4 200 =200
9003 =300
6 100 =600
-
В первых трех строках столбцов x x таблицы записываются коэффициенты при этих
переменных в системе уравнений (4), т.е. основная матрица системы. Столбец b таблицы содержит
свободные члены системы (4). Нижняя строка таблицы, которая называется индексной
строкой, содержит значения коэффициентов при переменных из уравнения целевой функции
(6), а в столбце b - его правую часть, равную нулю.
Правила заполнения последнего столбца
рассмотрим позже.
Теперь, когда начальная таблица построена (кроме столбца
), известен соответствующий
опорный план и значения целевой функции, нужно сделать вывод о том, можно ли улучшить
целевую функцию. Ответ на этот вопрос дает содержимое индексной строки: в случае
отсутствия там отрицательных чисел делается вывод о том, что рассматриваемый опорный
план является оптимальным и целевую функцию нельзя увеличить. В противном случае целевую
функцию можно улучшить, т.е. можно получить ее большее значение. Поскольку в данном
случае в индексной строке имеются отрицательные числа, план не является оптимальным
и его можно улучшить.
Переход к новому, лучшему опорному плану называется итерацией симплекс-метода.
Она представляет собой преобразование однократного замещения, поскольку при этом происходит
переход к новому набору базисных переменных: одна из базисных переменных становится
свободной, а в число базисных, наоборот, войдет одна из бывших свободных переменных.
Определим
эту пару переменных. Сначала определим переменную, которая войдет в
число базисных. Это должна быть одна из свободных переменных: x или 2
1
x . Выбираем ту
переменную, которой в индексной строке соответствует наименьшее отрицательное число
Стр.4
(-60, обведено прямоугольником). Значит, переменная 1
x становится базисной, а этот столбец
таблицы называют разрешающим столбцом.
Теперь определим переменную, “покидающую” число базисных. Это делается с помощью
симплексных отношений, вычисляемых для i - ой строки ( i 3,1 ) таблицы по формуле
(приведенной для выбранного первого разрешающего столбца):
i
i
(
a
b
,
i1
в противном
ес aли
i1 0,
Вычисленные по формуле (7) значения i , (i 3,1 ) записываются в последнем столбце
) симплекс–таблицы. Строка, в которой находится минимальное симплексное отношение,
случае.
называется разрешающей строкой. В нашем случае это первая строка с симплексным отношением
1
200. Выбор разрешающей строки по приведенному правилу гарантирует неотрицательность
свободных членов при дальнейшем пересчете таблицы и, стало быть, гарантию того,
что получаемые базисные решения системы будут опорными планами задачи линейного программирования.
Базисная
переменная 3
x , которая имеет в полученной разрешающей строке коэффициент,
равный 1, становится свободной переменной на следующем шаге вычислений.
Элемент таблицы, находящийся на пересечении разрешающего столбца и разрешающей
строки, называется разрешающим элементом таблицы (он выделен овалом).
Теперь приступают к пересчету таблицы. Заполнение новой таблицы начинается с разрешающей
строки. Элементы разрешающей строки прежней таблицы делятся на разрешающий
элемент (он равен 2) и в результате в разрешающем столбце 1
фициент 1 (отсюда её называют нормированной строкой):
1
x
1
x2
12
x3
12
x4
0
x5
0
b
200
x этой строки будет коэф(7)
элементов
столбца
Далее заполняются остальные строки новой таблицы, включая индексную строку (кроме
) так, чтобы получить нули в столбце 1x этих строк. Для этого используют
нормированную разрешающую строку. Из элементов строк прежней таблицы вычитают
соответствующие элементы нормированной разрешающей строки, умноженные на коэффици
Стр.5