Задачи линейного программирования и их решение в современных вычислительных

Лекция №12. Продолжение

задач ЛП
Matlab: функция linprog

ЛП в средах Matlab и Mathcad целевую функцию и ограничения

удобнее записать в матричном виде.
Далее мы рассмотрим запись в матричном виде для двух типов задач ЛП.

переменных модели.

ЦФ в векторном виде:
C=C(x)=cтx,
где т – транспонирование,


- матричное произведение.
Или:
C= C(x)= cx,
где  - скалярное произведение векторов

максимум.
Ограничения–линейные неравенства (≤) + условие положительности всех переменных:
Или в сокращенной

записи:

i=1, 2, …, m,
J=1, 2, …, n.

имеется, соответственно, a1, …,  an  единиц некоторого груза. Этот груз

следует доставить в m пунктов назначения  B1, …, Bm,  и в каждый из них должно быть завезено, соответственно, b1,  …, bm единиц этого груза. Стоимость перевозки одной единицы груза из пункта  Ai  в пункт  Bk  равна  ci,k. Составить такой план перевозок, чтобы суммарная стоимость перевозок была минимальной.
Считать, что количество всего груза на двух пунктах отправления равно потребности в грузе на всех трех пунктах назначения, то есть:
a1  + … + an = b1 +  … + bm.

таблицы:

пункта Ai в пункт Bk . Тогда ЦФ (которую нужно

минимизировать) равна:

Ограничения:

из единиц длины n,
q

– вектор-столбец из единиц длины m. Тогда ограничения имею вид:
Xq=a
tт X=b
X≥0

Обозначим:

параметров задачи – присваиванием или вводом:
Задание начального приближения: x:=0.
Запись ЦФ:

C(x):= cx
Given
Ограничения: Ax≤b
x≥0
Result:=Maximize(C,x) оптимальное решение задачи ЛП

См. https://gigabaza.ru/doc/80570.html и ЛР11.

пакет расширения SOEP (Solving and Optimization Extension Pack), в котором

имеется возможность уточнить тип результата - просто в завершающих функциях блока Given последним параметром ставится строка, указывающая тип переменной в системе уравнений. Местоположение целой переменной обозначается I, бинарной - В, и т.д.:
f(x1,x2)=5*x2-3*x1 Given 2x1+3x2≤5 x1≥0 x2≥0 Minimize (f,x1,x2,"II")

В базовой комплектации MathCAD нет инструментов для установления целочисленных ограничений.
НО можно самостоятельно разработать такой алгоритм!
См., например, http://blog.kislenko.net/show.php?id=974

min cтx таким образом,
что Ax ≤ b.

x = linprog(C,A,b,Aeq,beq) включает ограничения
равенства   Aeqx = beq. Установите   A =

[] и   b = [] если
никакие неравенства не существуют.

x = linprog(f,A,b,Aeq,beq,lb,ub) задает набор нижних
и верхних границ на переменных проекта, x, так, чтобы
решением всегда был в области значений     lb ≤ x ≤ ub.
Установите   Aeq = [] и   beq = [] если никакие равенства
не существуют.

Функция linprog принадлежит пакету Optimization Toolbox, который требует дополнительной установки.