Симплексный метод исследование задачи линейного программирование

Автор работы: Пользователь скрыл имя, 19 Ноября 2013 в 11:22, курсовая работа

Краткое описание

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

Содержание

Введение…………………………......………………......………………………4

1 Основные теоретические положения симплексного метода решения задачи линейного програмирования…............................……………………………6

1.1 Теория линейного программирования…………........…………………...6

1.2 Общий вид задач линейного программирования….....……………….8

1.3 Методы решения задач линейного программирования….....………...10

1.4 Общая характеристика симплекс-метода……………......………………12

2 Решение задачи линейного программирования симплексным методом 14
2.1 Примеры использования симплекс-метода в экономике…………14

2.2 Алгоритм решения задачи линейного програмирования симплексным методом………...................................................................................……………15

2.3 Решения задачи линейного програмирования симплекс-метод..............17

2.4 Двойственная задача........…………………………………..…….………....23

3 Конпьютерная реализация симплекс-метода при решении задачи линейного программирования.........................................................................….......…….....28

3.1 Описание программного продукта.............……………………………...…28

3.2 Тестирование программного продукта.........………………….…………30

Заключение........………………………………………………………………….32

Список используемой литературы.................................………………………….34

Вложенные файлы: 1 файл

курсовая работа2.docx

— 103.14 Кб (Скачать файл)

         Пусть это  минимальное значение принимается  при  , тогда в базис вводят вектор Рr. Число является разрешающим элементов. Переход к новой симплекс–таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Рне будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i–й строке симплекс–таблицы в столбце вектора Рстоит отрицательное число bi, а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения.

         Таким образом, отыскание решения задачи (17) – (19) двойственным симплекс-методом включает следующие этапы:

I

базис

С0

P0

C1

C2

Cе

Cm

C m+1

Cr

Cn

P1

P2

Pе

 

Pm

P m+1

 

Pr

 

Pn

1

P1

c1

b1

1

0

0

0

a1m+1

a1r

a1n

2

P2

C2

b2

0

1

0

0

a2m+1

a2r

A2n

...

……

….

….

е

Pе

Ce

be

0

0

1

0

aem+1

aer

aen

...

...

….

i

Pi

Ci

bi

0

0

0

0

aim+1

air

ain

...

m

Pm

Cm

bm

0

0

0

0

amm+1

amr

Amn

m+1

   

F0

0

0

0

1

m+1

r

n





1. Находят псевдоплан задачи.

2. Проверяют этот псевдоплан на оптимальность.                Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану.

3. Выбирают разрешающую строку  с помощью определения наибольшего  по абсолютной величине отрицательного  числа столбца вектора Ри разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)–и строки к соответствующим отрицательным элементам разрешающей строки.

 

4. Находят новый псевдоплан и повторяют все действия начиная с этапа 2.

Таблица 2 - решение двойственным симплекс-метод

 

Пример 1

Найти максимальное значение функции  при условиях

 

                                                    

Решение : Запишем исходную задачу линейного программирования в форме основной задачи: найти максимум функции  при условиях

 

                                                   

Умножим второе и третье уравнения  системы ограничений последней  задачи на –1 и перейдем к следующей  задаче: найти максимум функции

                                                                                              (20)      

                                                при условиях

                                                                                       (21)

                                                        .                                                (22)

Составим для последней задачи двойственную задачу. Такой является задача, в результате решения которой  требуется найти минимальное  значение функции

                                                                                          (23)

                                          при условиях

                                                                                    (24)

                                          .                                                                   (25)

Выбрав в качестве базиса векторы P3,P4 и X1, составим симплексную таблицу (табл. 3) для исходной задачи (20) – (22).

Таблица 3 – симплексная для исходной задачи

i

Базис

Сб

Р0

1

1

2

0

0

       

P1

P2

P3

p4

p5

1

2

3

4

p3

P4

p5

2

0

0

8

–4

–6

16

1

–1

–1

1

1

1

–2

1

1

0

0

0

0

