Автор работы: Пользователь скрыл имя, 19 Ноября 2013 в 11:25, курсовая работа
Проникновение математики в экономическую науку связано с преодолением значительных трудностей. В этом отчасти была «повинна» математика, развивающаяся на протяжении нескольких веков в основном в связи с потребностями физики и техники. Но главные причины лежат все же в природе экономических процессов, в специфике экономической науки.
Большинство объектов, изучаемых экономической наукой, может быть охарактеризовано кибернетическим понятием – сложная система.
Введение…………………………......………………......………………………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
Пусть это
минимальное значение
Таким образом, отыскание решения задачи (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. Выбирают разрешающую строку
с помощью определения
4. Находят новый псевдоплан и повторяют все действия начиная с этапа 2.
Таблица 2 - решение двойственным симплекс-метод
Пример 1
Найти максимальное значение функции при условиях
Решение : Запишем исходную задачу линейного программирования в форме основной задачи: найти максимум функции при условиях
Умножим второе и третье уравнения системы ограничений последней задачи на –1 и перейдем к следующей задаче: найти максимум функции
(21)
Составим для последней задачи двойственную задачу. Такой является задача, в результате решения которой требуется найти минимальное значение функции
Выбрав в качестве базиса векторы 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). При этом плане . Так как в столбце вектора Р0 таблица 16 имеются два отрицательных числа (–4 и –6), а в 4–й строке отрицательных чисел нет, то в соответствии с алгоритмом двойственного симплекс–метода переходим к новой симплекс–таблице. (В данном случае это можно сделать, так как в строках векторов Р4 и Р5 имеются отрицательные числа. Если бы они отсутствовали, то задача была бы неразрешима. Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора Р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 Таким образом, с помощью алгоритма двойственного симплекс–метода произведен упорядоченный переход от одного плана двойственной задачи к другому.
Так как в столбце вектора Р0 таблицы 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, Р4 и Р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) нет отрицательных
чисел. Следовательно, если бы в столбце
вектора Р0 не было отрицательных чисел,
то в таблице (6) был бы записан оптимальный
план. Поскольку в указанном столбце отрицательные
числа имеются и такие же числа содержатся
в соответствующих строках, переходим
к новойсимплекс–таблице (таблица 7). Для
этого исключим из базиса вектор Р5 и введем в базис
вектор Р1. В результате получим псевдоплан X=(6;0;-24;
Таблица 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 |
Информация о работе Симплекс-метод решения задачи линейного программирования