Решение задач оптимизации и линейного программирования с помощью современных программных средств

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

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

Е. Р. Алексеев, Е. В. Павловская, О. В. Чеснокова, О. Ломовцева

РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ И ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ СОВРЕМЕННЫХ ПРОГРАММНЫХ СРЕДСТВ

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

F(x15x2,K,xn)  min,

gi(x1,x2,...,xn) > 0,i = 1,k-

В данной работе описаны возможности пакетов MS Excel и MathCAD при решении задач оптимизации.

1. MS Excel

Основным инструментом для решения задач оптимизации в MS Excel является блок Поиск решения (Сервис \ Поиск решения).

Задача линейного программирования. С помощью блока Поиск решения можно находить решение практически любых задач линейного и целочисленного программирования.

Транспортная задача. С помощью блока Поиск решения можно решить закрытую транспортную задачу.

Рассмотрим транспортную задачу А с матрицей стоимостей перевозок

C=

80 215 100 108 102 68

вектором объема производства а = (2300 1400) и вектором спро-

са b = (1000 1500 1200). С помощью блока Поиск решения MS Excel можно

найти точное решение. С задачами с избытком или недостатком потребностей MS Excel часто не справляется. При решении задач с недостатком потребностей (см.

значительно отличается от оптимального

рис. 1) полученное решение

5 О 0 50 0 0

0 0 0 200 200

0 100 0 0 0

0 0 100 0 0

Задача В

A В С| D I E I F G Н

1 Матрица стоимостей перевозок

2 1 6 8 12 1Б

3 16 10 8 6 15

4 4 1 9 11 13

5 3 2 7 7 15

6 План перевозок Потребности

7 0 0 0 0 100 100 100

8 50 100 150 100 0 400 400

9 0 0 0 100 0 100 100

10 0 0 0 0 100 100 100

11 50 100 150 200 200 7800

12 Пр0ДЛОЖЄНИ0 50 100 150 200 250

1Я

Рис. 1

Задачи нелинейного программирования в MS Excel 2000 решаются достаточно хорошо. Рассмотрим задачу нелинейного программирования на примере

x v vz

задачи С: найти минимум функции f(x,y,z) = 7—+ 3—2- + 5^-з + xyz . Для этого в

v z x

рабочий лист Excel введем следующую информацию (см. рис.2).

Рис. 2

Для решения этой задачи следует воспользоваться блоком Поиск решения, в параметрах которого необходимо снять флажок линейной модели (это следует делать при решении любой нелинейной задачи оптимизации). В результате полученное решение (х=1.28, y= 1.17, z=1.36) отличается от точного (х=1.315, y= 1.21, z=1.2).

2. MathCAD

В MathCAD существует решающий блок, открываемый служебным словом Given, за которым должны следовать уравнения и ограничительные условия. При решении задач оптимизации решающий блок завершается функциями Maximize, Minimize. Функция Mmimize(f,v1,v2,...,vn) (Maximize(v1,v2,...,vn)) возвращает значения переменных, при которых функция f достигает минимального (максимального) значения.

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

f(x,y,z) := 7  —h 3  — + 5

У z2

х:=1 у:=1 z;=]

Given

X := Minimize

XT =

f(X0,XbX2) = 15.23 Рис. 3

y-z

Решение, полученное в MathCAD, значительно точнее решения, найденного в MS Excel.

Определенную сложность в MathCAD представляет решение транспортной задачи. При использовании решающего блока нельзя работать с матрицами, и поэтому при формулировке транспортной задачи необходимо избавиться от матриц путем перехода к одномерным массивам. На рис. 4 приведено решение задачи А средствами MathCAD. Однако MathCAD при решении транспортной задачи не справляется с большим количеством переменных.

ORIGIN := 1 N := 3 М := 2

Minimize^,у) =

Рис. 4

Кроме того, в MathCAD не предусмотрена возможность решения задач целочисленного программирования.

Наиболее распространенные в инженерной практике программы - MathCAD и MS Excel - хорошо справляются с задачами линейного программирования, MathCAD достаточно хорошо решает нелинейные задачи оптимизации. MS Excel достаточно точно решает закрытую транспортную задачу и задачу целочисленного программирования. Для решения более сложных задач оптимизации следует использовать специализированные пакеты решения задач оптимизации.