Решение задач линейной оптимизации с использованием MathCad и Excel: Методическое пособие и контрольные задания

2

Федеральное агентство по образованию Восточно-Сибирский государственный технологический университет

В.В. Бундаев РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОЙ ОПТИМИЗАЦИИ С ИСПОЛЬЗОВАНИЕМ MATHCAD и EXCEL Методическое пособие и контрольные задания для студентов всех специальностей дневной и заочной форм обучения

Улан-Удэ 2006

Бундаев В.В. Решение задач линейной оптимизации с использованием Mathcad и Excel. Методическое пособие и контрольные задания для студентов всех специальностей дневной и заочной форм обучения. Улан-Удэ: Изд-во ВСГТУ, 2006. – 30 с., ил. Методы линейного программирования получили широкое распространение при решении практических задач, связанных с составлением производственных планов, графиков обслуживания потребителей, оптимальным распределением ресурсов, транспортных потоков, размещением оборудования, с составлением различного рода смесей и т.д. Методическое пособие содержит необходимые теоретические сведения и практический материал для решения задач линейного программирования с использованием возможностей математического пакета Mathcad и табличного процессора Excel. На конкретных типовых примерах подробно разобраны порядок выполнения лабораторных работ по линейной оптимизации. В целях закрепления пройденного материала в конце пособия предлагаются индивидуальные задания для самостоятельного выполнения. Предполагается, что студент уже знаком с основами работы с пакетами прикладных программ Mathcad и Excel. Работа предназначена для студентов всех специальностей вузов, продолжающих изучение возможностей использования современных компьютерных технологий для решения вычислительных задач, предусмотренных требованиями ГОСВО. Методика решения таких задач может быть использована студентамистаршекурсниками для проведения различного рода линейных оптимизационных расчетов, а также при выполнении НИРС, курсовом и дипломном проектировании. Рецензент: Баргуев С.Г., к.ф.-м.н., доцент кафедра «Прикладная математика» ВСГТУ

3

4

r

1. ФОРМУЛИРОВКА ОБЩЕЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Пусть в m-мерном векторном пространстве Еm необходимо

r

выбрать такой вектор X = {x1 , x 2 ,..., x m } , который удовлетворяет следующим ограничениям:

ai1 ·х1 + ai 2 ·х 2 + ... + aim ⋅ x m ≤ b i ,  a k1 ·х1 + a k 2 ·х 2 + ... + a km ⋅ x m = b k , a ·х + a ·х + ... + a ⋅ x ≥ b , i ≠ k ≠ p 2 p p2 pm m  p1 1 x j ≥ 0, j = 1,2,..., m; bi ≥ 0, bk ≥ 0, b p ≥ 0

(1.1)

производные ни в какой точке X ∈ U не равны нулю. Отметим

r

также, что минимум F ( X ) всегда достигается либо в вершинах многоугольника (многогранника) допустимых решений, либо на его границе. 2. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В КАНОНИЧЕСКОЙ ФОРМЕ Вводя дополнительные переменные xm+q ≥ 0, q = 1,2,…n-m все ограничения-неравенства можно записать в виде равенств. Следовательно, любая задача линейного программирования может быть записана в каноническом виде:

 a11 x1 + a12 x 2 + ⋅ ⋅ ⋅ + a1n x n = b1  a x + a x + ⋅⋅⋅ + a x = b  21 1 22 2 2n n 2  ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅  a m1 x1 + a m 2 x 2 + ⋅ ⋅ ⋅ + a mn x n = bm x j ≥ 0; bi ≥ 0; i = 1,..., m; j = 1,...n n r F ( X ) = ∑ c j x j → min,

для которого достигается минимум линейной функции, т.е. F(x1,x2,…,xm) = c1·x1 + c2·x2+…+ cm·xm, (1.2) и определить значение этого минимума. Отметим, что если в конкретной задаче требуется отыскание не минимума, а максимума функции F(x1,x2,…,xm), то эту задачу можно превратить в задачу на поиск минимума, поменяв знак целевой функции на обратный, т.е.

{

}

r r max − F(X ) r r F ( X ) = min X

X

Также заметим, что ограничения (1.1), так же как и функция (1.2), являются линейными. Таким образом, приведенные соотношения (1.1)-(1.2) можно считать общей формой записи задачи линейного программирования. При этом функцию F(x1,x2,…,xm) называют целевой

r функцией, а множество точек X ∈ U , на котором ищется ми-

нимум этой функции – множеством допустимых решений. Это множество описывается системой ограничений (1.1) и представляет собой выпуклый многоугольник или многогранник. Решение поставленной задачи (1.1)-(1.2) на нахождение экстремума с помощью обычного способа приравнивания нулю производной целевой функции (1.2) и решения системы полу-

r

