1.1.2 Решение задачи линейного программирования как задачи оптимизации

В пакете Mathcad для решения задач оптимизации используются функции Maximize и Minimize. Применительно к рассматриваемой задаче запись решения имеет следующий вид:

(целевая функция)

(начальное приближение)

(ограничения) (1.6)

Полученные оптимальные значения переменных присваиваются компонентам вектора P. Оптимальное значение целевой функции может быть получено с помощью выражения

(1.7)

(Следует помнить, что в пакете Mathcad нумерация компонент вектора начинается с нуля).

Функции Maximize и Minimize могут быть использованы и при матричной записи задачи линейного программирования.

1.2 Решение задачи с помощью процессора Excel

Табличный процессор Excel содержит специальную программу - надстройку «Поиск решения», используемую для решения задач оптимизации.

Рассмотрим порядок решения на примере задачи (1.1). Предварительно на листе Excel необходимо подготовить исходные данные.

1. Ввести начальные значения переменных.

Сопоставим переменным x₁ и x₂ соответственно ячейки A1,A2 и заполним их нулями.

2. Задать целевую функцию.

В ячейку B1 введем формулу

.

3.Задать левые части ограничений.

В ячейки C1, C1, C3 введем соответственно формулы

4.В меню «Сервис» выполнить команду «Поиск решения» и заполнить диалоговое окно (рис. 1.2). Для ввода каждого нового ограничения необходимо нажимать кнопку «Добавить», а закончив ввод – кнопку «ОК».

Рисунок 1.2 – Вид заполненного диалогового окна

После заполнения окна нужно нажать кнопку «Выполнить» и в открывшемся окне «Результаты поиска решения» в поле «Тип отчета» выделить опцию «Результаты» и нажать кнопку «ОК».

Сформированный отчет будет содержать полученное значение целевой функции («Целевая ячейка») и оптимальные значения переменных («Изменяемые ячейки»).

Анализ таблицы «Ограничения» (рис. 1.3) позволяет заключить, что ресурсы, соответствующие первому и второму ограничениям, являются дефицитными – на это указывает статус ячеек C1 и C3 «связанное», а ресурс, соответствующий второму ограничению, - недефицитный (статус C2 «несвязанное»). Полученная информация позволяет провести исследование задачи на чувствительность.

Рисунок 1.3 – Статус ограничений

1.3 Варианты заданий

1.		2.
3.		4.
5.		6.
7.		8.
9.		10.
11.		12.
13.	14.
15.	16.
17.	18.
19.	20.
21.	22.
23.	24.

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

2.1 Транспортная задача с оптимизацией плана перевозок по критерию времени

Задачи данного типа не являются, как известно, задачами линейного программирования. Они решаются методом условной оптимизации, с включением в число ограничений порогового уравнения.

Задача. Найти оптимальное решение транспортной задачи с матрицей времени перевозок между пунктами

,

запасами в пунктах отправления a₁=10, a₂=15, a₃=25 и заказами в пунктах назначения b₁=5, b₂=10, b₃=20, b₄=15.

Использовать пакет Mathcad.

Решение. Задать нумерацию элементов массивов с единицы:

.

Определить число рядов и столбцов матрицы T:

Ввести единичные векторы IC (m x 1) IR(n x 1):

Задать начальные перевозки равными нулю:

Записать целевую функцию:

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

Упорядочить элементы матрицы X в порядке невозрастания соответствующих им элементов матрицы T и сформировать из них вектор g размерности (n+m) x 1:

Сформировать ограничения для задачи поиска решения:

Последнее из условий представляет собой пороговое уравнение.

Записать функцию поиска решения, удовлетворяющего заданным ограничениям:

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

Последовательно заменяя r числами 1, 2, ..., будем получать новые решения до тех пор, пока при некотором значении r* не поступит сообщение, что решение не найдено. Подставив вместо r значение r*-1, найдем оптимальное решение: