Исследование операций (85657)

Посмотреть архив целиком

Министерство образования и науки Украины

Днепропетровский Национальный Университет

Факультет электроники, телекоммуникаций и компьютерных систем

Кафедра АСОИ









Расчётная задача №2


«Исследование операций»



Выполнил:

Ст. группы РС-05


Проверил:

Доцент кафедры АСОИ

Саликов В.А.





г. Днепропетровск

2007г.


Условие задачи




1)Решим графическим методом



Следовательно, оптимальное решение: X1=4/9

Х2=35/9

Минимальное значение целевой функции: Z=55/9


2)Симплекс-метод


В случае, когда одно или несколько ограничений имеют знаки  или = невозможно получить решение. Для получения начального допустимого базиса вводят искусственные переменные R1,R2,R3,R4. Поскольку R1,R2,R3,R4 не имеют отношение к содержательной постановке задачи, то за их применение назначается штраф. В ходе решения задачи на заключительной итерации эти переменные должны принять нулевое значение и выйти из базиса.

Симплексный метод решения задачи линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план, и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план.

Приведем задачу к каноническому виду:


Z=5x1+x2 min


Добавим в систему уравнений искусственные переменные R



при ограничениях:



x1 >= 0; x2 >= 0; x3 >= 0; x4 >= 0; x5 >= 0; x6 >= 0; x7 >= 0; x8 >= 0; x9 >= 0; R1 >= 0; R2 >= 0; R3 >= 0; R4 >= 0


Существуют базисные и небазисные переменные.

Включающиеся переменные называются небазисными в данный момент переменными, которые включаются в состав базиса на следующей итерации.

Исключаемые - базисные переменные, которые на следующей итерации подлежат исключению.

На следующем шаге необходимо подставить значение в целевую функцию:



Таким образом, задача в стандартной форме имеет следующий вид:



x1 >= 0; x2 >= 0; x3 >= 0; x4 >= 0; x5 >= 0; x6 >= 0; x7 >= 0; x8 >= 0; x9 >= 0; R1 >= 0; R2 >= 0; R3 >= 0; R4 >= 0


Перенесем члены целевой функции влево


z -5x1-1x2 = 0


Далее задача решается обычным симплекс-методом


Шаг 0. Используя линейную модель стандартной формы, определяют начальное допустимое базисное решение путем приравнивания к нулю n- m небазисных переменных.

Шаг 1. Из числа небазисных переменных (равных нулю) выбирается включаемая в новый базис переменная, увеличение которой обеспечивает больший по сравнению с остальными рост целевой функции (условие оптимальности). Если такой переменной нет, вычисления прекращаются и полученное решение является оптимальным. В противном случае, переходят к шагу 2.

Шаг 2. Из числа переменных текущего базиса выбирается исключаемая переменная, значение которой быстрее всех стремится к нулю при переходе к новой смежной точке (становящаяся небазисной и равной нулю при введении в базис новой переменной - условие допустимости).

Шаг 3. Определяется новое базисное решение (соответствующее новой смежной точке, т.е. новому составу базисных и небазисных переменных) и осуществляется переход к шагу 1.


Строим симплекс таблицу:


Базис

Решение

Оценка

Z

0

0

0

0

0

0

0


-2

1

0

1

0

0

0

0

0

0

0

0

0

6

6

1

0

0

0

0

0

0

1

0

0

0

0

0

6

-

0

1

0

0

0

0

0

0

1

0

0

0

0

7

7

1

7

-1

0

0

0

0

0

0

1

0

0

0

7

1

2

5

0

0

-1

0

0

0

0

0

1

0

0

10

2

5

2

0

0

0

-1

0

0

0

0

0

1

0

10

5

7

1

0

0

0

0

-1

0

0

0

0

0

1

7

7


- ведущий столбец

- ведущая строка


Из числа текущих небазисных переменных выбирается включаемая в новый базис переменная, увеличение которой обеспечивает улучшение целевой функции

Для определения нового базисного решения (шаг 3) воспользуемся методом Гаусса-Жордана:

А) новая ведущая строка = предыдущая ведущая строка / ведущий элемент;

Б) новое уравнение = предыдущему уравнению – {старый коэффициент ведущего столбца, соответствующий искомому уравнению * новую ведущую строку}


Новая симплекс – таблица будет иметь следующий вид:



Базис

Решение

Оценка

Z

0

0

0

0

0

0

0


0

1

0

0

0

0

0

0

0

0

5

-

1

0

0

0

0

0

0

1

0

0

0

0

0

6

6

0

0

0

0

0

0

1

0

0

0

6

-

1

0

0

0

0

0

0

0

0

0

1

7

0

0

-1

0

0

0

0

1

0

0

5

0

0

0

-1

0

0

0

0

1

0

8

0

0

0

0

-1

0

0

0

0

1

6


Случайные файлы

Файл
10589.rtf
93542.rtf
13680-1.rtf
561.doc
159426.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.