После знакомства с продуктом GAMS появилось желание написать что-то своё для линейного программирования (чтобы каждый раз не «хардкодить» матмодель, а иметь возможность её изменять в отдельном файле). В результате появился скрипт на Python, состоящий из трёх файлов: сам файл скрипта, файл описания матмодели и файл с исходными данными (последние два файла — в текстовом формате).
Далее приведено описание файла матмодели, а также возможности формирования исходных данных для задачи прямо в Python.
1) Заполнение исходного файла (файл описания матмодели):
Опишем правила заполнения файла Task.txt — основного и единственного файла решаемой задачи линейного программирования. Правила пишем прямо в файле в виде комментариев, однако в рабочей версии таких комментариев быть не должно — они не распознаются парсером.
# В данном файле "кодирование" задачи представлено на примере транспортной задачи (массив a - источники, b - потребители, c - массив расстояний между источниками и потребителями).
# Блок data ограничен словами "data" и "enddata" и содержит массивы любых размерностей, на элементы которых в основной части задачи можно будет ссылаться. Используются только круглые скобки, а элементы массивов разделяются запятыми. Ппосле окончания блока должна иметь место пустая строка, а потом уже за ней - следующий блок.
a=(3,1,2)
b=(8,1,2,5)
c=((4,5,3,7),(4,6,7,9),(13,5,6,3))
# Следующий блок - coeffs (коэффициенты), он ограничен строками со словами "coeffs" и "endcoeffs", после него также должна быть вставлена пустая строка. В данном блоке описываются все коэффициенты по которым "строятся" суммы в наших формулах. Например: "i 3" - такая строка значит, что по i будет проводится суммирование от 1 до 3. Если есть ограничения вида y(j)<=d[j], где d[j] - элемент некоего массива, т.е. нет суммы как таковой, то надо для этой суммы ввести коэффициент "k 1", чтобы проводилось "суммирование" по k от 1 до 1 (т.е. будет только одно слагаемое).
coeffs
i 3
j 4
endcoeffs
# Следующий блок - vars (переменные). Здесь описываются все переменные, значения который необходимо найти в данной задаче. Запись вида "x i,j" означает, что необходимо искать переменные x, индексы у которых пробегают значения 1..3 и 1..4 (т.к. соотв. коэфф. i и j изменяются в этих диапазонах, что было определено в предыдущем блоке). Таким образом, ищется двумерный массив x. Размерность массивов переменных может быть любая. Количество массивов неизвестных не ограничено.
vars
x i,j
endvars
# Следующий блок - objectives (целевая функция). Первая строка - имя блока - всегда "objectives". Вторая строка - "min" или "max", т.е. ищется минимум или максимум целевой функции. Третья строка - "sum" - "суммирование"(данное слово обязательно), затем через пробел индексы по которым суммируем, после индексов - в скобках записываем элемент суммы в виде "(коэфф. при переменной)*переменная" (обязательно умножение через "*", если коэффициент равен 1, то пишется в виде "1*x(i,j)"). Во всей целевой функции любая переменная должна встречаться не более одного раза (если это не так, то сгруппируем коэффициенты при всех переменных).
# Заметим, что коэффициенты переменной записываются в круглых скобках и через запятую, а коэффициенты массивов данных - в квадратных каждый коэфф.отдельно!
objectives
min
sum i j ((c[i][j]-20000)*x(i,j))
# Следующий блок - constraints (ограничения). В каждой строке - одна группа ограничений. Запись в виде "forall i : sum j (1*x(i,j)) <= a[i]" означает, что создаётся i ограничений данной группы ("forall"="для всех"), каждое ограничение представляет собой сумму по указанным коэффициентам (в данном случае один коэффициент - j), элемент суммы (в скобках) равен "1*x(i,j)" (здесь коэфф.при x равен 1, но мы его всё равно должны записать!). Далее через пробел записываем знак "<=" (другие знаки пока не поддерживаются, поэтому задача должна быть приведена именно к такому виду), ещё через пробел - элемент правой части ограничения (в первой группе наших ограничений - a[i]).
constraints
forall i : sum j (1*x(i,j)) <= a[i]
forall j : sum i (1*x(i,j)) <= b[j]
endconstraints
# Следующая группа - Int (целочисленные переменные). Здесь перечисляются все переменные, которые должны быть целочисленными по результатам решения. Переменные записываются в виде: <имя переменной><пробел><перечисление коэффициентов через запятую> (также как и в блоке vars).
Int
x i,j
endInt
# Здесь перечисляются переменные, которые должны быть булевскими (в данном примере их нет).
Binaries
endBinaries
Результат решения задачи выдаётся в виде (содержание файла результатов):
-119980
x;0;0
1
x;0;1
0
x;0;2
2
x;0;3
0
x;1;0
1
x;1;1
0
x;1;2
0
x;1;3
0
x;2;0
0
x;2;1
0
x;2;2
0
x;2;3
2
Первая строка — значение целевой функции. Далее идут двумерные номера переменных (т.к. в исходных данных у переменных было по два индекса) и их значения.
2) Использование в Python:
Покажем использование вышеописанной функции на примере кода для решения транспортной задачи (массив a — пункты наличия ресурсов, массив b — пункты потребления ресурсов, c — массив стоимостей перевозок продукции из п.a в п.b).
Предполагается, что массивы a,b и c соответствующих размеров уже были к этому моменту созданы.
#отписываем описание задачи в файл
inp=open('myTask.txt','w')
inp.write('datan')
str2write='a=('
for i in xrange(0,len(a)):
str2write+='('+str(a[i][1])+','+str(a[i][2])+')'
str2write+=','
str2write=str2write[:-1]
str2write+=')n'
inp.write(str2write)
inp.write('n')
str2write='b=('
for i in xrange(0,len(b)):
str2write+=str(b[i][1])
str2write+=','
str2write=str2write[:-1]
str2write+=')n'
inp.write(str2write)
inp.write('n')
str2write='c=(('
for i in xrange(0,len(a)):
for j in xrange(0,len(b)):
str2write+=str(c[(i,j)])
str2write+=','
str2write=str2write[:-1]
str2write+='),('
str2write=str2write[:-2]
str2write+=')n'
inp.write(str2write)
inp.write('enddatan')
inp.write('n')
inp.write('coeffsn')
# коэфф. i изменяется от 0 до (длина массива a)-1
inp.write('i '+str(len(a))+'n')
# коэфф. j изменяется от 0 до (длина массива b)-1
inp.write('j '+str(len(b))+'n')
inp.write('endcoeffsn')
inp.write('n')
# к этому моменту отписаны только исходные данные, поэтому необходимо отписать ещё условие задачи "в чистом виде"
inp0=open('myTask0.txt','r')
str0=''.join([i for i in inp0])
inp0.close()
inp.write(str0)
inp.close()
# В этом комментарии приводится содержание файла myTask0.txt (условие задачи "в чистом виде"). Расшифровка содержания была приведена выше.
#vars
#x i,j
#endvars
#
#objectives
#min
#sum i j ((c[i][j]+a[i][1]-200000)*x(i,j))
#
#constraints
#forall i : sum j (1*x(i,j)) <= a[i][0]
#forall j : sum i (1*x(i,j)) <= b[j]
#endconstraints
#
#Int
#endInt
#
#Binaries
#endBinaries
# Запускаем функцию решения задачи, которой передаём имя входного файла и имя файла, в который будет записано решение задачи
PyGAMSfunc.startSolve('myTask.txt','myTaskSol.txt')
#разбираем файл решения
sol=open('myTaskSol.txt','r')
#словарь для отписывания переменных в виде ключ=[из какого пункта а, в какой пункт б] значение=[сколько единиц продукции]
x=dict()
while True:
t=sol.readline()
#пустая строка - признак окончания массива решений
if t=='':
break
tt=t.split(';')
t=sol.readline()
#складываем искомое значение для пары в словарь
x[(float(tt[1]),float(tt[2].split()[0]))]=t.split()[0]
Кого заинтересовала такая достаточная простая реализация — могу выслать скрипт.
Автор: vinger4