ченных уравнений непригодны ввиду линейности F ( X ) , т.е. ее

r

j =1

(2.1)

(2.2) (2.3)

где X = ( x1 , x 2 ,..., x n ) - вектор неизвестных в пространстве En;

r C = (c1 , c 2 ,..., c n ) - вектор коэффициентов целевой функции

(2.3); A = (aij) – прямоугольная матрица коэффициентов системы уравнений (2.1), размерность m×n; m - число уравнений, n – число неизвестных в системе (2.1).

r B = (b1 , b2 ,..., bm ) - вектор правых частей системы уравнений

(2.1); Можно показать, что всякому решению системы ограничений (1.1) соответствует определенное решение системы линейных уравнений (2.1), у которого те же самые значения основных переменных х1, х2,…,хm.

5

6

Если в задаче линейного программирования, записанной в канонической форме (2.1) – (2.3), число независимых уравнений m больше числа неизвестных n , то система (2.1) несовместима; если же m = n , то система имеет единственное решение. Это решение либо недопустимо, если хотя бы одно из xi , i = 1,2,…,n, отрицательно, либо является искомым оптимальным. Если же m < n , то система (3) имеет бесконечное множество решений, в котором n – m переменные могут иметь произвольные значения (свободные или небазисные переменные), а остальные m переменные выражаются через них (базисные переменные). Этот последний случай имеет наибольший практический интерес в линейном программировании. Определения. Любой набор переменных х1, х2, …, хn , удовлетворяющий системе уравнений (2.1), называется решением этой системы. Если xj ≥ 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 этой задачи.

3. ПОСТАНОВКА И ГРАФИЧЕСКОЕ РЕШЕНИЕ ЗАДАЧИ 1 Задача 1. Фирма производит изделия двух видов A1 и A2 с помощью последовательной обработки каждой из них в трех цехах. Исходные данные задачи приведены в таблице 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 изделие, у.е. Определить количества xj , j = 1,2 , изделий Aj , которые необходимо изготовить для достижения максимальной прибыли F = 65·x1 + 80·x2, (3.1) т.е. найти оптимальный план суточного выпуска изделий А1 и А2. Это типичная задача производственного планирования. Отметим, что значения x1 и x2 не могут быть выбраны произвольно, так как существуют ограничения на суточное время работы в цехах. Эти ограничения записываются в виде:

0,1·х1 + 0,2·х 2 ≤ 12  0,2·х1 + 0,1·х 2 ≤ 10 0,3·х + 0,3·х ≤ 21 1 2 

(3.2)

Кроме того значения x1 и x2 не могут быть отрицательными: x1 ≥ 0; x2 ≥ 0; (3.3) Требуется найти такое неотрицательное решение x1, x2 системы линейных неравенств (3.2), при котором целевая функция (3.1) принимает максимальное значение. 3.1. Графический метод решения задачи 1 Сформулированной задаче можно дать графическое решение. Так как переменные x1 и x2 неотрицательны (3.3), то множество точек (x1, x2), являющихся возможными решениями задачи,

7

8

лежит в первом квадранте плоскости х1ох2 (рис.3.1). Если в первом неравенстве системы (3.2) заменить знак « ≤ » на знак « = », то получим уравнение прямой линии 0,1·х1 + 0,2·х 2 = 12 . Эта прямая (прямая 1) делит плоскость х1ох2 на две полуплоскости так, что для одной из них выполнено неравенство 0,1·х1 + 0,2·х 2 > 12 , а для другой - 0,1·х1 + 0,2·х 2 < 12 . Непосредственной подстановкой точки (0,0) в левую часть уравнения прямой убеждаемся в том, что начало координат лежит в полуплоскости, удовлетворяющей требуемому ограничению 0,1·х1 + 0,2·х 2 ≤ 12 , т.е. допустимой для этого ограничения является полуплоскость, содержащая точку (0,0). Точно также определим полуплоскости для остальных ограничений системы (3.2) (прямые 2 и 3). В результате получим выпуклый многоугольник ОАВСД, который называется областью допустимых решений системы (3.2) (см. рис.3.1).

Любая точка (x1, x2), лежащая в этом многоугольнике, определяет количество изделий А1 и А2 , обеспечивающих необходимые суточные затраты времени в цехах В1, В2 и В3. Из множества этих точек надо выбрать такую, в которой целевая функция F (3.1) достигает своего максимального значения. Для некоторого фиксированного значения F* линейная функция F = 65·x1 + 80·x2 представляет собой прямую линию. Задаваясь различными значениями F* (например, 0,1,2 и т.д.), получим семейство параллельных прямых – линий уровня функции F. Увеличению значений F соответствует перемещение указанной прямой параллельно самой себе вверх по направлению вектора

