Решение задач лп с помощью пакета ilog OPL Studio

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 78Следующая ⇒

Практические выводы.

1. Не следует использовать точного сравнения вещественных чисел между собой (с помощью знака "=") за исключением случаев, когда желаемое тождество их машинных представлений можно обосновать (например, переменным могли быть присвоены только небольшие целые значения) или когда ошибка от принятия неправильного решения не имеет большого значения (например, требуется найти максимум из двух вещественных чисел, вычисленных приближенно).

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

if (fabs(D)<eps) …

Условие мнимости обоих корней (т.е. "существенной отрицательности" дискриминанта):

if (D<-eps) …

3. При округлении вверх приближенных величин имеет смысл предварительно вычесть некоторую достаточно малую константу e. Таким образом можно избавиться от нежелательных эффектов (например, что будет, если округлить вверх число x*=1E-20, когда x=0?). Аналогично поступаем при округлении вниз.

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

В вашем классе "решатель" все требуемые погрешности должны быть проинициализированы в конструкторе. Реально это может означать присвоение им заданной программистом константной величины (при программировании симплекс-метода) или получение ввода от пользователя, либо из файла с параметрами настройки решателя (при решении задач нелинейной оптимизации время сходимости алгоритма может сильно зависеть от заданной точности).

Пакет ILOG OPL Studio - интегрированная пользовательская среда для приложений математического программирования и комбинаторной оптимизации, использующая графический пользовательский интерфейс для языка OPL (Optimization Programming Language) [2].

К возможностям пакета относятся:

- создание моделей ЛП, целочисленного ЛП, задач маршрутизации, теории расписаний и др.;

- оптимизация с использованием указанных моделей;

- отладка моделей;

- управление процессом оптимизации и выводом результатов.

Входные данные задачи организованы в виде проекта, который состоит из трех файлов:

· *.mod – файл модели, содержащий описание математической модели, записанной на языке OPL (по синтаксису подобен языку C);

· *.dat – файл данных, где задаются значения исходных данных задачи, определенных в описании математической модели;

· *.prj – собственно файл проекта OPL Studio. Содержит ссылки на файлы модели и данных. Может также содержать настройки алгоритма для решения задачи.

Язык OPL, в отличие от традиционных языков программирования, является так называемым непроцедурным языком, то есть он служит для описания только постановки задачи, а не алгоритма ее решения. В качестве примера другого известного непроцедурного языка можно привести язык управления базами данных SQL.

Пример. Проект OPL Studio для решения задачи о диете.

Содержательная постановка задачи о диете:

Имеется n продуктов питания. Содержание белков, жиров, углеводов и калорий в единице каждого из них определяется коэффициентами a_1j, a_2j, a_3j, a_4j, соответственно, j = 1,...,n. Пусть c_j - стоимость единицы j-го продукта, j = 1,...,n, а b₁,....,b₄ - требуемое количество белков, жиров, углеводов и калорий соответственно в рационе.

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

Модель линейного программирования для данной задачи имеет следующий вид:

f(x) = c₁x₁ + ... + c_nx_n ® min,

    a_i1x₁ + ... + a_inx_n ³ b_i, i=1,...,4,

     x₁ ³ 0, ... , x_n ³ 0.

Файл example.prj:

MODEL = "d:\example\example.mod" // Имя файла модели

DATA = "d:\example\example.dat" // Имя файла данных

Файл example.mod:

int+ nProducts=...;      // Количество продуктов

range Products 1..nProducts;       // Диапазон индексов продуктов

enum Parameters=...;   // Множество индексов параметров рациона

int b[Parameters]=...; // Минимальное количество полезных веществ

int c[Products]=...;        // Стоимости продуктов

int a[Parameters,Products]=...; // Содержание полезных веществ в продуктах

var float+ x[Products];// Переменные задачи - количество продуктов

minimize sum(j in Products) c[j]*x[j]

// Целевая функция - минимизация стоимости

subject to                                         // Ограничения

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология