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

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

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

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

Кафедра АСОИ

















Расчётная задача №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





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

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





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

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

Для решения задачи шага 1 из числа небазисных (равных нулю) переменных выбираем включаемую переменную, имеющую наибольший отрицательный коэффициент в z – уравнении (условие оптимальности), т.к. при этом обеспечивается максимальный прирост целевой функции в стандартной форме. Столбец с включаемой переменной становится ведущим.

Исключаемую переменную (шаг 2) определяем по минимальному положительному отношению правой части уравнения к соответствующему коэффициенту ведущего столбца (условие допустимости - обращение в нуль данной переменной в смежной точке). Строка, соответствующая исключаемой переменной, становится ведущей. Далее определяем ведущий элемент таблицы на пересечении ведущего столбца и строки

Во вводимой переменной в задаче минимизации является небазисная переменная, имеющая в Z-уравнении наибольший положительный коэффициент. 







Базис





























Решение

Оценка

Z

0

0



0







0

0



0

0









0

0



1

0

0



0

0



0

0









0

0



0

0

0



1

0



0

0





-



0

0



0

0

0



0

1



0

0





42



0

1



0

0

0



0

0



0

0





-



0

0



0

-1

0



0

0



1

0









0

0



0

0

-1



0

0



0

1









1

0



0

0

0



0

0



0

0





42



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

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







Базис



























Решение

Оценка

Z

0

0

0

0







0

0





0









0

0

0

1



0



0

0

0



0





-



0

0

0

0



0



1

0

0



0









0

0

0

0



0



0

1

0



0





-



0

1

0

0



0



0

0

0



0





28



0

0

1

0



0



0

0

-1



0









0

0

0

0



-1



0

0

0



1









1

0

0

0



0



0

0

0



0





-



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

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









Базис



























Решение

Оценка

Z

0

0

0

0





0

0

0















0

0

0

1





0

0

0

0





0







0

0

0

0





0

1

0

0





0



-



0

0

0

0





0

0

1

0





0







0

1

0

0





0

0

0

0





0



-



0

0

1

0





0

0

0

-1





0



-



0

0

0

0





1

0

0

0





-1







1

0

0

0





0

0

0

0





0



15



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

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







Базис



























Решение

Z

0

0

0

0

0





0

0













0

0

0

1

0

1

-1

0

0

0

0

-1

1

3



0

0

0

0

0





1

0

0

0









0

0

0

0

0





0

1

0

0









0

1

0

0

0





0

0

0

0









0

0

1

0

0





0

0

-1

0









0

0

0

0

1





0

0

0

-1









1

0

0

0

0





0

0

0

0













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

Таким образом, оптимальное решение задачи имеет вид:



 , 



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