Курсовая работа: Экономико-математические модели задач о смесях на примере СПК "Родина"
Решение задач симплекс-методом предусматривает выполнение следующих процедур:
1) формирование целевой функции;
2) определение ограничительных условий – функциональных ограничений, которые могут иметь вид неравенств;
3) преобразование ограничений из неравенств в систему равенств путем ввода вспомогательных, свободных переменных (последние имеют экономическое содержание и характеризуют резерв, неиспользованный остаток тех ресурсов, по которым введено ограничение);
4) построение исходной симплексной таблицы, в которой в формируемый план входят только свободные переменные;
5) ввод в исходный вариант плана реальных переменных и прежде всего тех, которые в наибольшей степени реализуют целевую функцию;
6) определение числового значения вводимой переменной – величины программы.
При этом каждый из показателей, характеризующих ограничительное условие, делится на соответствующий коэффициент при вводимом переменном – удельный расход данного ресурса. Тогда наименьшее частное определит максимально возможное в условиях принятых ограничений использование ресурсов при заданном критерии оптимальности. Полученный результат вводится в соответствующую строку формируемого плана симплексной таблицы. На этой строке матрицы весь ресурс исчерпан, она является «узким местом» и подлежит выводу. На ее место вводится другая строка, предварительно пересчитанная. Формируется новый вариант симплексной таблицы.
После каждой симплексной таблицы анализируется оптимальность полученного решения. Если все элементы последней строки (Z-строки) положительны и задача на максимум, то решение оптимально. Если все элементы Z-строки отрицательны и задача на минимум, то решение оптимально. Если план неоптимальный, производится его дальнейшее улучшение.
Алгоритм решения задачи симплекс-методом. Формирование целевой функции и системы ограниченных условий.
1. Перевод неравенств в систему равенств.
2. Построение исходной симплекс-таблицы
Таблица 2.2.1
| Базис |
Ci+n |
C1 |
C2 |
… |
Cn |
Cn+1 |
Cn+2 |
… |
Cn+m |
Bj |
|
x1 |
x2 |
… |
xn |
xn+1 |
xn+2 |
… |
xn+m |
|||
|
xn+1 |
Cn+1 |
a11 |
a12 |
… |
a1n |
1 | 0 | … | 0 |
b1 |
|
xn+2 |
Cn+2 |
a21 |
a22 |
… |
a2n |
0 | 1 | … | 0 |
b2 |
| … | … | … | … | ... | … | … | … | … | … | … |
|
xn+m |
Cn+m |
am1 |
am2 |
… |
amn |
0 | 0 | … | 1 |
bn+m |
|
Z0 |
-- |
-C1 |
-C2 |
… |
-Cn |
0 | 0 | … | 0 | 0 |
3. 1-й столбец содержит базисные переменные (xn+m). 2-й столбец содержит коэффициенты целевой функции при базисных переменных (Ci+n). xi - переменные задачи i=1,2,…n. C1, …,Cn – коэффициенты при x1 ,…, xn целевой функции соответственно. Остальные столбцы и строки (кроме последней) содержат коэффициенты переменных в ограничениях. В последнем столбце находятся свободные члены. Последняя строка определяется по формуле:
4. Если решение не оптимально, то выбираем максимальный по абсолютной величине из отрицательных (если целевая функция стремится к максимуму) или из положительных (в противном случае) элемент Z-строки. В результате получаем «ключевой» столбец. Затем находим минимальное отношение элемента B-столбца на соответствующий положительный элемент «ключевого» столбца, получаем «ключевую» строку. На пересечении «ключевого» столбца с «ключевой» строкой находится «ключевой» элемент.
