Тема 1. Линейное программирование

Казанский институт (филиал)

Российского государственного торгово-экономического университета

_______________________________________________________

Кафедра информатики и высшей математики

ТАЛЫЗИН В.А.

МАТЕМАТИКА-3

учебно-методическое пособие

КАЗАНЬ-2004г.

Тема 1. Линейное программирование

Задача 1. Предприятие выпускает два вида продукции А и В, для производства которых используется сырьё трех типов. На изготовление единицы изделия А требуется затратить сырья каждого типа кг соответственно, а для единицы изделия В – кг. Производство обеспеченно сырьем каждого типа в количестве кг соответственно. Стоимость единицы изделия А составляет a руб., а единицы изделия В - b руб. Требуется составить план производства изделий А и В, обеспечивающий максимальную стоимость готовой продукции. Числовые данные параметров приведены в следующей таблице.

a

b

-150

1. Решить задачу симплекс – методом.

2. Сформулировать двойственную задачу и привести её решение.

3. Найти многогранник и интервалы устойчивости двойственных оценок.

4. Оценить стоимость готовой продукции, если запасы сырья каждого типа на производстве изменились на величину кг соответственно.

5. Решить исходную задачу графическим методом.

Решение. 1. Составим математическую модель задачи. Пусть , - количество производимых изделий вида и В соответственно. Тогда на их производство будет израсходовано () сырья 1-го типа. По условию это количество не должно превосходить располагаемого объема этого сырья в количестве 400 единиц, т.е. . Выполняя аналогичные действия с другими типами сырья, окончательно получим систему ограничений:

(1)

которые называются нетривиальными ограничениями задачи.

Количество изделий физически является неотрицательными величинами (нельзя произвести отрицательное количество изделий), что при формализации дает тривиальные ограничения задачи:

. (2)

Целевая функция задачи представляет собой общую стоимость произведенной продукции

, (3)

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

Для решения задачи симплекс–методом приведем задачу (1)-(3) к каноническому виду, введя дополнительные балансовые переменные .Неравенства (1) преобразуются в уравнения путем добавления указанных переменных по одной в каждое неравенство (другими словами, левые части неравенств становятся сбалансированными с правыми частями):

(4)

Физически переменные представляют собой остатки сырья соответственно 1-го, 2-го и 3-го типов, остающиеся неиспользованными при произвольном плане выпуска продукции и В в количестве единиц. Поэтому они также неотрицательны и тривиальная система неравенств в итоге принимает вид:

³ 0, j = . (5)

Введем балансовые переменные в целевую функцию с коэффициентами, равными 0:

.

Перенесем слагаемые с переменными в левую часть полученного выражения и запишем целевую функцию в виде уравнения:

_. (6)

Задача в форме (4)-(6) называется канонической моделью.

Для решения задачи (4)-(6) симплекс-методом необходимо иметь исходный опорныйплан, т.е. базисное решение системы уравнений (4), которое удовлетворяет условиям (5). Для этого все переменные системы надо разделить на две группы – базисные и свободные. Сначала выбирают базисные. Поскольку уравнений всего три, то и базисных переменных будет также три. Переменные могут быть базисными, если матрица коэффициентов при них является невырожденной, т.е. её определитель не равен нулю. В качестве базисных переменных целесообразно выбрать балансовые переменные , каждое из которых входит только в одно уравнение системы (4) и поэтому матрица коэффициентов при них будет единичной, и, стало быть, невырожденной. Остальные переменные ( и ) будут свободными. Если систему (4) разрешить относительно выбранных базисных переменных, то тем самым найдется общее решение системы. Базисное решение получается как частный случай общего решения, когда все свободные переменные в общем решении системы (4) приравниваются нулю. Подставив в (4) , легко получаем значения базисных переменных:

= 400; = 900; = 600,

которые удовлетворяют ограничениям (5). Тем самым найден исходный опорный план, который в векторном виде запишется:

= (0; 0; 400; 900; 600).

Подставив компоненты в целевую функцию (3), получим её значение для этого плана:

=0.

Теперь составим первоначальную симплексную таблицу:

						=200
						=300
						=600
-60	- 40					-

В первых трех строках столбцов таблицы записываются коэффициенты при этих переменных в системе уравнений (4), т.е. основная матрица системы. Столбец таблицы содержит свободные члены системы (4). Нижняя строка таблицы, которая называется индексной строкой, содержит значения коэффициентов при переменных из уравнения целевой функции (6), а в столбце - его правую часть, равную нулю.

Правила заполнения последнего столбца рассмотрим позже.

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

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

Определим эту пару переменных. Сначала определим переменную, которая войдет в число базисных. Это должна быть одна из свободных переменных: или . Выбираем ту переменную, которой в индексной строке соответствует наименьшее отрицательное число (-60, обведено прямоугольником). Значит, переменная становится базисной, а этот столбец таблицы называют разрешающим столбцом.

Теперь определим переменную, “покидающую” число базисных. Это делается с помощью симплексных отношений, вычисляемых для - ой строки () таблицы по формуле (приведенной для выбранного первого разрешающего столбца):

(7)

Вычисленные по формуле (7) значения , () записываются в последнем столбце () симплекс–таблицы. Строка, в которой находится минимальное симплексное отношение, называется разрешающей строкой. В нашем случае это первая строка с симплексным отношением 200. Выбор разрешающей строки по приведенному правилу гарантирует неотрицательность свободных членов при дальнейшем пересчете таблицы и, стало быть, гарантию того, что получаемые базисные решения системы будут опорными планами задачи линейного программирования.

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

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

Теперь приступают к пересчету таблицы. Заполнение новой таблицы начинается с разрешающей строки. Элементы разрешающей строки прежней таблицы делятся на разрешающий элемент (он равен 2) и в результате в разрешающем столбце этой строки будет коэффициент 1 (отсюда её называют нормированной строкой):

	1/2	1/2

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

	1/2	1/2
3-3×1=0	4-3×1/2=5/2	0-3×1/2= -3/2	1-3×0=1	0-3×0=0	900-3×200=300

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

	1/2	1/2
		-3/2
	5/2	-1/2
	-10					-

Произошел переход к новым базисным переменным: . При этом переменные

являются свободными, и в новом опорном плане их значения равны нулю. Значения остальных переменных получаем из нового столбца свободных членов (находятся напротив единиц базисных переменных):

х₁ = 200; х ₄ = 300; х ₅ = 400.

Запишем опорный план в векторной форме:

= (200; 0; 0; 300; 400).

Этому плану соответствует значение целевой функции, равное 12000 (проверьте подстановкой компонент в выражение (3)). В новой таблице это значение зафиксировано в индексной строке в столбце свободных членов.

Как видим, в индексной строке остался один отрицательный элемент, поэтому полученный план также не является оптимальным. Значение (-10) находится в столбце , поэтому переменная станет базисной. Минимальное симплексное отношение (120) достигается напротив коэффициента 1 в строке базисной переменной , которая станет свободной переменной на следующем шаге.

Далее по такой же схеме пересчитываем таблицу первой итерации и получаем таблицу второй итерации:

		4/5	-1/5
		-3/5	2/5
			-1
						-

Аналогично определяем новый опорный план:

= (140; 120; 0; 0; 100).

Ему соответствует значение целевой функции, равное 13200. Поскольку в индексной строке уже нет отрицательных элементов, план является оптимальным:

; =13200.

Итак, задача линейного программирования решена. Возвращаясь к содержательной постановке задачи, можно сказать, что план выпуска, включающий 140 единиц продукции вида и 120 единиц продукции вида , является оптимальным. При этом будет достигнута максимальная стоимость готовой продукции.

2. Рассмотрим исходную задачу (1)-(3). При переходе к двойственной задаче нужно выполнить ряд правил. Во-первых, каждому ограничению (1) исходной задачи соответствует переменная двойственной задачи. Таким образом, здесь будут три двойственные переменные . Во-вторых, нетривиальные ограничения двойственной задачи задаются матрицей, являющейся транспонированной по отношению к матрице ограничений (1), неравенства ограничений типа “ ” превращаются в неравенства типа “ ”, а свободными членами нетривиальных ограничений становятся коэффициенты при соответствующих переменных целевой функции (3). В-третьих, находится минимум, а не максимум целевой функции двойственной задачи и ее коэффициентами становятся свободные члены системы (1). Наконец, двойственные переменные , как и переменные задачи (1)-(3), подчиняются тривиальным условиям неотрицательности. С учетом этих замечаний задача, двойственная задаче (1)-(3), имеет вид:

(8)

, i =1,2,3,(9)

F = 400 y ₁ + 900 y ₂ + 600 y ₃ ® . (10)

Эта задача тоже является задачей линейного программирования и также может быть решена симплекс-методом. Однако обе задачи, прямая и двойственная, тесно связаны между собой, и поэтому, основываясь на теории двойственности, можно, не решая, привести решение второй, если получено решение первой.

Оптимальное решение задачи (8)-(10) находится в индексной строке последней симплекс-таблицы в столбцах, соответствующих первоначальным базисным переменным . Отсюда находим:

= (24; 4; 0).

Таким образом, = 24 > 0, = 4 >0, =0.

Это означает, что при оптимальном производстве данного вида изделий ресурсы первого и второго типов дефицитны ( > 0, > 0), т.е. используется полностью, а третий ресурс используется не полностью, поскольку = 0.

3. Согласно теории линейного программирования, двойственные оценки различных типов сырья (значения ) будут устойчивы к изменению запасов ресурсов, т.е. останутся неизменными, если выполняется условие:

0. (11)

Здесь D ^-1- матрица, состоящая из столбцов первоначальных базисных переменных (т.е. ) последней симплекс-таблицы:

.

Вектор – вектор первоначальных запасов сырья, – вектор изменения запасов сырья. В данном случае:

; .

Сначала определим многогранник устойчивости двойственных оценок.

