Статьи по информатике
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

ЕВРОПЕЙСКИЙ УНИВЕРСИТЕТ РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ МНОГОФУНКЦИОНАЛЬНЫЙ ПАКЕТ ОПТИМИЗАЦИИ

LINDO

(LInear, INTeractive , and DIscrete OPtimizer)

Симферополь – 2007 г.

Содержание

1. Введение........................................................1

2. Взаимодействие с LINDO.................................2

3. Ввод информации...........................................4

4. Вывод информации.........................................5

5. Задача линейного программирования................6

6. Задача целочисленного программирования.........8

7. Задача квадратичного программирования...........9

Введение

 

LINDO – система для решения задач линейного, квадратичного и целочисленного программирования,

Разработанная для широкого круга пользователей. Идея разработки такова, что если пользователь хочет сделать что-то несложное, то это не повлечет за собой больших затрат на изучение особенностей LINDO.

Если, например, пользователь желает :

Максимизировать 2х + 3у

при условиях 4х + 3у < 10

3х + 5у < 12

То, это, именно так, будет представлено пользователем для LINDO.

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

-1-

Пользователи, желающие спроектировать систему, в которой линейное программирование только часть

Большой задачи, могут использовать LINDO, так как она разработана так, что большинство свойств ее может быть доступно через подпрограммы, вызываемые из других программных продуктов.

Взаимодействие с LINDO

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

Существуют три различных стиля пользовательского интерфейса:

1. Версия для вычислительных комплексов

2. Версия для MS-DOS

3. Версия для Apple Macintosh

-2-

В данном пособии описаны главные особенности, общие для всех трех версий.

В версии MS-DOS есть полноэкранный редактор, также имеется возможность выбора файлов. В версии Macintosh предусмотрена система меню и есть возможность использовать другие редакторы, такие как Microsoft Word, Macwrite и другие.

Для помощи пользователю при выборе нужных команд используются три команды :

1. HELP

2. CATEGORIES ( или CAT )

3. COMMANDS ( или COM )

COM выдает список всех доступных команд, сгруппированных по категориям в соответствии с использованием, то есть, например, ввод, вывод и другие.

HELP c последующим именем команды выдает описание этой команды.

CAT выдает список только категорий, затем спрашивает номер интересующей вас категории, и, после ввода последнего, выдает соответствующие этой категории команды.

-3-

 

Ввод информации

 

Кроме ручного ввода информации в LINDO предусмотрены четыре команды для ввода из файла

RETRIEVE : вводит задачу запомненную командой

SAVE.

В версии MS-DOS для выбора

нужного файла можно задавать

маску файла, например,

RETR *.LPK

Все файлы с расширением LPK будут выведены на дисплей.

RMPS : берет задачу, сохраненную в MPS - формате.

TAKE : для считывания файлов - инструкций для LINDO .

Такой файл должен оканчиваться командой LEAVE.

RDBC : чтение файла, сохраненного командой SDBC

-4-

Вывод информации

 

 

LINDO имеет несколько команд вывода информации для двух целей :

1. сохранение формулировки задачи

2. сохранение результатов решения

Результаты решения хранятся в файле. Причина сохранения результатов в файл - это последующая их распечатка.

Команды вывода :

SAVE : cохранение текущей задачи

SMPS : cохранение задачи в MPS-формате

DIVERT : переносит всю информацию в файл,

пока команда RVRT выполняется

RVRT : возвращает информацию на терминал,

пока команда DIVERT выполняется

SDBC : cохранение в формате DataBase ( для

связи с системами dBase , Paradox и

другими)

-5-

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

 

Для ввода и анализа задачи используются следующие команды :

MAX - начало ввода ; максимизация задачи

MIN - начало ввода ; минимизация задачи

END - конец ввода задачи и возвращение в

командный режим

GO - решение текущей задачи и вывод

решения

LOOK - просмотр нужной строки формулировки

задачи

ALTER - изменение элемента текущей задачи

Например, нижеследующий ввод описывает небольшую задачу :

MAX 2х + 3у

SUBJECT TO

4х + 3у < 10

3x + 5y < 12

END

-6-

Команда GO осуществляет решение задачи.

При использовании команды LOOK, LINDO запрашивает спецификацию строки. Это может быть 3 или 1-2 или ALL, что соответствует выводу третьей строки, первой и второй строк или всех строк. При использовании ALTER, LINDO запрашивает для какой строки, переменной и новый коэффициент для этой переменной. После решения задачи, LINDO спрашивает Вас, о желании произвести анализ. Если Вы не знакомы с этими концепциями, вы должны ответить ‘no’ .

Для решения используется Симплекс метод

Следующий пример иллюстрирует выше приведенные комментарии ( смотрите распечатку )

-7-

Целочисленное программирование

Существуют два вида целых переменных, используемых в LINDO :

- переменные, значения которых только 0,1

- переменные, которые принимают значения

0,1,2,....,32766

Переменные первого вида идентифицируются командой INTEGER, переменные второго вида - командой GIN.

Для решения используется метод ветвей и границ.

Следующий пример иллюстрирует выше приведенные комментарии ( смотрите распечатку )

-8-

Квадратичное программирование

 

 

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

Пусть мы имеем следующую модель :

3x2 + 2y2 + z2 + 2xy - xz - 0.8yz -> min

при условиях :

x + y + z = 1 (*)

1.3x + 1.2y + 1.08z >1.12

x < 0.75

y < 0.75

z < 0.75

LINDO требует, чтобы эта модель была переведена в соответствующую совокупность условий Куна-Таккера для оптимальной точки.

Мы переходим к новой задаче, которая является задачей линейного программирования и решение которой есть решение исходной задачи (*).

-9-

Делая это, мы должны ввести для каждого ограничения множитель Ла Гранжа. В нашем случае для пяти ограничений вводим пять множителей :

FIRST

SECOND

THIRD

FOURTH

FIFTH

Запишем функцию Ла Гранжа :

3x2 + 2y2 + z2 + 2xy - xz - 0.8yz +

+ FIRST (x + y + z) +

+ SECOND(1.3x + 1.2y + 1.08z)+

+ THIRD(x - 0.75)+

+ FOURTH(y - 0.75)+

+ FIFTH(z - 0.75)

Для каждой переменной X, Y , Z мы должны записать ограничение, которое представляет собой первую производную функции Ла Гранжа по этой соответствующей переменной.

Затем должны записать первую производную по множителям Ла Гранжа, то есть добавить ограничения исходной задачи (*).

-10-

Целевая функция преобразованной модели представляет собой сумму, первые слагаемые которой это переменные исходной задачи(X+Y+Z), а последующие слагаемые это множители Ла Гранжа. Заметим, что порядок следования ограничений соответствует следованию слагаемых в целевой функции.

После ввода новой (линейной) модели используют команду QCP, с помощью которой указывают номер строки соответствующего первому реальному ограничению (из(*)).

Ввод преобразованной модели и решение задачи представлено ниже ( смотрите распечатку )

-11-

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство