Задача 1. Производственная задача

Предприятие производит продукцию двух видов А и В, для производства которых используется сырье трех видов. На изготовление единицы изделия А требуется затратить сырья каждого вида 16, 8 и 5 кг соответственно, а для единицы изделия В – 4, 7 и 9 кг. Производство обеспечено сырьем каждого вида в количестве 784 кг, 552 кг и 567 кг соответственно.

Стоимость единицы изделия А составляет 4 руб., единицы изделия В – 6 руб. Требуется составить план производства изделий А и В, обеспечивающий максимальную стоимость готовой продукции. Решить исходную задачу геометрически.

Решение. Дадим математическую постановку задачи.

Пусть продукции А производится x ₁ единиц, а продукции В – x ₂единиц. Стоимость всех изделий А составит 4 х ₁ рублей, изделий В –6 х ₂рублей, суммарная стоимость произведенной продукции:

Z = 4 x ₁ + 6 x ₂.

Требуется затратить 16 x ₁ кг – количество сырья первого вида, идущего на изготовление всех изделий вида A; 4 x ₂ – количество сырья первого вида, идущего на изготовление всех изделий вида B.

Получим ограничение по сырью первого вида:

16 x ₁ + 4 x ₂ £ 784.

Аналогично определяем ограничение по сырью 2 вида:

8 x ₁ + 7 x ₂ £ 552,

и ограничение по сырью 3 вида:

5 x ₁ + 9 x ₂ £ 567.

Количество выпускаемых изделий не может быть отрицательным. Следовательно, получаем условие неотрицательности решения: x ₁ ³ 0, x ₂ ³ 0.

Таким образом, получили задачу линейного программирования:

Требуется максимизировать функцию стоимости готовой продукции:

Z = 4 x ₁ + 6 x ₂ max

при ограничениях:

Решим задачу графически.

Так как переменные x ₁, x ₂ неотрицательны, то допустимые решения лежат в первом координатном углу.

Для построения области допустимых решений (ОДР) для каждого ограничения строят прямую, соответствующую равенству.

Первому условию в системе ограничений соответствует равенство:

16 x ₁ + 4 x ₂ = 784.

Построим эту прямую по точкам:

x 1
x 2

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

Если прямая не проходит через начало координат, то в качестве произвольно выбранной точки удобно брать начало координат, то есть точку О (0, 0).

Для нашего случая возьмем начало координат О (0; 0) и, поставив ее координаты в неравенство, получим:

16×0 + 4×0 < 784.

Имеем верное равенство. Следовательно, полуплоскость, которой принадлежит точка О (0, 0) и есть геометрическое решение неравенства. Решением первого неравенства системы является полуплоскость, лежащая ниже прямой 16 x ₁ + 4 x ₂= 784. Таким же образом найдем решения каждого неравенства системы (рис. 1).

Решением системы неравенств будет пересечение всех полуплоскостей. Это пересечение есть выпуклое множество, называемое областью допустимых решений(ОДР).

В общем случае, ОДР может быть замкнутым выпуклым многоугольником, незамкнутым или пустым.

Для нахождения оптимального решения, то есть такого, при котором целевая функция принимает свое максимальное (минимальное) значение, дадим целевой функции Z произвольное численное значение, то есть положим Z = С (стоимость постоянная).

Множество точек 4 x ₁ + 6 x ₂ = С определяет прямую, называемой линией уровня функции цели Z (x ₁, x ₂). При различных значениях С получаем семейство линий уровня – параллельных прямых с одним и тем же нормальным вектором . С увеличением Z они будут передвигаться в одну сторону, с уменьшением – в противоположную.

Интерес представляют линии уровня, имеющие общие точки с ОДР. При С = 0 общая стоимость равна нулю. Так как коэффициенты функции цели Z положительны, ее значение увеличивается при движении прямых от линии уровня, проходящей через точку O (0,0), в направлении вектора . Крайняя прямая из семейства параллельных прямых имеет с многоугольником решений общую точку А.

Координатами нормального вектора являются коэффициенты при текущих координатах в уравнении прямой Z, то есть (4; 6). Поэтому для определения оптимального плана на графике достаточно построить нормальный вектор (4; 6), провести прямую, перпендикулярную через крайнюю точку ОДР (рис.1), то есть точку, в которой прямая Z касается ОДР.

 

Рис.1. Геометрическое решение задачи линейного программирования

 

Из рисунка видно, что точкой, в которой прямая Z касается ОДР является точка А. Находим ее координаты, решая систему уравнений:

Получим x ₁ = 27, x ₂= 48, то есть точка А имеет координаты (27; 48).

Максимальный доход составляет Z_max = 4∙27 + 6∙48 = 396руб.

Ответ. Для получения максимальной стоимости изделий Z = 396 рублей необходимо изготовить изделий А x ₁ = 27 единиц, изделий В x ₂ = 48 единиц.

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

1. Если оптимальное решение существует, то оно лежит на границе ОДР.

2. Если решение единственное, то оно достигается в одной из вершин ОДР.

3. Если решений множество, то они достигаются на одной из сторон выпуклого многоугольника ОДР.

4. Решение, лежащее в одной из вершин ОДР, является опорным решением, а сама вершина – опорной точкой.

5. Для того, чтобы найти опорное решение достаточно перебрать все вершины ОДР (опорные точки) и выбрать ту, где целевая функция достигает максимума (минимума).

 

Симплексный метод

 

Алгебраический метод решения (симплекс-метод) разработан американским математиком Д. Данцигом и опубликован в 1951 году. В его основе лежит использование элементарных преобразований матрицы ограничений канонической задачи линейного программирования (метод Жордана-Гаусса).

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

, (5)

которые удовлетворяют системе линейных уравнений:

(6)

и дают экстремум функции цели:

max (min) (7)

Правомерность перехода от общей задачи к задаче в канонической форме основывается на теореме: неотрицательное решение системы неравенств (2) является решением системы уравнений (6). Справедливо и обратное утверждение.

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

Справедливы теоремы.

Теорема 1. Если для некоторого фиксированного индекса j выполняется условие Z_j – c_j > 0, то можно построить хотя бы один опорный план, для которого значение целевой функции Z будет меньше первоначального, то есть Z < Z₀.

Теорема 2. Если для некоторого опорного плана` x выполняется соотношение Z<sub>j</sub> – c<sub>j</sub> £ 0, то план` x является оптимальным.

Сформулируем алгоритм симплексного метода.

По условию задачи составляется экономико-математическая модель задачи в общем виде:

Z (x ₁, ..., x_n) = c ₁ x ₁ +...+c_nx_n max

x_j 0, (j = 1,…, n)

Переходят от задачи на максимум к задаче на минимум Z. Для этого целевую функцию умножают на (–1).

– Z(x ₁,..., x_n) = – c ₁ x ₁– ... – c_nx_n min.

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

x_j 0,(j = 1, …, n+m).

Запишем систему ограничений в векторной форме:

или

.

 

Составляется первая симплексная таблица:

Таблица 1

Базис	C	b	-c1	-c2	…	-cn	cn+ 1=0	…	cn+m =0
a 1	a 2	…	an	an+ 1	…	an+m
an+ 1	cn+ 1 = 0	b 1	a 11	a 12	…	a 1 n		…
an+ 2	cn+ 2 = 0	b 2	a 21	a 22	…	a 2 n		…
…	…	…	…	…	…	…	…	…	…
an+m	cn+m= 0	bm	am 1	am 2	…	amn		…
Zj-cj	Z0	c 1	c 2	…	cn		…

Столбец «Базис» – столбец векторов, входящих в базис.

Столбец «C» – столбец коэффициентов, стоящих в целевой функции при векторах базиса.

Строка «Z_j – c_j» – называется индексной строкой.

Столбец «b» – столбец ограничений по ресурсам, входящих в базис.

Столбцы a ₁ … a_m, …, a_{m+ 1}, …, a_n – это коэффициенты, стоящие при неизвестных в системе ограничений.

Заполним индексную строку «Z_j – c_j». Для столбца «b» это значение равно сумме попарных произведений элементов столбца «C» на элементы столбца «b», т. е.

.

Решение находится в столбце «b»:

=(b ₁, b ₂, …, b_m,0,…, 0); Z = Z₀..

Две верхние строки таблицы содержат коэффициенты функции цели и n+m векторов системы ограничений.

Просматриваются числа Z_j – c_j индексной строки.

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

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

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

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

, (8)

a_ij – разрешающий элемент матрицы, a_ij 0.

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

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

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

Если же решение не оптимальное, то процесс преобразования симплексной таблицы повторяется. Симплексный метод повторяют до тех пор, пока не будет найдено базисное решение.

 

4.1. Решение производственной задачи
симплексным методом

Требуется найти максимум функции доходов:

Z = 4 x ₁ + 6 x ₂ max

при ограничениях:

 

Сведем задачу на максимум к задаче на минимум. Для этого умножим функцию цели на (–1).

– Z = –4 x ₁ – 6 x ₂ min.

Для приведения задачи к каноническому виду (с ограничениями-равенствами), пригодному к решению симплекс-методом, вводим дополнительные неотрицательные переменные x ₃, x ₄, x ₅ 0.

Имеем:

– Z = –4 x ₁ – 6 x ₂ + 0 х ₃ + 0 х ₄ + 0 х ₅ min

В производственной задаче дополнительные переменные x ₃, x ₄, x ₅ означают количество неиспользованного сырья (остаток) соответственно первого, второго и третьего вида.

Запишем задачу в векторной форме:

– Z = –4 x ₁ – 6 x ₂ + 0 х ₃ + 0 х ₄ + 0 х ₅ min

.

Составим первую симплекс-таблицу (таблица 2).

Коэффициенты при дополнительных переменных x ₃, x ₄, x ₅ образуют единичную матрицу. Принимаем вектора коэффициентов при x ₃, x ₄, x ₅ за базис, то есть в столбец «Базис» записываем вектора .

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

В столбец b поставим ограничения по ресурсам. Коэффициенты в столбцах а ₁, а ₂, …а ₅ – это коэффициенты, соответствующие переменным х ₁, х ₂,… х ₅ в системе ограничений, записанной в векторной форме.

Последняя строка называется индексной. Ее заполняют следующим образом. Находят сумму попарных произведений столбца b на С, затем вычитают соответствующий коэффициент при целевой функции.

Столбец b: Z ₀=0×784 + 0×552 + 0×567 = 0.

Столбец а ₁: Z ₁ – c ₁ = 0×16 + 0×8 + 0×5 – (– 4) = 4.

Столбец а ₂: Z ₂ – c ₂ = 0×4 +0×7 + 0×6 – (– 6) = 6.

Столбец а ₃: Z ₃ – c ₃ = 0×1 +0×0 + 0×0 – 0 = 0

Столбец а ₄: Z ₄ – c ₄ = 0×0 + 0×1 + 0×0 – 0 = 0

Столбец а ₅: Z ₅ – c ₅ = 0×0 + 0×0 + 0×1– 0 = 0

Полученные значения записываем в индексную строку таблицы 2.

Таблица 2

Базис	C	b	с 1 =– 4	с 2 =– 6	с 3 = 0	с 4 = 0	с 5 = 0
`a 1	`a 2	`a 3	`a 4	`a 5
`a 3	с 3 =0
`a 4	с 4 =0
`a 5	с 5 =0
Zj - Cj

Первое базисное решение находится в столбце b: x ₁ = 0; x ₂ = 0; x ₃ = 784; x ₄ = 552; x ₅ = 567. При этом Z = 0. В индексной строке имеются положительные числа 4, 6. Следовательно, план не оптимальный.

Применяем алгоритм симплексного метода.

1. Выбираем максимальный по абсолютной величине элемент, стоящий в индексной строке. Этот элемент равен 6. Ему соответствует столбец а ₂. Этот столбец будем называть направляющим. Выделим его в симплексной таблице.

2. Выбираем направляющую строку. Для этого делим элементы столбца b на соответствующие числа направляющего столбца и находим минимальное частное, то есть

.

Минимальное частное соответствует третьей строке. Таким образом, направляющей строкой будет строка а ₅. Выделим ее.

Если в направляющем столбце стоят нули или отрицательные числа, то соответствующие строки не рассматриваются. Если все элементы столбца меньше или равны нулю, то нельзя выбрать направляющую строку и найти оптимальное решение.

3. Элемент, стоящий на пересечении направляющей строки и направляющего столбца называется разрешающим. В данном случае он равен 9.

4. Строим вторую симплексную таблицу. Для этого переменную, соответствующую разрешающему столбцу а ₂ введем в базис на место переменной а ₅.

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

(63; 5/9; 1; 0; 0; 1/9).

6. Элементы направляющего столбца, кроме разрешающего, равного теперь единице, заменяем нулями. Результат вносим в соответствующий столбец новой таблицы.

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

строка а₃:

; ; ; ; .

строка а ₄:

; ; ; ; .

индексная строка:

; ; ; ; .

Полученные значения записываем на соответствующие места таблицы 3.

Таблица 3

Базис	C	b	с 1 =– 4	с 2 =– 6	с 3 = 0	с 4 = 0	с 5 = 0
`a 1	`a 2	`a 3	`a 4	`a 5
a 3			124/9				-4/9
a 4			37/9				-7/9
a 2	-6		5/9				1/9
Zj-Cj	-378	2/3				-2/3

 

Получили второе базисное решение: x ₁ = 0; x ₂ = 63; x ₃ = 532; x ₄ = 111; x ₅ = 0и– Z ₂ = –378(значение –378 находится на пересечении индексной строки и столбца из свободных членов). Это решение не оптимально, так как в индексной строке имеется положительное число 2/3.

Повторяем процедуру симплексного метода.

Выбираем направляющий столбец (положительное число в индексной строке соответствует а ₁). Вводим в базис вектор а ₁ в новой симплекс-таблице.

 

Выбираем направляющую строку, то есть находим:

.

Направляющей строкой будет строка а₄. Разрешающий элемент 37/9.

Составим третью симплекс-таблицу (табл.4).

Таблица 4.

	Базис	C	b	с 1 =– 4	с 2 =– 6	с 3 = 0	с 4 = 0	с 5 = 0
	`a 1	`a 2	`a 3	`a 4	`a 5
	a 3						-124/37	80/37
	a 1	-4					9/37	-7/37
	a 2	-6					-7/37	8/37
	Zj-Cj	-396				-6/37	-20/37

 

Получили третье базисное решение: x ₁ = 27; x ₂ = 48; x ₃ = 16; x ₄ = 0; x ₅ = 0; -Z=- 396.

В индексной строке нет положительных чисел. Решение оптимальное.

Вывод. Для получения максимальной стоимости готовой продукции Z_max =396 руб. необходимо изготовить 27 единиц продукции вида A и 48 единиц продукции вида В. При этом сырье первого вида останется неизрасходованным в количестве x ₃ = 16 кг, а сырье второго и третьего вида будет израсходовано полностью x ₄ = 0; x ₅ = 0.

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

 

Транспортная задача

Транспортная задача является специальной задачей линейного программирования.

Имеется m баз (пунктов отправления) A ₁, A ₂,..., A _m, в которых сосредоточены запасы однородного груза в количествах соответственно. Груз необходимо перевезти n потребителям (магазинам) B ₁, B ₂,..., B _n в количествах соответственно. Известна стоимость перевозки единицы груза с базы A_i (i= 1,2,…, m) потребителю B_j (j= 1,2,…, n). Требуется спланировать перевозки грузов так, чтобы их общая стоимость была минимальная.

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

. (9)

Рассмотрим закрытую модель транспортной задачи с матрицей перевозок, заданной в таблице 5.

Таблица 5

Базы	Потребители	Запасы (ai)
B 1	B 2	.................	B n
A 1	c 11	c 12	..................	c 1 n	a 1
A 2	c 21	c 22	..................	c 2 n	a 2
................	..............	.................	..................	.........	...................
A m	cm 1	cm 2	...................	cmn	am
Потребности (bj)	b 1	b 2	.................	bm

5.1. Математическая модель и анализ
транспортной задачи

 

Обозначим x_ij – величина груза, перевозимого с базы A_i (i= 1,2,…, m) потребителю B_j (j= 1,2,…, n).

Так как стоимости перевозок c_ij (тарифы) известны, запишем функцию общих затрат на перевозку:

min. (10)

Величина перевозимых грузов не может быть отрицательна:

(i= 1,2,…, m)(j= 1,2,…, n). (11)

Если задача с выполненным балансом, то есть выполняется условие (9), то количество вывозимого с i -ой базы груза должно совпадать с запасами на этой базе:

, (12)

количество груза, перевозимого j -ому потребителю, должно совпадать с его потребностями

. (13)

Математическая модель задачи: требуется минимизировать функцию затрат (функцию цели) Z:

min (14)

При наличии ограничений:

(15)

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

1. Все коэффициенты в системе ограничений равны единице.

2. Не все m + n уравнений являются независимыми. В силу условия одно из ограничений можно исключить и тогда для общего числа m´n переменных будет m + n –1 ограничений. То есть опорный план должен содержать не более m + n –1 компонент. В этом случае план называется невырожденным. В случае вырожденного опорного плана число компонент будет меньше, чем m + n –1. Если план оказывается вырожденным, то в клетку следует ввести пустую поставку (груз, равный 0) и считать ее заполненной.

При решении транспортной задачи выделяются следующие шаги:

1. Составление начального плана перевозок.

2. Проверка плана на оптимальность и его пошаговое улучшение.