|
|
| Модуль "Симплекс-метод линейного программирования" |
Последнее обновление: 17 января 2007 23:46 Перейти к скачиванию
Симплекс-метод линейного программирования
Версия: 1.02
Авторы: XXXX Pro (admin@xxxxpro.ru), Lion-Simba.
Все вопросы задавайте на форуме: http://openproj.ru/index.php?f=11
Для использования модуля необходима среда Delphi 6 или более поздняя версия.
Данный модуль реализует обычный и целочисленный симплекс-методы для решения задачи вида:
L=L[1]*x1+L[2]*x2+ .... +L[n]*xn----> min (max)
при ограничениях:
A1[1]*x1+A1[2]*x2+....+A1[n]*xn <=> B1
.....................
Am[1]*x1+Am[2]*x2+....+Am[n]*xn <=> Bm
Где <=> - один из знаков: >= , = , <=
Внимание: ограничения вида x[j]>=0 добавлять не требуется - их наличие неявно предполагается самим симплекс-методом. Явное добавление этих ограничений может привести к зацикливанию
программы или иным негативным явлениям.
Модуль распространяется по принципу КАК ЕСТЬ, автор не несет никакой ответственности за возможные последствия использования данного модуля.
При использовании целочисленного метода целыми считаются все переменные,
возможности сделать целые переменные выборочно на данный момент не предусмотрено.
Для использования модуля необходима среда Delphi с поддержкой динамических массивов (Delphi 6 или 7).
Основные классы и типы:
TSimplex - решение обычным симплекс-методом
TIntSimplex (наследник TSimplex) - решение целочисленным методом
TExtArray - динамический массив чисел типа extended
Основные процедуры и функции Tsimplex:
Constructor Create(const L:TExtArray,maximize:boolean=false); - инициализация объекта.
Имеет два параметра:
L - массив коэффициентов оптимизируемой функции
maximize - направление оптимизации: false - ищем минимум, true - максимум
Procedure AddCons(B:extended; A:TExtArray, Sign:TOperation); - добавление ограничения вида Ai[1]*x1+Ai[2]*x2+....+Ai[n]*xn <=> Bi
Имеет тип параметра:
B - значение коэффициента Bi,
A - массив значений коэффициентов Ai
Sign - знак, перечисляемый тип, приниающий одно из след. значений: (Equal, Less, Greater)
Примечание: если массив A имеет большую длину, чем массив коэффициентов при оптимизируемой функции или
добавленные ранее ограничения, то они автоматически дополняются нулями до нужной длины
Функция может вызываться столько раз, сколько ограничений нужно добавить для задачи
Function Solve:integer; - поиск решения для заданной функции с учетом ограничений
Возвращаемые значения:
SIMPLEX_DONE - решение успешно найдено
SIMPLEX_NO_SOLUTION - решения нет, или невозможно найти опорный базис
SIMPLEX_NO_BOTTOM - решения нет в силу неограниченного убывания линейной формы
Function GetMin:extended; - получение значения (тип extended) функции в точке минимума (максимума)
Function GetSolution:TExtArray; - получение координат (тип TExtArray) найденной точки минимума (максимума)
Destructor Free; - уничтожение объекта
Основные процедуры и функции TintSimplex:
В классе TIntSimplex доступны все функции TSimplex, а также следующие:
Function IntSolve:integer; - решение целочисленным методом, возвращаемые значения полностью аналогичны Solve
Function GetIntMin:extended; - получение значения фунциии в минимуме, найденном целочисленным методом
Function GetIntSolution:TExtArray; - получение координат точки минимума, найденных целочисленным методом
Пример использования:
Uses Simplex;
var
Simplex : TSimplex;
Begin
Simplex:=TSimplex.Create(L,false); // L - массив коэффициентов оптимизируемой функции,
// false - направление поиска (false - минимум, true - максимум)
Simplex.AddCons(B1,A1,equal); // A1 - массив коэффициентов первого ограничения, equal,less, grater - возможные знаки при ограничении
...
Simplex.AddCons(B1,A1,equal); // A1 - массив коэффициентов n-ного ограничения
if (Simplex.Solve=SIMPLEX_DONE) then begin // ф-ция Solve производит решение задачи. Если возвращаемое значение SIMPLEX_DONE, решение найдено
writeln('Результат:',Simplex.GetMin); // получение значения минимума функции
Res:=Simplex.GetSolution; // получение решения - координат точки минимума
end
else writeln('Решения не существует!');
Simplex.Free; // уничтожение объекта;
End;
Для целочисленного решения необходимо заменить TSimplex на TIntSimplex,
Solve - на IntSolve, GetMin - на GetIntMin, GetSolution - на GetIntSolution.
Кроме этого, имеется возможность скачать графическую оболочку (за ее разработку Объединенный Открытый Проект выражает благодарность Lion-Simba) для решения задач с использованием этого метода.
Также на основе модуля Simplex была создана компонента для 1С, автором которой является Игорь Лаврик aka gr. Скачать ее можно здесь: http://www.openproj.ru/simplex/vk_simplex.zip
Всего скачиваний: 9838
|
Время выполнения скрипта: 0.0145. Количество выполненных запросов: 6, время выполнения запросов 0.0050
|
|
