Реферат: Математические методы и языки программирования: симплекс метод

n

a i j * x j  A i (i=1,2,..,m)

j=1

2. Реальность плана выпуска:

Xj 0

3. Ограничение по комплектности:

Xk Kl (k=1,2,…,l); (r=1,2,….,p)

Xr Kp

Целевой функционал:

n

Fmax = Xj

j=1

3. ВЫБОР МЕТОДА РЕАЛИЗАЦИИ МОДЕЛИ.

ОБОСНОВАНИЕ МЕТОДА

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

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

1. Ограничения вида «»- ресурсные ограничения. Справа находится то что мы используем на производстве, слева - то что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0».

2. Ограничения вида «=». Часто бывает, что несмотря на то что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса - Yi. В систему ограничений они входят с коэффициентом «1» , а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin - «+M», при Fmax - «-M»).

3. Ограничения вида «» - Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл - перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0». А искусственные переменные (Y) как в предыдущем случае.

Алгоритм симплекс метода.

(первая симплекс таблица)

Пусть система приведена к каноническому виду.

X1+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

X2+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

X3+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

……………………………………………………………….

Xm+ qm,m+1 Xm+1 + …. + qm,m+n Xm+n =hm

В ней m базисных переменных, k свободных переменных. m+k=n - всего переменных.