Сравнительный анализ программных средств для решения линейных оптимизационных задач с перспективой их применения в школьном курсе информатики на профильном уровне. Часть 2

1  2

---

2.6.4 Python

 

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

Ещё одним преимуществом является возможность расширения языка, так как изначально по задумке автор он должен был быть расширяемым. В свою очередь это означало, что данный язык могут корректировать любые программисты. Интерпретатор создан на базе С, а исходный код дает возможность совершения различного рода действий. Также можно на С создавать собственные дополнения к Python, затем совершать компиляцию и получать интерпретатор но с уже новыми навыками и возможностями.

Следующим плюсом является присутствие огромного количества модулей, которые имеют разные возможности. Данные модули можно создавать как на базе С, так и на базе Python. Можно привести несколько примеров таких модулей:

• Numerical Python — расширенные математические возможности, такие как манипуляции с целыми векторами и матрицами;
• Tkinter — построение приложений с использованием графического пользовательского интерфейса (GUI) на основе широко распространенного на X-Windows Tk-интерфейса;
• OpenGL — использование обширной библиотеки графического моделирования двух- и трехмерных объектов Open Graphics Library фирмы Silicon Graphics Inc. Данный стандарт поддерживается, в том числе, в таких распространенных операционных системах как Microsoft Windows 95 OSR 2, 98 и Windows NT 4.0.

Единственным недостатком, замеченным автором, является сравнительно невысокая скорость выполнения Python-программы, что обусловлено ее интерпретируемостью.

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

 

2.6.5 IBM ILOG CPLEX STUDIO

 

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

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

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

Что касается недостатков, это конечно же отсутствие руководства на русском языке, что уже затрудняет изучение данной программы, большое количество алгоритмов просто не позволяет отыскать нужный. Также трудности вызывает создание кода программы, так как стоит учитывать очень много различных условий, которые могут привести к неверному решению.

В школе данная программа не применима, потому что она проигрывает тому же Excel и MathCad по простоте изложения материала, но в научных расчетах, для решения серьезных задач, данная программа может пригодиться.

Глава 3 ПЕРЕЧЕНЬ ТЕСТОВЫХ ПРИМЕРОВ

 

Для сравнительного анализа решим данные задачи в каждой из рассмотренных выше программ.

 

Задача №1. Составить оптимальный производственный план

Все переменные задачи неотрицательны .

Ответ .

Задача №2. Решить транспортную задачу в матричной постановке

 

Ответ:

Минимальные транспортные расходы – 1190.

Решение задач оптимизации в MS Excel является самым оптимальным, так как затрачиваемое время на нахождение решения минимальное, алгоритм реализации достаточно просто, по сравнению с другими программами, что только усложняет исходную задачу. Учащимся рамного ближе пакет MS Excel, так как с его основами они знакомятся ещё в средней школе. Решения в других программах больше подходит для университетского курса, так как теория необходимая для их решения расширяется, появляются новые задачи, которые имеют свой специфические условия.

 

ГЛАВА 4 ОБЗОР РЕШЕНИЯ ЗАДАЧИ СИМПЛЕКС-МЕТОДОМ

4.1 Решение задачи № 1 в MS Excel

 

Табличное представление представлено на рисунке 5.1.

Рисунок 5.1 – Табличное представление задачи

После определения модели задачи необходимо настроить параметры Поиска решения (рисунок 5.2). Результаты решения представлены на рисунке 5.3.

Рисунок 5.2 – Диалоговое окно Параметры поиска решения

Рисунок 5.3 – Диалоговое окно Добавление ограничений

После нажатия кнопки Найти решение будет найдено оптимальное решение для модели выбора ассортимента продукции.

Рисунок 5.4 – Результат решения

Модель поиска решения не всегда имеет решение, например, когда ограничения на ресурсы не позволяют удовлетворить потребность во всех продуктах. Для удовлетворения потребности необходимо добавить рабочее время или сырье.

Рисунок 5.5 – Результат решения

Решение задачи происходит с помощью надстройки «Поиск решения» в которой уже есть все встроенные алгоритмы, только нужно вводить значения ячеек, в которых присутствуют данные задачи.

 

4.2 Решение задачи № 1 в MathCAD

 

Составляем целевую функцию:

Матрица коэффициентов системы неравенств и столбец правых частей:

Начальное приближение:

Решаем с помощью блока Given, записываем систему ограничений :

Таким образом, получено решение

Максимальное значение целевой функции .

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

1) Специальной переменной ORIGIN присваивают значение 1. Значением ORIGIN является номер первого элемента строки или столбца в матрице. По умолчанию ORIGIN=0. В меню Math выбрать строку Options или ORIGIN.

2) Вводят исходные данные задачи в матричной форме.

3) Вводят линейную целевую функцию.

4) Задают начальные значения переменным задачи.

5) Вводят ограничения задачи в матричной форме.

6) Определяют оптимальное решение задачи с помощью встроенной функции Maximize (в случае поиска максимума функции) или Minimize (в случае поиска минимума функции).

 

4.3 Решение задачи № 1 в Python

 

Задачу на поиск оптимального решения будем искать симплекс-методом

#подключение библиотек

importnumpy as np

#симплекс-таблица 5*11.

st=np.array([[0,0,1,2,3,4,5,6,7,8,9],

[7,4.,5.,-1.,2.,-1.,5.,0.,1.,0.,0.],

[8,5.,4.,0.,6.,2.,0.,4.,0.,1.,0.],

[9,8.,0.,5.,4.,5.,3.,1.,0.,0.,1.],

[0,0.,-6.,-3.,-6.,-5.,-2.,-3.,0.,0.,0.]])

defsimplex_method(st):

l=0

whilemin(st[4])<0:

#Ищем минимальный элемент в последней строке

n=np.argmin(st[4])

u=np.array([-1.0,-1.0,-1.0,-1.0,-1.0])

for i in range(1,4):

ifst[i,n]>0:

u[i]=st[i,1]/st[i,n]

minba=max(u)

iba=0

#номер строки, в которой находится наше классное ai, которое удовлетворяет нужным условиям

for i in range(1,4):

if u[i]>0 and u[i]<=minba:

minba=u[i]

iba=i

#нашли нужную строчку, теперь будем строить новую симплекс-таблицу

#Делим ведущую строку на ведущий элемент

a=st[iba,n]

for j in range(1,11):

st[iba,j]=st[iba,j]/a

for i in range(1,5):

a=st[i,n]

for j in range(1,11):

if i<iba or i>iba:

st[i,j]=st[i,j]-st[iba,j]*a

#Заменяем номер старого базисного элемента на новый в нулевом столбце

st[iba,0]=st[0,n]

#Запишемтеперьответ

x=[0,0,0,0,0,0]

for i in range(1,4):

x[int(st[i,0])]=st[i,1]

print(‘Производственный план:’,x)

print(‘Максимальное значение целевой функции:’,st[4,1])

return 0

simplex_method(st)

 

4.4 Решение задачи № 1 в Maple

 

На рисунке 5.7 представлено решение задачи № 1 в Maple.

Рисунок 5.7 Решение задачи № 2

Как можно заметить, снова имеют преимущества пакеты MathCad и Maple, так как алгоритмы строятся достаточно компактно и быстро, шанс ошибки достаточно мал, по сравнению с тем Python, в котором одна ошибка приводит к отсутствию запуска программы. Такая же ситуация с MS Excel.

 

4.5 Решение задачи № 1 в IBM ILOG CPLEX STUDIO

 

CPLEX> enter example

Enter new problem [‘end’ on a separate line terminates]:

maximize 6×1 + 3×2 + 6×3 + 5×4 + 2×5 + 3×6

subject to 5×1 — x2 + 2×3 – x4 + 5×5 <= 4

4×1 + 6×3 + 2×4 + 4×6 <=5

5×2 + 4×3 + 5×4 + 3×5 + x6 <=8

bounds

0 <= x1

0 <= x2

0 <= x3

end

CPLEX> optimize

Tried aggregator 1 time.

No LP presolve or aggregator reductions.

Presolve time = 0.00 sec. (0.00 ticks)

Iteration log . . .

Iteration: 1 Dual infeasibility = 0.000000

Iteration: 2 Dual objective = 202.500000

Dual simplex — Optimal: Objective = 2.0250000000e+002

Solution time = 0.01 sec. Iterations = 2 (1)

Deterministic time = 0.00 ticks (3.38 ticks/sec)

CPLEX> display solution variables x1-x6

Variable Name Solution Value

x1 1.120000

x2 1.340000

x3 0.000000

x4 0.260000

x5 0.000000

x6 0.000000

F 12.07000

CPLEX> quit

Стоит отметить, что задача линейного программирования достаточно просто решается с помощью MS Excel, MathCad, Maple, это обусловлено тем, что эти программы обладают набором необходимых команд и встроенных функций, которые помогают оптимизировать процесс, в отличии от Python и Cplex, так как они требуют написания кода программы, что уже может являться препятствием для решения задач большей размерности, поэтому целесообразно использовать на выбор, либо MS Excel, либо MathCad, либо Maple.

 

ГЛАВА 5 ОБЗОР РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

5.1 Решение задачи № 2 в MS Excel

 

Рассмотрим пример решения транспортной задачи в матричной постановки в MSExcel. Исходные данные представлены в таблице 6.1

Рисунок 6.1 Исходные данные задачи

Вводим формулы, необходимые для решения:

Заполняем «Поиск решения»:

Полученный результат:

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

 

5.2 Решение задачи № 2 в MathCAD

 

На рисунке 6.6 представлено решение задачи № 2 в MathCAD.

Рисунок 6.6 Решение задачи № 2

Таким образом, получен оптимальный план перевозок:

• Из пункта 1 надо доставить 5 ед. груза потребителю 3, 20 ед. потребителю 5 и 30 ед. потребителю 6.
• Из пункта 2 надо доставить 30 ед. груза потребителю 3 и 30 ед. потребителю 4.
• Из пункта 3 надо доставить 35 ед. груза потребителю 2 и 15 ед. потребителю 5.
• Из пункта 4 надо доставить 55 ед. груза потребителю 1 и 5 ед. потребителю 4.
• Из пункта 5 надо доставить 25 ед. груза потребителю 6.

Минимальные расходы на перевозку составили 1190 ден. ед.

 

5.3 Решение задачи №2 на Python

 

import numpy as np

t1=np.array([[0,55,35,35,35,35,55],

[55,10,8,6,8,6,7],

[60,6,6,3,4,6,9],

[50,8,5,9,8,5,6],

[60,5,5,5,4,9,9],

[25,6,3,5,4,6,3]])

t2=np.array([[0,5,15,15,10],

[15,11,0,20,11],

[25,12,7,9,20],

[5,0,14,16,18]])

def Transport(t,m,n):

#На всякий случай проверяем условие баланса

sum_a=0

sum_b=0

for j in range(1,n):

sum_a=sum_a+t[0,j]

for i in range(1,m):

sum_b=sum_b+t[i,0]

if sum_a==sum_b:

x=np.zeros((m,n)) #наш будущий план перевозок

#Найдём сначала допустимое решение с помощью метода северо-западного угла

i=1

j=1

while i

while j

x[i,j]=min(t[0,j],t[i,0])

t[0,j]=t[0,j]-x[i,j]

t[i,0]=t[i,0]-x[i,j]

if t[0,j]==0:

for k in range(i+1,m):

x[k,j]=0

j=j+1

if t[i,0]==0:

for l in range(j+1,n):

x[i,l]=0

i=i+1

#Теперь будем искать оптимальный план перевозок с помощью метода потенциалов