Запишем неравенство (11):

= 0.

Векторное неравенство преобразуем в систему скалярных неравенств, выписывая их для каждой компоненты вектора:

4/5 (400 + b ₁) – 1/5 (900 + b ₂) ³ 0,

-3/5 (400 + b ₁) + 2/5 (900 + b ₂) ³ 0, (12)

(400 + b ₁) – (900 + b ₂) + (600 + b ₃) ³ 0.

Система неравенств (12) определяет в пространстве переменных многогранник устойчивости двойственных оценок.

Теперь построим интервалы устойчивости по каждому типу ресурса в отдельности. Вначале построим интервал устойчивости для первого типа сырья. Положим =0, = 0. Подставляя это в систему неравенств (12), находим:

4/5 b ₁ - = - 140, или b ₁ - 175,

- 3/5 b ₁ - = - 120, или b ₁ 200,

b ₁ 900 – 400 - 600 = - 100, или b ₁ - 100.

Объединяя эти неравенства, получаем:

- 100 b ₁ 200,

что соответствует следующему интервалу устойчивости по первому ресурсу:

.

Изменение запасов сырья только второго типа ( b ₁ = b ₃ = 0) дает из системы (12) нам следующее:

- 1/5 b ₂ - + = - 140, или b ₂ 700,

2/5 b ₂ - = - 120, или b ₂ - 300,

- b ₂ 900 – 400 - 600 = - 100, или b ₂ 100.

Отсюда получаем неравенство

- 300 b ₂ 100

и интервал устойчивости по второму ресурсу:

.

Аналогично исследуем устойчивость по третьему типу сырья ( b ₁=0, b ₂=0):

b ₃ 900 – 400 – 600 = - 100

или

- 100 Δ b ₃ < ∞.

Отсюда интервал устойчивости: .

Как и следовало ожидать, произвольное увеличение недефицитного сырья третьего типа не изменит его нулевой двойственной оценки.

4. Проверим выполнение неравенства (11) для условий нашей задачи ( ):

= = > 0.

Таким образом, при заданных изменениях запаса сырья двойственные оценки не изменятся. Это означает, что первый и второй виды сырья также будут использованы полностью, поэтому первое и второе неравенства системы (1) с измененными правыми частями можно записать как уравнения:

Получили систему двух уравнений с двумя неизвестными. Решая её, получаем новый оптимальный план:

= 280, = 40.

При этом новая стоимость продукции получается подстановкой этих значений в целевую функцию (3):

Z _нов.max = 60 ∙ 280 + 40 ∙ 40 = 18400.

5. Рассмотрим исходную задачу (1)-(3). Поскольку в ней только две переменные _, , то её можно решить графически на координатной плоскости _. Тривиальные неравенства (2) означают, что решение следует искать в первом квадранте системы координат. Нетривиальные неравенства (1) представляют собой полуплоскости, пересечение которых в пределах первого квадранта образует так называемую область допустимых решений (ОДР) задачи линейного программирования. Оптимальный план представляет собой одну из угловых точек ОДР.

Построим, например, полуплоскость, отвечающую первому неравенству системы (1):

≤ 400.

Эта полуплоскость определяется граничной линией, заданной уравнением:

= 400.

Линию, если она не проходит через начало координат, проще всего построить по двум точкам на осях координат. При = 0 получаем = 400, а при = 0 находим = 200. Соединяем эти две точки прямой линией, получаем две полуплоскости, выше и ниже этой прямой. Отметим эту линию цифрой (1). Исходному неравенству отвечает только одна из указанных полуплоскостей. Она определяется подстановкой в неравенство пробной точки, не

лежащей на граничной прямой. Например, такой точкой может быть начало координат х ₁ = х ₂ = 0. Подставляя в неравенство нулевые значения переменных, получим:

0 £ 400.

Это неравенство является истинным, значит, начало координат принадлежит указанной полуплоскости. В противном случае пробная точка лежит в полуплоскости, не отвечающей исходному неравенству.

400 (1)

Аналогично построим и две другие полуплоскости, получим в итоге ОДР (ее границы обведены жирными линиями):

400 (1)

200

(3)

40 (2)

60 200 400 600

Теперь надо найти угловую точку ОДР, в которой целевая функция достигает максимума. Для этого построим градиент (вектор роста) целевой функции = (60; 40), координаты которого состоят из коэффициентов целевой функции при соответствующих переменных. Градиент указывает направление наискорейшего возрастания целевой функции. Надо найти в ОДР точку, наиболее удаленную от начала координат в этом направлении. Для этого на направление вектора из всех угловых точек ОДР опускаем перпендикуляры. Оптимальному плану соответствует угловая точка, порождающая самый дальний от начала координат перпендикуляр. В нашем случае такая угловая точка образована пересечением границ 1-го и 2-го неравенств:

Решение этой системы даёт оптимальный план задачи:

= 140; = 120.

Заметим, что полученные числа совпадают с решением симплексного метода.

Поиск по сайту: