В. Ф. Казак, Е. В. Морозова, И. Э. Симонова

В. Ф. Казак, Е. В. Морозова, И. Э. Симонова

 

Методы

Оптимальных решений

МИНОБРНАУКИ РОССИИ

 ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

КАМЫШИНСКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)

ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО ОБРАЗОВАТЕЛЬНОГО

УЧРЕЖДЕНИЯ ВЫСШЕГО ОБРАЗОВАНИЯ

«ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

 

 

В. Ф. Казак, Е. В. Морозова, И. Э. Симонова

Методы

оптимальных решений

 

 

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

 

Волгоград

2016

УДК

               

 

Рецензенты:

 

 

Печатается по решению редакционно-издательского совета

Волгоградского государственного технического университета

 

Казак, В. Ф.

Методы оптимальных решений: учебно-методическое пособие / В. Ф. Казак, Е. В. Морозова, И.Э. Симонова; ВолгГТУ. – Волгоград, 2016. – 110 с.

 

ISBN

 

Излагается теоретическое обоснование методов математического моделирования (основные понятия, теоремы, алгоритмы) и приводятся примеры их применения.

Предназначено в помощь студентам, изучающим дисциплины «Методы оптимальных решений», «Теория принятия решений» и др..

 

 

Ил.: 28. Табл.: 42.  Библиогр.: 7 назв.

 

 

ISBN                                                          Ó Волгоградский

                                                                      государственный

                                                               технический

                                                               университет, 2016

ОГЛАВЛЕНИЕ

1. Предмет математического программирования. Линейное программирование…………………………………………….....	4
2. Графическое решение задачи линейного программирова-ния…………………………………………….............................	17
3. Симплексный метод решения задач линейного програм-мирования…………………………………………………………	30
4. Двойственность в линейном программировании…………..	47
5. Элементы теории матричных игр……………………………	56
6. Транспортная задача линейного программирования………	74
7. Элементы сетевого планирования…………………………...	94
8. Решение задач линейного программирования с использованием ЭВМ………………………………………………………	102
Список используемой литературы………………………………	109

ПРЕДМЕТ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Построение математических моделей простейших

Экономических задач

1. Задача использования сырья

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

 Рассмотрим задачу на конкретном примере. Для изготовления двух видов продукции Р₁, Р₂ используют три вида сырья S₁, S₂, S₃. Запасы сырья, количество единиц продукции, а также величина прибыли, получаемая oт реализации единицы продукции, приведены в табл. 1.

Таблица 1

Виды сырья	Запас сырья	Количество единиц сырья, идущих на изготовление единицы продукции
		Р1	Р2
S1 S2 S3	20 40 30	2 8 5	5 5 6
Прибыль от единицы продукции, (руб.)		50	40

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

Обозначим через х₁ – количество изготовленных единиц продукции Р₁, х₂ – количе­ство изготовленных единиц продукции Р₂. Тогда, учитывая количество единиц сырья, идущих на изготовление единицы продукции, а также запасы сырья, получим систему ограничений:  (количество сырья, идущего на изготовление продукции, не должно превышать запасы сырья).

Также на х₁ и х₂  должно быть наложено ограничение неотрицатель­ности х₁ ³ 0, х₂ ³ 0. Конечную цель решаемой задачи – получение макси­мальной прибыли при реализации продукции, выразим как функцию цели Z = 50х₁ + 40х₂ (руб.). Числа х₁, х₂ могут быть и дробными, так как в задаче не оговорены условия целочисленности.

 Итак, мы построили ма­тематиче­скую модель задачи использования сырья (ресурсов): найти max значение целевой функции Z = 50 х₁ + 40 х₂ при ограничениях

при условии х1 ³ 0, х2 ³ 0.

Обобщим эту задачу (табл. 2).              

Таблица 2

Виды сырья	Запас сырья	Количество единиц сырья, идущих на изготовление единицы продукции
		Р1	Р2	…	Рn
S1 S2 … Sm	В1 В2 … Вm	a11 a21 … am1	a12 a22 … am2	… … … …	a1n a2n   amn
Прибыль		c1	c2	…	cn

Математическая модель задачи

Пусть дан план = {x₁, x₂, … x_n} где x_j – количество изготовленной единиц   j продукции. Тогда требуется найти целевую функцию Z = c₁x₁ + c₂x₂ + … + c_nx_n при ограничениях (условиях):

2. Задача о смесях.

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

При откорме каждое животное ежедневно должно получить не менее 9 единиц питательного вещества S₁, не менее 8 единиц вещества S₂ и не менее 12 единиц вещества S₃. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в табл. 3.

Таблица 3

Питательные вещества	Количество единиц питательных веществ в 1 кг корма
	Корм 1	Корм 2
S1 = 9 S2 = 8  S3 = 12	3 1 1	1 2 6
Стоимость 1 кг корма (в руб.)	4	6

Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть min.

Для составления математической модели обозначим через x₁, x₂ – количество килограммов корма соответственно 1 и 2 в дневном рационе:

Цель данной задачи – добиться min затрат на дневной рацион, поэтому общую стоимость рациона можно выразить целевой функцией Z = 4x₁ + 6x₂.

Задачу составления рациона можно обобщить, если предусмотреть в рационе т видов питательных веществ в количестве не менее В _i (i = ) и использовать n видов кормов. Обозначим через а _ij − количество единиц i-го питательного вещества, содержащего-ся в единице j-го корма, c _j − стоимость единицы j корма, x _j – количество единиц j-го корма в дневном рационе. Тогда, требуется найти min Z = с₁х₁ + с₂х₂ + … + с_n х_n, при ограничениях:

Помимо этих задач, можно привести примеры задач о раскрое мате­риалов, о размещении заказа, транспортной задачи и т. д.

Симплексные таблицы.

Признак оптимальности опорного плана

Итак, любую задачу линейного программирования можно предста­вить в предпочтительном виде: max(min) Z = ,

                       x_i + , B_i ³ 0, (i = ),

                      х_j ³ 0, (j = ).

Рассмотрим эту задачу для n = 4, m = 2 (и распространим ее для общего случая): Z = c₁x₁ + c₂x₂ + c₃x₃ + c₄x₄.

  

  

 

Выразим базисные переменные (БП) х₁, х₂ через свободные х₃ и х₄

  x₁ = ,

  x₂ =     и подставим их в целевую функцию

Введем обозначения в общем виде:

,

где = (с₁; с₂; …; с_m) – вектор коэффициентов целевой функции при базисных переменных,  = (B₁; B₂;..; B_m) – вектор свободных членов; =  – вектор коэффициентов при переменных х _j.

С учетом этих равенств целевая функция примет вид:

max(min)Z=  где ; .

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

Таблица 17

БП	СБ	В	х1   х2 … xi … xm xm+1   …    xj … xn
			c1   c2 … ci … cm  cm+1   …    cj … cn
x1 x2 . . . xm	c1 c2 . . . cm	B1 B2 . . . Bm	1     0   …   0 … 0 1, m+1   … 1, j … 1n 0     1  …   0 … 0 2, m+1   … 2, j … 2,n ……………………………………………………………..   0     0 … 0 …  1 m, m+1  … m, j … mn
Z j – c j		ΔO	0 …  0 … 0 … 0  Δm+1          Δ j            Δn

Последнюю строку называют индексной строкой, число  – значение целевой функции для начального опорного плана , т. е. Δ_O = Z() = , числа  – называются оценками свободных переменных.

Теорема.

Пусть исходная задача решается на max. Если для некоторого опорного плана все оценки Δ_j (j = ) не отрицательны (больше или равны 0), то такой план оптимален.

Доказательство: Так как Z = Δ_O и Δ_j ³ 0, то Z достигает max, когда = 0, а это возможно, если х_m+1 = 0, х_m+2 = 0,..., хn = 0, т. е. опорный план (В₁, В₂, …, В_m, 0, …, 0) – оптимален.

Теорема.

Если исходная задача решается на min и для некоторого опорного плана все оценки Δ_j (j = ) не положительны (меньше или равны 0), то такой план оптимален.

Пример 9. Решить задачу линейного программирования.

=>

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

Таблица 18

БП	СБ	В	x1	x2	x3	x4	x5
			2	– 1	3	– 2	1
x2	– 1	1,5	0	1	0,5	0	0,5
x4	– 2	2	0	0	1	1	0
x1	2	0,5	1	0	– 0,5	0	0,5
Zj – cj		– 4,5	0	0	– 6,5	0	– 0,5

Заполним индексную строку (Z _j – с _j): ,

Δ_O = – 1 × 1,5 – 2 × 2 + 2 × 0,5 = – 4,5,

Δ₁ = – 1× 0 – 2 × 0 + 2 × 1 – 2 = 0,

Δ₂ = – 1× 1 – 2×0 + 2×0 – (–1) = 0,

Δ₃ = – 1× 0,5 – 2 + 2 × (– 0,5) – 3= – 6,5,

Δ₄ = – 1× 0 – 2×1 + 2×0 – (– 2) = 0,

Δ₅ = – 1× 0,5 – 2 × 0 + 2 × 0,5 – 1 = – 0,5.

Начальный опорный план  = (0,5; 1,5; 0;2; 0), Z () = – 4,5. Так как все оценки индексной строки Δ _j не положительны, а задача на min, то план  – оптимален х* = (0.5: 1.5: 0: 2: 0); Z (х*) = – 4,5.

 

3.3. Переход к нехудшему опорному плану

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

 (i = ),                    (5)

ее начальный опорный план  = (В₁, В₂, …, В_m, 0, …, 0). Значение целевой функции Z() =  = Δ_O.

Рассмотрим задачу на mах: если все Δ _j ³ 0, то опорный план опти­мален. Пусть существует j_O, для которого Δj_O < 0. Вектор столбец , для которого Δj_O < 0, называется разрешающим, а соответствующая пе­ременная x_jo – перспективной. Попытаемся, не изменяя нулевых значений свободных переменных х_m+1, х_m+2, …, х_n, кроме x_jo увеличить значение целевой функции Z за счет увеличения переменной x_jo > 0. Однако увеличивать x_jo надо осторожно, так как выбор  влияет на значения х₁,..., х_m, которые должны быть ³ 0. Имеем: х₁ ³ 0, х₂ ³ 0,..., х_m ³ 0, х_m+1 = 0,..., x_jo-1 = 0, x_jo > 0, x_jo+1 = 0,..., x_n = 0 и из (5) имеем

 x _i = B _I –   – (i = ).                                (6)

При значительном увеличении  может случиться, что для некоторого i соответствующее B _I < , значит получим х_i < 0, что недопустимо. В случае, если  (i = ), такого нарушения не произойдет.

Итак, x_jo можно увеличивать до тех пор, пока B _i – x_jo ³ 0, не на­рушая общности, можно считать > 0, тогда  £ . Найдем среди отношений  наименьшее. Пусть оно называется наименьшим симплексным отношением и обозначается Q.

x_jo = min  =  = Q,

(если это условие выполняется при нескольких i, то в качестве i _O можно выбрать любое) Cтроку  называют разрешающей, элемент  – разрешающим. Переменная , присутствующая в базисе, является неперспективной и ее выводят из базиса:

x_m+1 = 0, …, = 0, = Q,

 = 0, …, x_n = 0, а из равенства (6) находим: x₁ = B₁ – Q, …,

= – Q,  = 0, = – Q, …,

x_m = Q.

Новый базис будет состоять из переменных х₁, , , ,..., x_m, а соответствующий ему опорный план примет вид, X₁ = (B₁ – Q; B₂ – Q; …; – Q; 0; – Q; …; Q; 0; …; Q; 0; …; 0).

В результате преобразований получен новый опорный план , в котором переменная  заменена на , причем Z(X₁) = Δ₀ – Δ_j0Q = Z(X₀) – Δ_j0Q, но Δ_j0 < 0, поэтому Z(X₁) ³ Z(X₀), то есть новый план  не хуже начального .

Практика показывает, что в случае решения задачи на max число шагов уменьшается, если разрешающий столбец выбрать по правилу max (Δ_j £ 0), т. е. в базис вводить переменную, которой соответствует max по абсолютной величине оценки.

В случае задачи на min разрешающий столбец нужно выбирать по правилу mах Δ_j (Δ_j > 0).

Далее процесс повторяется. Проверяем, является ли план  оптимальным, если да, то задача решена. Если нет, то перехо­дим к нехудшему опорному плану  и т. д.

Шаг симплексного метода, позволяющий перейти от одного опорного плана к другому нехудшему, называется итерацией.

Симплексные преобразования нового базиса выполняются по правилу:

1. Элементы строки i _O новой таблицы равны соответствующим элементам разрешающей строки старой таблицы, деленным на разре­шающий элемент: , , (j = ).

2. Элементы разрешающего столбца j₀ новой таблицы равны 0, за исключением = 1.

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