Рис.3.1

 ∂F   ∂x  65  1=   ∂F  80  ∂x 2  Из рис.3.1 видно, что максимальное значение функции F на допустимом множестве точек OABCD соответствует прямой, проходящей через точку В пересечения прямых 0,1·x1 + 0,2· x2 = 12 и 0,3·x1 + 0,3· x2 = 21. Координаты точки В: х1 = 20, х2 = 50 дают оптимальное решение исходной задачи (1) – (3), при этом Fmax = 65·20 + 80·50 = 5300. Таким образом, фирме в сутки необходимо изготовить 20 изделий А1 и 50 изделий А2, чтобы получить наибольшую прибыль 5300 у.е. Для сравнения отметим, что если бы фирма изготавливала только изделие А1, то ей пришлось бы изготавливать 50 штук этого изделия , получив при этом наибольшую прибыль F = 50·65 = 3250 у.е., а при изготовлении только изделия А2 - 60 штук, что дало бы F = 80·60 = 4800 у.е. прибыли. Анализируя графическое решение задачи (3.1)-(3.3), можно убедиться, что при других значениях коэффициентов целевой функции F (3.3) оптимальное решение может достигаться в других вершинах многоугольника OABCD (см. рис.3.1) или на прямых, являющихся его границами, если прямая F = с1·x1 + с2·x2, параллельна этим границам.

10

9

Эту же задачу можно решить с помощью математического пакета Mathcad. 4. РЕШЕНИЕ ЗАДАЧИ 1 В СИСТЕМЕ MATHCAD 4.1. Построение многоугольника допустимых решений ORIGIN := 1 Запишем все исходные неравенства (3.2), а также целевую функцию (3.1) в виде уравнений, заменив символ F некоторой произвольной константой с

Построим графики записанных уравнений в координатах хоу. Для этого обозначим x2 в i-м уравнении через yi(x), а х1 - через х и запишем эти уравнения в виде, разрешенном относительно yi(x) y1 ( x) :=

y2 ( x) :=

y4 ( x) :=

12 − 0.1 ⋅ x 0.2 10 − 0.2 ⋅ x 0.1

y3 ( x) :=

21 − 0.3 ⋅ x 0.3

c := 5300

c − 65 ⋅ x

80 Строим графики этих функций, используя кнопку Декартов график Shift+2 в панели Графики. x := 0 , 0.01 .. 130

Рис. 4.1 На рис. 4.1 пятиугольник, ограниченный координатными осями х = 0, у = 0, а также прямыми у1(х), у2(х), у3(х), образует многоугольник допустимых решений. Задавая различные возрастающие значения константе с можно добиться того, что прямая 65 x + 80 y = c, смещаясь параллельно самому себе, будет проходить через одну из вершин полученного многоугольника допустимых решений (рис. 4.1). Из графика видно, что задача имеет единственное решение. Максимум целевой функции достигается в точке пересечения прямых 0,1x1 + 0,2x2 = 12 и 0,3x1 + 0,3x2 = 21.

11

12

4.2. Определение точки максимума и значения целевой функции F в этой точке Т.е, точка максимума имеет координаты x1 = 20, x2 = 50 Значение функции F в точке максимума:

Given

 20.   50. 

5. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В СРЕДЕ EXCEL

Find( x , y) → 

F ( x , y) := 65 ⋅ x + 80 ⋅ y Fmax := F ( 20 , 50) Fmax = 5.300000 × 10

3

4.3. Решение задачи линейного программирования с помощью встроенной функции maximize Целевая функция: F ( x) := 65 ⋅ x1 + 80 ⋅ x2 Опишем ограничения: матрица М содержит коэффициенты при неизвестных в левой части ограничений, а вектор v - правые части исходных неравенств (3.2)

 0.1 0.2  M :=  0.2 0.1   0.3 0.3 

 12  v :=  10   21 

Решим задачу с помощью вычислительного блока Given...maximize Для формирования нулевого приближения полагаем значение х2 равным нулю (инициализация решения) x2 := 0 Given M⋅ x ≤ v

x≥ 0

5.1. Графический метод решения задачи 1 1. В столбце А таблицы Excel зададим последовательность значений переменной х1 как арифметическую прогрессию с первым членом, равным нулю, разностью 10 и предельным значением 130. 2. В ячейки В1, С1, D1 вводим следующие формулы В1: =(12-0,1*A1)/0,2; С1: =(10-0,2*A1)/0,1; D1: =(21-0,3*A1)/0,3 и копируем их соответственно в столбцы В,С и D. 3. Вводим в ячейку Е1 формулу = -65*А1/80, которая получается из выражения для целевой функции (3.1) при F = 0, и копируем ее в столбец Е. Значения в этом столбце позволяют построить линии уровня F = 0. 4. Выделяем диапазон А1: Е27, задаем команду «Вставка/Диаграмма…», в открывшемся окне Мастер диаграмм выбираем Тип: «Точечная»; Вид: «Точечная диаграмма со значениями, соединенными сглаживающими линиями без маркеров» и получаем рисунок 5. Форматируем этот рисунок. Устанавливаем курсор мыши на ось х так, чтобы ниже ее появилась надпись Ось Х (категорий) и щелкаем правой кнопкой мыши. Появляется контекстное меню, в которой выбираем Формат оси…

