Экономико-математические методы и модели

С учетом этого понятия аналитический метод решения задачи ЛП называют симплекс-методом. Он основан на алгоритме направленного перебора вершин. Этот алгоритм обеспечивает переход от одной вершины к другой в таком направлении, при котором значение целевой функции от вершины к вершине улучшается.

þ Определение значения целевой функции и переменных в одной вершине считается итерациейb>.

Число итераций в реальных задачах может измеряться сотнями. Вручную, с помощью симплекс-метода, могут быть решены задачи, содержащие не более 10 итераций. Поэтому в реальных задачах применяют ЭВМ и пакеты прикладных программ (ППП).

Метод решения задач ЛП с помощью симплексных таблиц изложен на конкретном примере. Пусть требуется найти неотрицательное решение системы линейных неравенств:

ì4x1+9x2 £ 56

(5.14) í5x1+3x2 £ 37

î-x1+2x2 £ 2

обращающее в максимум линейную форму:

¦=3x1+4x2 (5.15)

Вначале перейдем от системы неравенств (5.14) к системе уравнений, добавив к левым частям неравенств неотрицательные переменные x3, x4, x5. Мы получим:

ì4x1+9x2+x3+0 . x4+0 . x5=56

(5.16) í5x1+3x2+0 . x3+x4+0 . x5=37

î-x1+2x2+0 . x3+0 . x4+ x5=2

¦= 3x1+4x2+0.x3+0.x4+0.x5 (5.17)

перепишем теперь систему (5.16) в виде системы 0-уравнений:

ì0=56 - (4x1+9x2+1 . x3+0 . x4+0 . x5)

(5.18) í0=37 - (5x1+3x2+0 . x3+1 . x4+0 . x5)

î0=2 - (-x1+2x2+0 . x3+0 . x4+1 . x5)

¦=0 - (-3x1-4x2-0.x3-0.x4-0.x5) (5.19)

заметим, что система (5.18) может быть записана в виде одного векторного равенства:

0=B-(A1x1+A2x2+A3x3+A4x4+A5x5),

где вектор-столбец В имеет своими компонентами свободные члены, а векторы A1, A2, . , A5 - коэффициенты при соответствующих переменных x1, x2, x3, x4, x5. Иными словами:

Линейная форма имеет вид: ¦=3x1+4x2+0 . x3+0 . x4+0 . x5.

Векторы A3, A4, A5 образуют базис. Это означает, что, присвоив х1=0, х2=0, получаем из (5.16) первое базисное решение: x1=0; x2=0; x3=56; x4=37; x5=2.

При этом значение линейной формы ¦=0. На основании (5.18) строим первую симплексную таблицу.

Симплексная таблица строится следующим образом:

В заглавной строке пишем последовательно векторы B, A1, A2, A3, A4 , A5. Слева добавляем колонку «Базисные векторы», рядом с ней колонку «С», в которой поставлены коэффициенты при базисных переменных в линейной форме, в данном случае величины С3, С4, С5. В последней строке, называемой индексной, и обозначаемой через ¦ j-Сj, проставляются числа, равные значению линейной формы, в соответствием с уравнением (j=1, 2, 3, 4, 5). В итоге мы имеем таблицу 5.3.

Таблица 5.3.

Базисные	Коэффициенты	Вектор свободных	3	4	0	0	0
векторы	линейной формы С	членов В	A1	A2	A3	A4	A5
A3	0	56	4	9	1	0	0
A4	0	37	5	3	0	1	0
A5	0	2	-1	2	0	0	1
Индексная строка ¦ j-Сj		0	-3	-4	0	0	0

 Скачать реферат

Страница:  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 
 16  17  18 

Другие рефераты на тему «Экономико-математическое моделирование»:

• Статистический анализ и прогнозирование доходов бюджета
• Статистические методы определения экономических показателей
• Компьютерное моделирование технологических процессов пищевых производств
• Построение моделей статики по методике активного эксперимента
• Нахождение критического пути табличным методом