4. По 3 пункту вычисляются и элементы индексной строки.

Для контроля вычислений они могут быть рассчитаны по формулам ,

Пример 10. Найти max Z = 14х₁ – 5х₂ + 2х₃ – х₄ + 8х₅, если

Решение.

Так как задача имеет предпочтительный вид, то занесем ее условия в симплексную табл. 19 (итерация 0).

Таблица 19

N итерации	БП	СБ	В	x1	x2	x3	x4	x5	Симплексные отношения
				14	– 5	2	– 1	8
0	x2	– 5	5	[1]	1	0	0	– 1
	х3	2	41	5	0	1	0	3
	х4	– 1	15	– 5	0	0	1	4
	zj – cj		42	[– 4]	0	0	0	– 1
1	х1	14	5	1	1	0	0	– 1
	х3	2	16	0	– 5	1	0	[8]
	х4	– 1	40	0	5	0	1	– 1
	zj – cj		62	0	4	0	0	[– 5]
2	х1	14	7	1	3/8	1/8	0	0
	Х5	8	2	0	– 5/8	1/8	0	1
	х4	– 1	42	0	35/8	1/8	1	0
	zj – cj		72	0	7/8	5/8	0	0

0 итерация: исходная задача на max, поэтому начальный опорный план . Он неоптимальный, так как Δ₁ < 0, Δ₅ < 0.

                           

1 итерация:

1) выбираем разрешающий элемент из условия: max {|Δ₁|, |Δ₅|} = m a x (4; 1) = 4 – это соответствует 1 столбцу, поэтому его выбираем за разрешающий то есть X₁ будем вводить в базис. Для определения разрешающей строки находим минимальное симплексное отношение:

= =

итак, 1 – строка разрешающая =>элемент а₁₁ = 1 – разрешающий;

2) переменную х₂ выведем из базиса, а х₁ введем в базис;

3) разрешающую строку делим на разрешающий элемент;

4) элементы разрешающего столбца заполняем нулями;

5) остальные элементы пересчитываем по правилу прямоугольника и делим на разрешающий элемент.

Делаем контрольные проверки:

14 – 5 + 2×16 – 1× 40 = 62; 14 – 10 – 5 + 5 = 4;

14 + 0 + 0 – 14 = 0;      0 + 2 + 0 – 2 = 0;

0 + 0 – 1 + 1 = 0;      – 14 + 16 + 1 – 8 = – 5 < 0.

Так как существует отрицательная оценка ∆₅ = – 5, план  = (5; 0; 16; 40; 0) не оптимальный, Z(x₁) = 62 > Z () = 42.

2 итерация:

1) разрешающий столбец 5, переменную. х₅,будем вводить в базис.

2) определяем разрешающую строку: min симплексное отношение  =  = 2 соответствует 2-ой строке, значит переменную х₃ выводим из базиса. Разрешающий элемент а₂₅ = 8;

3) разрешающую строку делим на 8;

4) в разрешающем столбце проставляем нули;

5) остальные элементы пересчитываем;

6) делаем контрольные проверки, так же как и в итерации 1, так как все D_j ³ 0, опорный план  – оптимален

Ответ:  = (7; 0; 0; 42; 2), Z() = 72.

Пример 11. Решить М-задачу линейного программирования:

Найти: min Z = 3x₁ + 2х₂ + 3х₃, если

Решение:

Сведем задачу к каноническому виду и введем искусственные переменные  и :

Занесем условие М-задачи в симплексную таблицу (индексную строку записываем в две строки: в первой – слагаемые без М, во второй – слагаемые с М) (табл. 20).

Таблица 20

№		БП	СБ		В	х1	х2	х3	х4	х5	х6	w1	w2	Q
						3	2	3	0	0	0	M	M
0		х4 w1 w2	0 М М		2 8 1	2 3 0	1 [8] 0	1 2 1	1 0 0	0 – 1 0	0 0 – 1	0 1 0	0 0 1	2/1 = 2 8/8 = [1]
					0	– 3	– 2	– 3	0	0	0	0	0
					9M	3M	[8M]	3M	0	– M	– M	0	0
1	х4 х2 w2			0 2 М	1 1 1	13/8 3/8 0	0 1 0	3/4 1/4 [1]	1 0 0	1/8 – 1/8 0	0 0 – 1	– – –	0 0 1	1/ 1/ 1/1=[1]
					2	– 9/4	0	– 7/2	0	– 1/4	0	–	0
					М	0	0	[M]	0	0	-М	–	0

Окончание табл. 20

2	х4 х2 х3	0 2 3	1/4 3/4 1	13/8 3/8 0	0 1 0	0 0 1	1 0 0	1/8 – 1/8 0	3/4 1/4 – 1	– – –	– – –
			9/2	– 9/4	0	0	0	– 1/4	– 5/2

Примечание: по мере вывода из базиса искусственных переменных соответствующие им столбцы можно опускать.

 

Так как все D_j ≤ 0, то план оптимален,

Ответ:  = (0; 3/4; 1; 1/4; 0; 0), Z() = 9/2.

Замечания:

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

2. Если в индексной строке симплексной таблицы задачи линейного программирования на max содержится отрицательная оценка D_j < 0, а в соответствующем столбце переменной х_j. нет ни одного положительного элемента, то целевая функция на множестве допустимых планов задачи не ограничена сверху.

Если же задача линейного программирования на min и в индексной строке содержится положительная оценка D_j > 0, а в столбце переменной х_j нет ни одного положительного элемента, то на множестве допустимых планов целевая функция не ограничена снизу.

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

а) неполный учет ограничений, которые являются существенными в данной задаче;

б) небрежные оценки параметров, которые участвуют в ограничениях.

 

Задания для самостоятельной работы

Задание 1. Для изготовления двух видов продукции P₁ и P₂ используют три вида сырья (S₁, S₂, S₃).

На изготовление единицы продукции P₁ используют сырье      S₁ – a₁ (ед.), S₂ – a₂ (ед.), S₃ - a₃ (ед.). На изготовление единицы продукции P₂ используют сырье S₁ – b₁ (ед.), S₂ – b₂ (ед.), S₃ – b₃ (ед.). Запасы сырья S₁ составляют не более чем k₁, сырья S₂ – не более чем k₂, сырья S₃ – не более чем k₃.

Прибыль от единицы продукции P₁ составляет a руб., от P₂ составляет b руб.

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

Данные для выполнения задания соответствующего варианта представлены в табл. 21.

Таблица 21

Вар.	A1	a2	a3	b1	b2	b3	k1	k2	k3	a	b
1	2	3	4	2	3	3	305	676	400	5	6
2	9	7	4	5	8	16	143	122	132	3	2
3	2	7	5	3	3	6	576	344	570	4	7
4	6	7	2	3	5	4	421	567	321	5	7
5	2	6	3	10	3	5	900	540	700	4	5
6	2	4	9	4	6	2	720	300	422	3	2
7	4	5	6	2	7	9	279	756	674	6	2
8	3	7	9	2	9	3	279	392	549	4	7
9	2	4	5	6	7	8	320	440	550	3	4
10	5	4	9	2	1	4	422	516	312	5	7
11	3	4	12	9	8	2	550	600	472	2	8
12	2	3	6	7	4	8	330	410	520	3	2
13	5	4	9	2	3	4	212	512	400	4	5
14	6	4	2	6	7	2	715	472	128	7	8
15	7	2	3	2	4	5	572	244	560	2	3
16	2	3	4	2	4	5	672	567	322	3	4
17	2	4	7	2	3	3	572	322	496	3	7
18	2	3	7	5	6	8	219	300	420	5	6
19	4	2	1	8	7	2	500	617	650	4	4
20	3	4	6	2	3	5	200	215	400	6	2
21	2	3	2	3	6	8	428	672	672	3	8
22	4	3	3	3	4	5	440	393	450	6	5
23	4	3	2	4	3	4	480	144	546	2	4
24	2	4	2	2	5	6	520	670	720	5	4

Окончание табл. 21

25	3	4	2	4	5	4	672	344	520	3	2
26	2	3	2	4	6	5	505	212	470	4	3
27	4	5	4	3	4	3	320	318	415	4	5
28	3	3	4	2	2	6	550	312	202	4	3
29	8	6	3	2	3	2	340	680	300	3	4
30	6	4	3	2	3	4	600	520	700	4	7

Заданеи 2. Задана каноническая модель задачи линейного программирования.

Z = CX, AX = A₀, X ³ 0, A = (a_ij)_{3 х 5}.

Требуется найти max Z М- методом.

1.

 

2.

 

3.

 

4.