Курсовая работа: Линейное программирование
Вербальные
Эти модели используют последовательности предложений на формализованных диалектах естественного языка для описания той или иной области действительности.
Математические
Это очень широкий класс знаковых моделей, основанных на формальных языках над конечными алфавитами, широко использующих те или иные математические методы.
Информационные
Это класс знаковых моделей описывающих информационные процессы в системах самой разнообразной природы.
Граница между вербальными, математическими и информационными моделями может быть проведена весьма условно; можно считать информационные методики подклассом математических моделей.
Математическая модель выражает существенные черты объекта или процесса языком уравнений и других математических средств. Огромный толчок развитию математическому моделированию дало появление ЭВМ, хотя сам метод появился тысячи лет назад.
Понятие «аналитическое» решение и «компьютерное» решение не противостоят друг другу, так как:
Всё чаще компьютеры при математическом моделировании используются не только для численных расчётов, но и для аналитических преобразований.
Результат аналитического исследования часто выражен в столь сложной форме, что при взгляде на неё не складывается восприятие описываемого ею процесса. Эту формулу можно протабулировать, представить графически, проиллюстрировать в динамике, то есть проделать то, что называется визуализацией абстракции.
2Симплекс метод решения задач линейного программирования
Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.
Для привидения системы ограничений неравенств к каноническому виду, необходимо в системе ограничений выделить единичный базис.
I. Ограничения вида « »- ресурсные ограничения. Справа находится то что мы используем на производстве, слева - то что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0».
II. Ограничения вида «= ». Часто бывает, что несмотря на то что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса - Yi. В систему ограничений они входят с коэффициентом «1» , а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin - «+M», при Fmax - «-M»).
III. Ограничения вида « » - Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл - перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0». А искусственные переменные (Y) как в предыдущем случае.
Алгоритм симплекс метода .
(первая симплекс таблица)
Пусть система приведена к каноническому виду.
X1+ q1,m+1 Xm+1 + …. + q1,m+nXm+n = h1
X2+ q1,m+1 Xm+1 + …. + q1,m+nXm+n = h1
X3+ q1,m+1 Xm+1 + …. + q1,m+nXm+n = h1
……………………………………………………………….
Xm+ qm,m+1 Xm+1 + …. + qm,m+nXm+n =hm
В ней m базисных переменных, k свободных переменных. m+k=n - всего переменных.
Fmin= C1X1+ C2X2+ C3X3+....+ CnXn
Все hi должны быть больше либо равны нулю, где i=1,2...m. На первом шаге в качестве допустимого решения принимаем все Xj=0 (j=m+1,m+2,...,m+k). При этом все базисные переменные Xi=Hi.
Для дальнейших рассуждений вычислений будем пользоваться первой симплекс таблицей (таблица 3.1).