Работа № 6. Симплекс-метод линейного программирования

Задание

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

2. Построить алгоритм и программу реализации симплекс-метода в Mathcad и решить задачу оптимизации для контрольного примера.

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

4. Дать геометрическую интерпретацию задачи линейного программирования, согласно варианту задания в 3D и 2D графике Mathcad.

Методические указания.

1. Постановка задачи линейного программирования и теоретическая основа методов линейного программирования приведены в разделе 3, тема 4.

2. Приведенный далее машинный алгоритм симплекс-метода детализирует операции метода и адаптирует их к специфике Mathcad. Он заключается в следующем:

1) Решая совместно любую произвольную пару уравнений для ограничений, записанных в канонической форме, находим некоторую (начальную) вершину многогранника допустимых решений (начальное допустимое базисное решение).

2) В этой вершине вычисляем значение целевой функции.

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

4) Вычисляем в ней значение целевой функции.

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

6) Процедура п.п. 1–5 проделывается для всех смежных вершин, вновь пока не случится, что все вершины смежные с базисной будут иметь большее значение целевой функции. Эта вершина и принимается за оптимальное решение.

Ввиду конечности вершин многогранника (следствие конечности ограничений задачи ЛП) за конечное число шагов мы найдем искомую точку минимума.

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

Согласно приведенному алгоритму нужно составить программу в Mathcad и отладить ее на примере следующей задачи. Текст программы, а также отладочный пример решения оптимизационной задачи приведен на рис. 35.

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

Целевая функция задана F(x) = 10 + 2px₁ + qx₂ ,

Критерий оптимизации F(x*) = min F(x) ,

О граничения x₁ - 5p x₂ = 1

x₁ + q x₂ = 7

x₁ + p x₂ = 2

x₁ – 3q x₂ = 4

x_i ≥ 0, i =1,…,4

Требуется найти координаты точки x*, в которой F(x) имеет минимум.

Согласно алгоритму симплекс-метода, составляем пары ограничений с первым уравнением, записываем в матричной форме и, решая их совместно как систему уравнений, находим базисное решение. Вычисляем значения целевой функции F(x) в базисной точке. Находим minF(x) с помощью встроенной процедуры Mathcad. Получаем новое базисное решение. Процедуру реализуем в цикле (см. раздел «Инструкция по работе в Mathcad»).

Рис. 35. Текст программы для решения задачи ЛП симплекс-методом, пример расчета и геометрическая интерпретация.

На рис. 35 приведены результаты решения оптимизационной задачи отладочного примера – координаты точки минимума х*(x₁,x₂.) и значение целевой функции F* = F(x*).

3. Для решения задачи повариантно значения параметров p и q принимаются в соответствии с номером фамилии студента в списке группы.

Значения параметров заданий по вариантам приведены в табл. 6.

Таблица 6. Параметры по вариантам заданий.

№ вар	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
p	0,5	0,4	0,3	0,3	0,2	0,1	0,1	0,1	0,1	0,6	0,1	0,8	0,9	0,4	0,6
q	0,3	0,2	0,1	0,5	0,1	0,4	0,5	0,4	0,3	0,1	0,4	0,3	0,5	0,3	0,4

4. Для построения геометрической интерпретации необходимо для каждой функции ограничений ввести новые идентификаторы x₁(x), x₂(x), x₃(x), x₄(x). Вызов встроенных процедур 3D и 2D графиков в MathCad производится согласно инструкции по работе в MathCad (см. раздел 4). Геометрическая интерпретация задачи линейного программирования для отладочного примера в графике MathCad приведена на рис 33. Построены целевая функция в 3D-графике и область допустимых значений параметра оптимизации в 2D.

Работа № 7. Многомерные методы оптимизации

Задание

1. Ознакомиться с методами многомерной оптимизации: методом Хука-Дживса, методом покоординатного спуска, методом наискорейшего спуска и методом градиента.

2. Составить программу расчета для одного из методов, согласно варианту задания, по двум параметрам для задачи без ограничения и отладить ее на контрольном примере.

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

Методические указания

1. Постановка задачи нелинейного программирования и многомерные методы приведены в разделе 3, тема 5. В данной работе многомерная оптимизация рассматривается на примере двухпараметрической задачи. В качестве методов использованы, в зависимости от варианта, метод Хука-Дживса и метод покоординатного спуска, которые относятся к методам нулевого порядка.

Алгоритм любого из методов поисковой многомерной оптимизации состоит из двух этапов:

1) Определение направления движения в пространстве параметров на текущем шаге.

2) Движение вдоль выбранного направления одним из методов одномерной оптимизации.

На первом этапе в обоих из названных методов направление выбирается вдоль координаты.

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

Процесс оптимизации завершается, когда удовлетворяется заданная точность одновременно по обеим координатам.

2. При составлении программы многомерного метода рекомендуется воспользоваться готовой программой одномерного метода равномерного поиска, использованной в работе №1. Эта программа выполняет роль внутренней процедуры и дополняется модулем чередования координат, из которого к ней производится обращение.

В качестве параметров оптимизации принимаются переменные х и у, область допустимых значений параметров определена границами (Ах,Вх и Ау,Ву), точность по каждому параметру соответственно Ех и Еу. Выражение целевой функции записывается в виде: Z(x,y)=F(x) +H(y).

Для определения координат текущей точки в области параметров оптимизации рекомендуется использовать двумерные массивы Mathcad.

Текст программы формирования целевой функции Z(x,y), а также ее геометрическая интерпретация для отладочного примера в 3D и 2D графиках приведен на рис. 36. Вызов процедур в MathCad производится согласно инструкции по работе в MathCad (см. раздел 4).

Программа двумерной оптимизации методом покоординатного спуска в MathCad и результаты оптимизационного расчета для отладочного примера приведены на рис. 37. Использованы вспомогательные машинные переменные для аргумента t и целевой функции Р(Х,Y), а также рабочие ячейки G и H. Одномерный метод равномерного поиска оформлен в виде процедуры и обозначен в программе L(P, a, e), где параметры P, a, e формальные параметры процедуры которым при обращении присваиваются фактические значения. Результаты расчетов: координаты точки минимума обозначены идентификаторами (Xm,Ym), а значение целевой функции в этой точке − Z(Xm,Ym).

Рис.36. Программа построения целевой функции от двух параметров в Mathcad.

Рис. 37. Программа двумерной оптимизации в MathCad.

3. При выполнении оптимизации согласно варианту для целевой функции и параметров, используются данные, представленные в табл. 7. Варианты заданий, как по методу, так и по компонентам F(x) и H(y) целевой функции Z(x,y), а также интервалам по координатам х и у отражены сочетанием номеров строк табл. 7. Компоненты целевой функции F(x) и H(y), значения границ интервалов – (Ах,Вх) и (Ау,Ву), а также значения точностей Ех и Еу по каждой из кооринат – х и у берутся из графы «номер функции» табл.7. В качестве стартовой принимается точка С(Ах,Ау) на границе области допустимых значений параметров оптимизации (Ах,Вх и Ау,Ву).

Таблица 7. Варианты заданий.

№ варианта		1	2	3	4		5	6		7	8
Метод		Хука-Дживса					Поокординатного спуска
Номер F(x)		1	2	3	4		5	6		5	4
Номер H(y)		2	3	4	5		6	1		2	3
Номер функции	Целевая функция Z(x,y) =F(x) + H(y)					Интервал (а,b)			Точность e
1	4 – 0,1х + cos(x)					0 – 5,0			0,1
2	х² + 1/х					0,1 – 2,0			0,01
3	tg(x) + 1/х					0,1 – 1,5			0,001
4	exp(x) + 1/х					0,1 – 1,0			0,01
5	tg(x) – ln(x)					0,1 – 1,0			0,001
6	3۰exp(–x) + sin(x)					0 – 8,0			0,1

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

Работа № 8. Многомерная оптимизация при ограничениях

Задание

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

2. Составить программу расчета для одного из методов, согласно варианту задания по двум параметрам для задачи с ограничениями и отладить ее на контрольном примере.

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

