Навигация
Решение поставленной задачи
15921
знак
4
таблицы
2
изображения
3. Решение поставленной задачи
x1 – количество изделий первого вида.
x2 – количество изделий второго вида.
F(x) – целевая функция.
5x1 + 3x2 =150
x1 £20
x2 £25
x1, x2≥0
F(x) = 7x1 +8x2 ® max
Приведем заданную модель к каноническому виду, введя свободные переменные x3, x4, x5, превращающие неравенства в равенства. Переменные x3, x4, x5 входят в уравнение с коэффициентом единица и только один раз:
5x1 + 3x2+x3 =150
x1+x4=20
x2+x5 =25
x1, x2, x3, x4, x5≥0
F(x)= 7x1 +8x2 +x3 +x4 +x5
x3, x4, x5 – базисные переменные; x1, x2 – свободные переменные.
Составим симплекс – таблицу, соответствующую каноническому виду:
Таблица 2 – Итерация 1
| Базис | Свободные чл. | X 1 | X 2 | X 3 | X 4 | X 5 |
| X 3 | 150 | 5 | 3 | 1 | 0 | 0 |
| X 4 | 20 | 1 | 0 | 0 | 1 | 0 |
| X 5 | 25 | 0 | 1 | 0 | 0 | 1 |
| F(x) | 0 | -7 | -8 | 0 | 0 | 0 |
Построив первую таблицу, проверяем ее на оптимальность, то есть в последней строке таблицы ищем максимально отрицательный элемент, в нашем случае – это -8. Из этого следует, что столбец х2 становится ключевым. Далее в столбце х2 ищем ключевую строку: свободный член делим на элемент столбца х2, находящийся в этой же строке. Из полученных делений выбираем минимальное, у нас это будет 25. То есть строка, в которой получилось минимальное частное, будет являться ключевой (строка х5). А элемент, стоящий на пересечении ключевого столбца и ключевой строки будет являться ключевым элементом, в нашей задаче это будет 1.
Строим новую таблицу, следуя алгоритму, приведенному выше.
Таблица 3 – Итерация 2
| Базис | Свободные | X 1 | X 2 | X 3 | X 4 | X 5 |
| X 3 | 75 | 5 | 0 | 1 | 0 | -3 |
| X 4 | 20 | 1 | 0 | 0 | 1 | 0 |
| X 2 | 25 | 0 | 1 | 0 | 0 | 1 |
| F(x) | 200 | -7 | 0 | 0 | 0 | 8 |
Таблицу 3 проверяем на оптимальность таким же способом, что и изначальную таблицу. Находим ключевой элемент в таблице 3, и затем заново пересчитываем новую таблицу.
Таблица 4 – Итерация 3
| Базис | Свободные | X 1 | X 2 | X 3 | X 4 | X 5 |
| X 1 | 15 | 1 | 0 | 0,2 | 0 | -0,6 |
| X 4 | 5 | 0 | 0 | -0,2 | 1 | 0,6 |
| X 2 | 25 | 0 | 1 | 0 | 0 | 1 |
| F(x) | 305 | 0 | 0 | 1,4 | 0 | 3,8 |
В нашем случае таблица 4 стала окончательным решением, так как в последней строке нет отрицательных чисел, из этого следует, что мы нашли оптимальный способ решение поставленной задачи.
X 1=15; X 2=25; Fmax=305.
Для достижения максимальной прибыли, равной 305 руб., необходимо производить 15 изделий первого вида и 25 изделий второго вида в день.
Похожие работы
... . 1.3. Построение ограничений и градиента целевой функции : 1.4. Область допустимых решений – отрезок AB. 1.5. Точка А – оптимальная. Координаты т. А: ; ; . 2. Решение задачи линейного программирования симплекс-методом. Прямая задача. Задачу линейного программирования для любой вершины в компактной форме можно представить в виде: Для получения используем алгоритм, приведённый в ...
... положит в такой симплекс-таблице текущие базисные переменные равными Ai,0, а свободные - нулю, то будет получено оптимальное решение. Практика применения симплекс метода показала, что число итераций, требуемых для решения задачи линейного программирования обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс метода превращаются в прямой ...
... 0 505/103 0 792/103 669/103 500/103 Анализ Таблицы 6 позволяет сделать вывод о допустимости и оптимальности базиса XБ4=(x5, x7, x1, x2, x4)T. 3.4 Результат решения задачи планирования производства В результате решения поставленной задачи симплекс-методом получили набор производимой продукции x=(x1, x2, x3, x4, x5)=( 15145/103, 8910/103, 0, 1250/103, 3255/103), который удовлетворяет всем ...
... - формула (1.2), ограничений не отрицательности переменных (есть, нет) - формула (1.3) (1.1) i = 1,… m (1.2) (1.3) Алгоритм решения задач линейного программирования требует приведения их постановки в канонический вид, когда целевая функция ...
0 комментариев