13

14

рис.5.1. Точка пересечения прямых 1 и 3 является точкой выхода линий уровня из многоугольника допустимых решений и имеет координаты (20; 50). Эта точка является точкой максимума целевой функции F (3.1). Значение функции в ней можно найти, если задать формулу: =65*20+80*50. Получается значение 5300. 5.2. Решение задачи симплекс-методом Запишем задачу (3.1) – (3.3) в канонической форме (2.1) – (2.3):

0,1·х1 + 0,2·х 2 + x3 = 12,  0,2·х1 + 0,1·х 2 + x 4 = 10, 0,3·х + 0,3·х + x = 21. 1 2 5  Рис. 5.1 В открывшемся диалоговом окне выбираем вкладку Шкала, в которой в пункте Шкала по оси Х (категорий) указываем опции: - минимальное значение: 0; - максимальное значение: 150; - цена основных делений: 50; - цена промежуточных делений: 10; - ось Y (значений) пересекает в значении: 0. Кроме этого во вкладке Вид задаем более толстую толщину сплошной осевой линии. Аналогично форматируем ось у. Только здесь указываем другие опции: - минимальное значение: -10; - максимальное значение: 110; - цена основных делений: 20; - цена промежуточных делений: 10; - ось Х (значений) пересекает в значении: 0. В диалоговом окне Параметры диаграммы задаем названия диаграммы, осей х и у, а также указываем оси, линии сетки и легенду. В результате графики принимают вид, показанный на

(5.1)

- 65·x1 - 80·x2 = -F → min (5.2) Где х3 ≥ 0, х4 ≥ 0, х5 ≥ 0 являются дополнительными переменными. Известно, что задача линейного программирования решается симплекс-методом. Чтобы получить представление об этом методе, составим в Excel симплекс-таблицы (рис.5.2).

Рис. 5.2 Первая симплекс-таблица расположена в блоке A1:H5. Так как все коэффициенты bi в (5.1) положительны, а коэффициенты

15

16

при дополнительных переменных х3, х4 и х5 равны +1, то очевидно, что набор х1 = х2 = 0, х3 = 12, х4 = 10, х5 = 21 образуют начальное базисное допустимое решение. Эти значения указаны в столбце С таблицы. Коэффициенты при неизвестных хi, i = 1,2,3,4,5 введены в ячейки блока D2:H4, а коэффициенты целевой функции (-F) - в строку 5. Поскольку функция цели (-F) в (5.2) выражена через небазисные переменные х1 и х2, а коэффициенты при х1 и х2 отрицательны, то любое изменение неотрицательных переменных приводит к убыванию (-F). Для простоты будем увеличивать переменную с большим по модулю коэффициентом, т.е. х2. Однако такое увеличение х2 будет сопровождаться изменением переменных х3 и х4 , так как они связаны соотношениями (5.1). Следовательно, х2 не может увеличиваться неограниченно. Из первого равенства системы (5.1) следует, что х3 = 0 при х2 = 12/0,2 = 60, из второго – х4 = 0 при х4 = 0 при х2 = 10/0,1 = 100, а из третьего – х5 = 0 при х2 =21/0,3 = 70. Так как х3, х4 и х5 неотрицательны, то мы не можем увеличивать х2 до значения более, чем 60, т.е.

10  12 max x 2 = min  , ,  0,2 0,1

21   = 60. 0,3 

Т.о, положительный наибольший элемент диапазона D2:H2 находится в ячейке Е2. Следовательно, столбец Е – разрешающий столбец. Наименьшее отношение положительных свободных членов ограничений (5.1) к положительным элементам этого столбца соответствует элементу ячейки Е2, который и будет разрешающим элементом таблицы. Он обозначен в правом верхнем углу ячейки треугольником. Разделив первое ограничение на коэффициент 0,2 при х2 , получим 0,5·х1 + х2 + 5·х3 = 60. Предварительно умножив это преобразованное ограничение на соответствующие коэффициенты при х2 во 2-м, 3-м и 4-м равенствах системы (5.1) и, вычтя его из этих равенств, исключим переменную х2 отовсюду, кроме первого, куда она входит с коэффициентом +1, т.е.

0,5 x1 + x 2 + 5 x3 = 60, 0,15 x1 − 0,5 x3 + x 4 = 4, 0,15 x1 − 1,5 x3 + x5 = 3, − 25 x1 + 400 x3 = − F + 4800

(5.3)

Коэффициенты системы (5.3) вычисляются в ячейках блока A6:H10 , составляющей вторую симплекс-таблицу (рис. 5.2). При этом в ячейку C7 введена следующая формула: =C$2/$E$2, которая скопирована в ячейки D7:H7 этой же строки. В ячейку С8 - =C3-C$2/$E$2*$E3 (или =C3-C$7*$E3). Формула скопирована в ячейки блока C8:H8. Система уравнений (5.3) также является канонической формой исходной задачи (3.1) – (3.3), но уже для базиса х2 , х4 и х5. Теперь эти переменные х2 , х4 и х5 составляют базисное допустимое решение, а переменные х1 и х3 стали небазисными. Отметим, что дальнейшего уменьшения функции (-F) можно добиться только за счет увеличения х1 , поскольку коэффициент при х1 в выражении для функции цели в (5.3) отрицательный. Найдем пределы изменения х1 из условия неотрицательности х2 , х4 и х5. Из первого уравнения (5.3) следует, что х2 = 0 при х1 = 60/0,5 =120, из второго уравнения (5.3) – х4 = 0 при х1 = 4/0,15 = 26,7 , из третьего уравнения (5.3) – х5 = 0 при х1 = 3/0,15 = 20. Следовательно, переменную х1 нельзя увеличивать более, чем до 20, т.е.

 60 max x1 = min  ,  0,5

4 , 0,15

3   = 20. 0,15 

Т.о, положительный наибольший элемент диапазона D9:H9 находится в ячейке D9. Следовательно, столбец D – разрешающий столбец. Наименьшее отношение положительных свободных членов ограничений (5.3) к положительным элементам этого столбца соответствует элементу ячейки D9, который и будет разрешающим элементом таблицы. Он обозначен в правом верхнем углу ячейки треугольником. Третье ограничение в (5.3) разделим на коэффициент при х1 , равный 0,15 , и, умножив полученное равенство на соответст-

17

18

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

x 2 + 10 x3 − 3,333x5 = 50, x3 + x 4 − x5 = 1, x1 − 10 x3 + 6,667 x5 = 20, 150 x3 + 166,667 x5 = − F + 5300

(5.4)

Коэффициенты системы (5.4) вычисляются в ячейках блока A11:H15 , составляющей третью симплекс-таблицу (рис.5.2). При этом в ячейку C14 введена формула: =C$9/$D$9, которая скопирована в ячейки D14:H14. В ячейку С12 - формула: =C7C$9/$D$9*$D7. Формула скопирована в остальные ячейки блока C12:H13. В ячейку C15 введена формула: =C10-C$9/$D$9*$D10 и скопирована в ячейки D15:H15 этой же строки. Переменные х2 , х4 и х1 для этой формы составляют базисное допустимое решение. Отметим, что теперь увеличение любой из небазисных переменных х3 и х5 в выражении для целевой функции (5.4) приводит к увеличению (-F), поскольку коэффициенты при этих переменных положительны. Следовательно, дальнейшее убывание (-F) невозможно, и минимум функции (-F), равный 5300, найден. Он достигается при базисном допустимом решении х1 = 20, х2 = 50, х3 = 0, х4 = 1, х5 = 0. Процесс этих вычислений можно интерпретировать геометрически. Последовательность канонических форм исходной задачи (3.1) – (3.3) соответствует постепенному переходу из точки O в точку В – точку минимума функции (-F) (5.2), через вершины O – A – B многоугольника допустимых решений (см. рис. 1). Если же в уравнениях (5.1) – (5.2) в качестве базисной выбрать переменную х1 , то переход в точку минимума совершился бы по цепочке вершин O – D – C – B, т.е по более длинному пути. Описание процедуры получения последовательности канонических форм представляет собой итерационный процесс. Номера итераций указаны в столбце А (рис. 5.2).

5.3. Решение задачи 1 с помощью встроенных функций Excel Для решения оптимизационных задач в табличном процессоре Excel используется пункт «Поиск решения» (Solver – Решатель) в меню «Сервис» на панели инструментов. Если этого пункта нет, то необходимо установить соответствующую надстройку. Для этого в меню Сервис нужно выбрать пункт Надстройки и в диалоговом окне установить флажок слева от надписи «Поиск решения». В меню «Сервис» появится пункт «Поиск решения». Решение. В соответствии с данными (3)-(4) примера 1 составим и заполним в Excel следующую таблицу Таблица 5.1

Числа в ячейках столбца «Ограничения» подсчитаны с помощью формул. Формула =СУММПРОИЗВ(В3:С3;$B$7:$C$7)D3 введена в ячейку F3 и продолжена в ячейки F4:F5 таблицы. Эта формула также скопирована в F6, но без вычитаемого D6. Выделим ячейку F6 с целевой функцией и вызовем Решатель «Сервис/ Поиск решения». В диалоговом окне укажем: «Установить целевую ячейку:» $F$6, «максимальное значение», «Изменяя ячейки:» $B$7:$C$7, «Ограничения:» $F$3:$F$5<=0. Так как все ограничения имеют одинаковые знаки «<= », то здесь они введены блоком. Заметим, что количества xj , j = 1, 2 изделий являются целыми числами. Поэтому необходимо наложить еще одно ограничение: $B$7:$C$7=целое (целочисленная оптимизация).

19

В окне «Параметры» установим флажки «Линейная модель» и «Неотрицательные значения». Запустим «Выполнить». Поиск решения вернет результат: х1 = 20; х2 = 50. Целевая функция равна Fmax = 5300. Этот результат поиска максимума функции F совпадает с результатами, полученными в п.п. 5.1 и 5.2 с помощью построения графиков и составления симплекс-таблиц в Excel, а также с использованием пакета Mathcad в п. 4. 6. ПОСТАНОВКА И РЕШЕНИЕ ЗАДАЧИ 2 Задача 2. Для изготовления сплава из меди, олова и цинка в качестве сырья используют два сплава тех же металлов, отличающихся составом и стоимостью. Данные об этих сплавах приведены в таблице 2. Таблица 6.1 Содержание компонентов, % Компоненты сплава сплав № 1 сплав № 2 Медь 10 10 Олово 10 30 Цинк 80 60 Стоимость 1 кг, у.е. 5 4 Полученный сплав должен содержать не более 2 кг меди, не менее 3 кг олова, а содержание цинка может составлять от 7,2 до 12,8 кг. Определить количества xj, j = 1, 2 сплавов каждого вида, обеспечивающие получение нового сплава с минимальными затратами на сырье. Эта задача математически формулируется следующим образом. Требуется найти минимум функции F = 5·x1 + 4·x2, (6.1) При следующих ограничениях

20

 0,1 ⋅ x1 + 0,1 ⋅ x 2 ≤ 2,  0,1 ⋅ x + 0,3 ⋅ x ≥ 3, 1 2   0,8 ⋅ x1 + 0,6 ⋅ x 2 ≥ 7,2, 0,8 ⋅ x + 0,6 ⋅ x ≤ 12,8, 1 2   x1 , x 2 ≥ 0.

(6.2)

Здесь неравенства описывают ограничения, накладываемые на количество того или иного металла в полученном сплаве. 6.1. Графический метод решения задачи 2 Решим эту задачу графически. На рис. 6.1 прямые линии, соответствующие неравенствам (6.2), обозначены цифрами 1,2,3,4.

Рис. 6.1 Допустимой областью здесь является пятиугольник PQRST. Целевая функция F (6.1) убывает в направлении вектора

21

22

 ∂F   ∂x  5  −  1  = −   ∂F   4  ∂x 2  Минимальное значение этой функции достигается в точке Р с координатами х1 =2, х2 = 9,333 и равно 47,333. Отметим, что точка Р, являющаяся оптимальным решением задачи (6.1), (6.2), есть вершина допустимой области PQRST. 7. РЕШЕНИЕ ЗАДАЧИ 2 В СИСТЕМЕ MATHCAD 7.1. Построение многоугольника допустимых решений ORIGIN := 1 Запишем все исходные ограничения (6.2) и целевую функцию F (6.1) в виде равенств

Рис. 7.1 Минимальная точка находится на пересечении прямых y2(x) и y3(x): 0,1x1 + 0,3x2 = 3 и 0,8x1 + 0,6x2 = 7,2 (рис. 7.1). 7.2. Определение точки минимума и значения целевой функции F в этой точке

23

24

2.    9.3333333333333333333 

Find( x , y) → 

8. РЕШЕНИЕ ЗАДАЧИ 2 В СРЕДЕ EXCEL

7.3. Решение задачи линейного программирования с помощью функции minimize

В соответствии с данными (3)-(4) примера 1 составим и заполним в Excel следующую таблицу Таблица 8.1

Целевая функция: F ( x) := 5 ⋅ x1 + 4 ⋅ x2 Предварительно поменяв знаки второго и третьего неравенств (2) на противоположные, опишем ограничения с помощью матриц М и v

 0.1  −0.1 M :=   −0.8   0.8

0.1



−0.3 −0.6

 

0.6



 2   −3  v :=   −7.2    12.8 

Решим задачу с помощью вычислительного блока Given...minimize Инициализация решения: x2 := 0 Given M⋅ x ≤ v Minimize( F , x) =

x≥ 0

 2.000000    9.333333 

Т.е, точка минимума имеет координаты x1 = 2, x2 = 9.333333 Значение функции F в точке минимума:

В таблице 8.1 ячейкам В2 и В3 присвоены имена х и у соответственно с помощью команд «Вставка/ Имя► Присвоить…». В ячейки В2 и В3 занесены нулевые значения. В ячейки В6, В9В12 введены формулы, указанные в таблице 8.1 справа от соответствующих ячеек. Выделим ячейку B6 с формулой для целевой функцией и вызовем Решатель «Сервис/ Поиск решения». В диалоговом окне укажем: «Установить целевую ячейку:» $B$6, «минимальное значение», «Изменяя ячейки:» $B$2:$B$3, «Ограничения:» $B$9 <= 2; $B$10 >=3; $B$11 >=7,2; $B$12 <=12,8 (рис. 8.1).

25

26

фавита, например: шифр 2 6 3 буквы а б в В таблице из вертикальных столбцов, обозначенных внизу соответствующей буквой, нужно выбрать числа, стоящие в тех горизонтальных строках, номера которых совпадают с номерами букв по шифру. Замечание. Студенты-заочники выбирают данные из таблиц 1 и 2 в соответствии с шифром – тремя последними цифрами номера зачетной книжки.

Рис.8.1 В окне «Параметры» установим флажки «Линейная модель» и «Неотрицательные значения». Запустим «Выполнить». Поиск решения вернет результат: х = 2; y = 9,333333333. Целевая функция равна Fmin = 47,33333333. Этот результат поиска минимума функции F совпадает с результатами, полученными ранее в системе Mathcad и с помощью графиков (п.п. (6.1), (7.1) – (7.3)). Точка с найденными координатами (2; 9.333333333) находится на пересечении прямых 2 и 3, соответствующих второму и третьему ограничениям системы (6.2). Самостоятельно решить задачу (6.1) – (6.2) с помощью симплекс-таблиц [4]. ЗАДАНИЯ К САМОСТОЯТЕЛЬНЫМ РАБОТАМ Для выработки навыков математической постановки задач линейного программирования и освоения методов их решения ниже приведены задания. Исходные данные к заданиям необходимо выбрать из указанных таблиц согласно своему шифру, который сообщается студенту преподавателем, ведущим практические занятия. Для этого под шифром, представляющим собой трехзначное число, следует расположить три буквы русского ал-

ЗАДАНИЕ 1 «Оптимальный план суточного выпуска строительных изделий» Процесс изготовления строительных изделий двух видов состоит в последовательной обработке каждого из них в трех цехах. Пусть ai,j - время обработки каждого изделия вида j в цехе i, чаc/cут; i = 1,2,3; j = 1,2; bi - время работы цеха i, час/сут; cj - прибыль от реализации одного изделия вида j, у.е.; xj – количество изделий вида j, шт. Составить план суточного выпуска изделий так, чтобы прибыль от их производства была максимальной. Задачу решить: 1) графически с помощью чертежных инструментов; 2) с помощью математического пакета Mathcad: - графически, - с помощью встроенных функций; 3) с использованием табличного процессора Excel: - графически, - с помощью составления симплекс-таблиц, - с помощью встроенных функций Excel; 4) полученные результаты сравнить. Исходные данные взять из таблицы 1

27

№№ строк 1 2 3 4 5 6 7 8 9 0

28

а11

а12

а21

а22

а31

а32

в1

в2

в3

0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 a

1,0 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 б

0,6 0,5 0,7 0,4 0,8 0,3 0,9 0,2 1,0 0,1 в

0,1 0,6 0,2 0,7 0,3 0,8 0,4 0,9 0,5 1,0 а

0,5 0,6 0,7 0,8 0,9 1,0 0,1 0,2 0,3 0,4 б

0,4 0,5 0,6 0,7 0,8 0,9 1,0 0,3 0,2 0,1 в

12 13 14 15 16 17 18 19 20 21 а

10 11 12 13 14 15 16 17 18 19 б

21 20 19 18 17 16 15 14 13 12 в

4) полученные результаты сравнить. Исходные данные взять из таблицы 2.

Таблица 1 с1 с2

№№

65 70 75 80 85 90 60 55 50 45 б

80 85 90 95 100 75 70 65 60 55 в

ЗАДАНИЕ 2 «Задача об оптимальном составе бетонной смеси» Для приготовления b0 кг бетонной смеси c заданными свойствами используются вещества Аj , j = 1,2,3. В xj кг вещества Аj содержится aijxj кг химического элемента Bi , i = 1,2. Содержание элемента Bi в смеси должно заключаться в пределах от bi/ до bi// кг. Стоимость 1кг вещества Aj составляет cj у.е. Требуется определить такой состав для приготовления смеси, при котором общая стоимость израсходованных веществ была бы минимальной. Задачу решить: 1) графически с помощью чертежных инструментов; 2) с помощью математического пакета Mathcad: - графически, - с помощью встроенных функций; 3) с использованием табличного процессора Excel: - графически, - с помощью составления симплекс-таблиц, - с помощью встроенных функций Excel;

a11 a12 а.13 a21 a22 a23 b1/

Таблица 2 b2/ b1// b2// b0 с1 с2 с3

cтрок

1

0,1 1,0 0,6 0,1 0,5 0,4 3,2 5,0 7,0 5,2 15 5 14 5

2

0,2 0,9 0,5 0,6 0,6 0,5 3,4 4,8 6,8 5,4 20 6 13 14

3

0,3 0,8 0,7 0,2 0,7 0,6 3,6 4,6 6,6 5,6 25 7 12 6

4

0,4 0,7 0,4 0,7 0,8 0,7 3,8 4,4 6,4 5,8 30 8 11 13

5

0,5 0,6 0,8 0,3 0,9 0,8 4,0 4,2 6,2 6,1 35 9 10 7

6

0,6 0,5 0,3 0,8 1,0 0,9 4,2 4,0 6,0 6,2 40 10 9 12

7 8

0,7 0,4 0,9 0,4 0,1 1,0 4,4 3,8 5,8 6,4 45 11 8 8 0,8 0,3 0.2 0,9 0,2 0,3 4,6 3,6 5,6 6,6 50 12 7 11

9

0,9 0,2 1,0 0,5 0,3 0,2 4,8 3,4 5,4 6,8 55 13 6

0

1,0 0,1 0,1 1,0 0,4 0,1 5,0 3,2 5,2 7,0 60 14 5 10 а

б

в

а

б

в

а

б

в

а

б

в

а

9 б

Список рекомендуемой литературы 1. Банди Б. Основы линейного программирования: Пер. с англ. – М.: Радио и связь, 1989. – 176 с.: ил. 2. Ивашкин Ю.А. Вычислительная техника в инженерных расчетах. – М.: Агропромиздат, 1989. – 335 с.: ил. 3. Очков В.Ф. Mathcad 8 Pro для студентов и инженеров. – М.: КомпьютерПресс, 1999. – 523 с.: ил. 4. Бундаев В.В. Решение задач линейной оптимизации симплекс-методом. Методические указания и контрольные задания для студентов дневной и заочной форм обучения. – УланУдэ: Изд-во ВСТИ, 1993. – 33 с.: ил.

29

30

Содержание

8. Решение задачи 2 в среде Excel…………………………..

24

1. Формулировка общей задачи линейного программирования……………………………………………………………..

3

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

25

4

Задания 1 «Оптимальный план суточного выпуска строительных изделий»………………………………………...…..

26

2. Постановка задачи линейного программирования в канонической форме……………………………………………….

27

3. Постановка и графическое решение задачи 1…………....

6

Задания 2 «Задача об оптимальном составе бетонной смеси………………………………..………………………….….

3.1. Графический метод решения задачи 1………………….

6

Список рекомендуемой литературы……………………..….

28

4. Решение задачи 1 в системе Mathcad…………………….

9

Содержание……………………………………………………

29

4.1. Построение многоугольника допустимых решений в системе Mathcad………….…………………………………..

9

4.2. Определение точки максимума и значения целевой функции F в этой точке………………………………………

11

4.3. Решение задачи линейного программирования с помощью встроенной функции maximize…..…………………… 5. Решение задач линейного программирования в среде Excel……………………………………………………….… 5.1. Графический метод решения задачи 1……………........

11 12

5.2. Решение задачи симплекс-методом……………………

14

5.3. Решение задачи 1 с помощью встроенных функций Excel…………………………………………………………..…..

18

6. Постановка и решение задачи 2……………………………..…..

19

6.1. Графический метод решения задачи 2………………..…

20

7. Решение задачи 2 в системе Mathcad…………………..….

21

7.1. Построение многоугольника допустимых решений…....

21

7.2. Определение точки минимума и значения целевой функции F в этой точке………………………………………

22

7.3. Решение задачи линейного программирования с помощью функции minimize………………………………………

23

12

31

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОЙ ОПТИМИЗАЦИИ С ИСПОЛЬЗОВАНИЕМ MATHCAD И EXCEL Составитель: В.В. Бундаев

Рецензент: С.Г.Баргуев, к.ф.-м.н., доцент кафедры «Прикладная математика».

Ключевые слова: Mathcad, Excel, задача, уравнения, функция, задание, метод, формулировка, ограничения, коэффициенты.

Редактор Т.А. Стороженко Подписано в печать

2006 г. Формат 60х84 1/ .

Усл. п.л.

. Печать операт., бум. писч.

, уч.-изд. л.

Тираж 100 экз. Заказ №

.

Издательство ВСГТУ. г. Улан-Удэ, ул. Ключевская, 40,в.