#Построим систему потенциалов, сначала найдём кол-во уравнений системы

q=0

for i in range(1,m):

for j in range(1,n):

if x[i,j]>0:

q=q+1

#Создадим матрицу, в которую позже внесем коэффициенты системы

#Размер матрицы q*(m+n)

sp=np.zeros((q,m+n-2))

spb=np.zeros(q) #вектор свободных членов

#Теперь вносим коэффициенты

k=0

for i in range(1,m):

for j in range(1,n):

if x[i,j]>0:

spb[k]=x[i,j]

sp[k,m-2+j]= 1

sp[k,i-1]=-1

k=k+1

#Надо сделать матрицу квадратной, чтобы у системы было единственное решение

#Положим первые две переменные равными нулю, просто уберем первые два столбца

sp1=sp[:,2:m+n-2]

#Решим систему линейных уравнений

uv=np.linalg.solve(sp1,spb)

print(uv)

u=[0,0,uv[0],uv[1],uv[2]]

v=uv[m-3:m+n-1]

print(u,v)

print(spb)

#Строим матрицу невязок

c=np.zeros((m,n))

for i in range(1,m):

for j in range(1,n):

c[i,j]=t[i,j]-(v[j-1]-u[i-1])

print(x)

return 0

Transport(t1,6,7)

Результат:

[ 15. -10. -5. 55. 35. 25. 50. 20. 20.] [0, 0, 15.0, -10.0, -5.0] [55. 35. 25. 50. 20. 20.] [55. 35. 25. 10. 35. 5. 30. 30. 25.] [[ 0. 0. 0. 0. 0. 0. 0.] [ 0. 55. 0. 0. 0. 0. 0.] [ 0. 0. 35. 25. 0. 0. 0.] [ 0. 0. 0. 10. 35. 5. 0.] [ 0. 0. 0. 0. 0. 30. 30.] [ 0. 0. 0. 0. 0. 0. 25.]]

 

5.4 Решение задачи № 2 в Maple

 

1. Решить первую транспортную задачу, найдя цену перевозки и план перевозки.
2. Решить вторую транспортную задачу (с другими ценами), найдя цену перевозки и план перевозки.
3. Составляем матрицу M=, где f1x — это план перевозки первой задачи, поставленный в функцию цели первой задачи; f2x — это план перевозки первой задачи поставленный, в функцию цели второй задачи; f1y — это план перевозки второй задачи, поставленный в функцию цели первой задачи; f2y — это план перевозки второй задачи, поставленный в функцию цели второй задачи.
4. Матрицу M транспонируем. Полученную матрицу обозначаем A.
5. Находим собственные значения и собственные векторы матрицы А.
6. Берем один из столбцов матрицы собственных векторов, в зависимости конечно от собственных значений (если собственное значение равное единице стоит первым, то берем первый столбец, иначе второй ) и нормируем этот столбец.
7. Первую координату нормированного вектора умножаем на первую матрицу цен и складываем с второй матрицей цен умноженное на вторую координату полученного нормированного вектора. Получили новую матрицу цен.
8. Решаем новую транспортную задачу с таким же объемом поставок и потребностей, но с новыми ценами, полученными в пункте 7.
9. Новый план перевозок ставим в функцию цели первой и второй транспортной задачи и таким образом получаем УПРАВЛЕНИЯ. На содержательном уровне нашли оптимальное управление, что одновременно минимизирует стоимость и время перевозки.

Наиболее простой реализацией транспортной задачи является реализация в Excel так как она происходит в надстройке «Поиск решения» которая не является сложной для усвоения, так же время затрачиваемое на решение является достаточно малым, в отличии от реализации на Python или Maple, так как количество элементов кода или программы достаточно велико и нужно быть очень внимательным при создании. Решение транспортной задачи в Mathcad является промежуточным вариантом между MS Excel и Maple, так как Mathcad более прост в использовании.

Заключение

 

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

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

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

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

---

1  2