Исследование операций
Министерство образования и науки Украины
Днепропетровский Национальный Университет
Факультет электроники, телекоммуникаций и компьютерных систем
Кафедра АСОИ
Расчётная задача №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 | | | | |
|
Если переменной для включения в базис нет и все коэффициенты при небазисных переменных - отрицательны, то полученное решение оптимально.
Таким образом, оптимальное решение задачи имеет вид:
,
Так как, значение целевой функции, вычисленное симплекс методом, совпало со значением, полученным в результате решения графическим методом, можно сделать вывод, что найденные значения верны.