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

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. Параметры по вариантам заданий.

№ вар
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.

Дата добавления: 2014-12-27