1

0

0

0

0

1

0


Из этой таблицы видим, что планом двойственной задачи (20) – (22) является  y=(2;0;0). При этом плане . Так как в столбце вектора Ртаблица 16 имеются два отрицательных числа (–4 и –6), а в 4–й строке отрицательных чисел нет, то в соответствии с алгоритмом двойственного симплекс–метода переходим к новой симплекс–таблице. (В данном случае это можно сделать, так как в строках векторов  Ри  Римеются отрицательные числа. Если бы они отсутствовали, то задача была бы неразрешима. Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора Р0. В данном случае это число –6. Следовательно, из базиса исключаем вектор Р5. Чтобы определить, какой вектор необходимо ввести в базис, находим   где  Имеем

 

Значит, в базис вводим вектор P2. Переходим к новой симплекс–таблице (табл. 4).

Таблица 4 –  новая симплекс-таблица

i

Базис

Сб

Р0

1

1

2

0

0

       

P1

P2

P3

p4

p5

1

2

3

4

p3

P4

p2

2

0

1

5

–7

3

13

1/2

–3/2

1/2

1/2

0

0

1

0

1

0

0

0

0

1

0

0

1/2

1/2

–1/2

½


Из этой таблицы видно, что получен  новый план двойственной задачи  Y=(2;0;1/2). При этом плане значение ее линейной формы равно F*=13 Таким образом, с помощью алгоритма двойственного симплекс–метода произведен упорядоченный переход от одного плана двойственной задачи к другому.

         Так  как в столбце вектора  Р таблицы 4 стоит отрицательное число –7, то рассмотрим элементы 2–й строки. Среди этих чисел есть одно отрицательное –3/2. Если бы такое число отсутствовало, то исходная задача была бы неразрешима. В данном случае переходим к новой симплекс-таблице (табл. 5).

Таблица 5- новая симплек-таблица

I

Базис

Сб

Р0

1

1

2

0

0

       

P1

P2

P3

p4

p5

1

2

3

4

p3

P1

p2

2

1

1

8/3

14/3

2/3

32/3

0

1

0

0

0

0

1

0

1

0

0

0

1/3

–2/3

1/3

1/3

2/3

–1/3

–1/3

2/3


Как видно из таблицы 5, найдены оптимальные планы исходной и двойственной задач. Ими являются  и . При этих планах значения линейных форм исходной и двойственной задач равны между собой: 

Пример 2

Найти максимальное значение функции  при условиях

 

                                             .

Решение: Умножая первое и третье уравнения системы ограничений задачи на –1, в результате приходим к задаче нахождения максимального значения функции  при условиях

 

                                            .

Взяв в качестве базиса векторы Р3, Ри Р5, составляем симплекс-таблицу (табл. 6).

Таблица 6 – симплекс - таблица

i

Базис

Сб

Р0

2

3

0

5

0

       

P1

P2

P3

p4

p5

1

2

3

4

p3

P4

p5

0

5

0

–12

10

–18

50

2

1

–3

3

–1

2

2

7

1

0

0

0

0

1

0

0

0

0

1

0


В 4-й строке таблице (6) нет отрицательных чисел. Следовательно, если бы в столбце вектора Рне было отрицательных чисел, то в таблице (6) был бы записан оптимальный план. Поскольку в указанном столбце отрицательные числа имеются и такие же числа содержатся в соответствующих строках, переходим к новойсимплекс–таблице (таблица 7). Для этого исключим из базиса вектор Ри введем в базис вектор Р1. В результате получим псевдоплан X=(6;0;-24;4)

Таблица 7 - новый симплекс таблица

i

Базис

Сб

Р0

2

3

0

5

0

       

P1

P2

P3

p4

p5

1

2

3

4

p3

P4

p1

0

5

2

–24

4

6

32

0

0

1

0

1/3

8/3

–2/3

9

1

0

0

0

0

1

0

0

2/3

1/3

–1/3

1

Информация о работе Симплексный метод исследование задачи линейного программирование