Методические указания

1. Постановка задачи многомерной оптимизации при ограничениях проведена в разделе 3, тема 5. Описание методов оптимизации при ограничениях: метода движения вдоль границ, отражения от границ, метода штрафных функций − приведены в разделе 3, тема 6. В данной работе многомерная оптимизация рассматривается на примере двухпараметрической задачи. В качестве методов использованы, в зависимости от варианта, метод Хука-Дживса или метод покоординатного спуска.

Алгоритмы методов многомерной оптимизации при ограничениях (метода движения вдоль границ, отражения от границ) состоят из двух этапов:

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

- движение в пространстве параметров оптимизации, когда ограничения нарушены.

На первом используется один из методов, описанных в разделе 4, тема5, например, метод Хука-Дживса или метод покоординатного спуска.

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

2. Программа многомерной оптимизации при ограничениях объединяет согласно алгоритму (см. п. 1) две программы: программу расчета области допустимых значений параметров и программу оптимизации без ограничений, использованную в предыдущей работе №7. Начнем с первой. Программа расчета области допустимых значений параметров, заданной ограничениями, двумерной задачи приведена на рис. 38.

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

Целевая функция Z(X,Y), как и в предыдущей работе №7, задана в виде двух слагаемых:

Z(X,Y) = F(X) + H(Y) (8.1)

Для отладочного примера ограничения заданы эллипсом и линейной функцией. Эллипс задан в тригонометрической форме уравнениями:

x2(t) = A cos(t)+xc, (8.2)

y2(t) = B cos(t)+y.

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

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

u(t) = kt + b1 (8.3)

В рассмотренном на рис. 38 примере коэффициент наклона прямой принят k=0.

Там же приведены графики области допустимых значений параметров оптимизации в формате 2D и график целевой функции в 3D.

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

В задачах с ограничениями более эффективно использовать одномерные методы деления отрезка пополам либо «золотого сечения». Если ограничение задаются функциями (в отладочном примере):

Q1(x,y) = С, (8.4)

Q2(x,y)=A(x-a)² + (y-b)²,

где А, a, в, С - коэффициенты, которые выбираются согласно варианту (таблица 7), то область допустимых значений параметров оптимизации (Ах,Вх и Ау,Ву) может быть определена путем совместного решения уравнений (8.4) как системы. Эти решения дадут границы интервала поиска решения по каждой координате x и y соответственно (Ах,Вх) и (Ах,Вх).

Приведенная на рис. 39 программа написана для метода покоординатного спуска, в котором для движения вдоль координаты использована программа одномерного метода деления отрезка пополам (см. Работа 1), оформленная в виде процедуры.

3. При выполнении оптимизации для функции и параметров согласно варианту, используются данные, представленные в табл. 9. Варианты заданий, как по методу, так и по компонентам целевой функции F(x) и H(y), а также интервалу по координатам х и у отражены сочетанием номеров строк табл. 8, как и в работе №7.

Рис. 39. Программа метода покоординатного спуска и пример оптимизации при ограничениях.

Таблица 9. Варианты параметров для ограничений.

В качестве программ одномерной оптимизации методами деления отрезка пополам и «золотого сечения» рекомендуется использовать программы из работ №2 и №3 соответственно, оформив их как процедуры. Выбор метода в зависимости от варианта таков: четные номера вариантов соответствуют методу деления отрезка пополам, нечетные – методу «золотого сечения».

Задание рекомендуется выполнять в следующей последовательности:

Дополнить модуль выбора направления движения соответствующего многомерного метода п. 2 блоком отыскания границ интервала вдоль выбранного направления, решив совместно систему:

Q(x,y) = C, (8.5)

Y = k۰X + d.

В программе из работы 7 п. 2 рис. 36 заменить модуль одномерной оптимизации равномерного поиска на модуль метода деления отрезка пополам или метод «золотого сечения» в соответствии с вариантом.

3.3. Провести оптимизационный расчет для функции п. 2 с ограничением, согласно варианту табл. 8.2.

43