Функция, максимум которой надо найти с помощью симплекс метода

F = 6*x1 + 2*x2 + 5/2*x3 + 4*x4

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

5*x1 + x2 + 2*x4 <= 1000

4*x1 + 2*x2 + 2*x3 + x4 <= 600

x1 + 2*x3 + x4 <= 150

 

Вводим указанные данные в "симплекс метод онлайн"

Получим подробное решение:

Результат решения симплекс методом

Найдем максимальное значение ф-ции
                  5*x3       
F = 6*x1 + 2*x2 + ---- + 4*x4
                   2         
при условиях
5*x1 + x2 + 2*x4 <= 1000
4*x1 + 2*x2 + 2*x3 + x4 <= 600
x1 + 2*x3 + x4 <= 150

Быстрый ответ

x1 = 0, x2 = 225, x3 = 0, x4 = 150, x5 = 475, x6 = 0, x7 = 0
Fmax=1050

Подробное решение

Приведём систему условий к каноническому виду:
Там, где стоит знак неравенства "<=" или "=", то к левой части добавляем еще одну новую переменную xi со знаком "+", а если знак неравенства ">=", то xi со знаком "-"; если же у условия знак "=", то ничего не добавляем. (xi >= 0)
Получаем систему ур-ний (1):
5*x1 + x2 + 2*x4 + x5 = 1000
4*x1 + 2*x2 + 2*x3 + x4 + x6 = 600
x1 + 2*x3 + x4 + x7 = 150
 
Находим базисные переменные:
Все переменные, которые входят один раз в систему уравнений и они с коэфициентом 1, называются базисными переменными.
В нашем случае выберем такие:
x5, x6, x7
 
Составляем начальную таблицу:
* Вдоль каждой строки в таблице проставлены коэфициенты при неизвестных в уравнениях-условиях (1)
* В первом столбце проставлены базисные переменные
* В последнем столбце свободные члены
* В последней строке стоят коэф. при неизвестных из функции F с обратным знаком
Получаем таблицу:
+----------------+----+----+------+----+----+----+----+------------------+
| Basovie perem. | x1 | x2 |  x3  | x4 | x5 | x6 | x7 | Svobodnie chleni |
+================+====+====+======+====+====+====+====+==================+
| x5             | 5  | 1  | 0    | 2  | 1  | 0  | 0  | 1000             |
+----------------+----+----+------+----+----+----+----+------------------+
| x6             | 4  | 2  | 2    | 1  | 0  | 1  | 0  | 600              |
+----------------+----+----+------+----+----+----+----+------------------+
| x7             | 1  | 0  | 2    | 1  | 0  | 0  | 1  | 150              |
+----------------+----+----+------+----+----+----+----+------------------+
| F              | -6 | -2 | -5/2 | -4 | 0  | 0  | 0  | 0                |
+----------------+----+----+------+----+----+----+----+------------------+
Начинаем применять симплекс метод, а именно
* Стремимся, чтобы в последней строке остались только положительные элементы или равные нулю
* Стремимся, чтобы в столбце свободных членов остались только положительные элементы или равные нулю
Для этого будем
* Находить наибольшее значение по модулю в последней строке,
соотв. элемент будет задавать ведущий столбец
* Находим минимальное отрицательное отношение элементов свободного столбца к элементам ведущего столбца,
находим соотв. ведущую строку
* На пересечении ведущей строки и ведущего столбца находится ведущий элемент
* Для всех строк кроме ведущей делаем преобразование:
[новая строка] = [старая строка] - E[il] / E[ll] * [ведущая строка],
где
E[il] - эл-нт при пересечение ведущего столбца и текущей строки
E[ll] - ведущий элемент
* Элементы ведущей строки делим на ведущий элемент
* На место базисного элемента в ведущей строке ставим переменную из ведущего столбца
Итак, проделываем вышеописанные шаги:
     |                                                                     
     v                                                                    
 --> E <-- - так обозначается ведущий элемент
     ^                                                                    
     |                                                                
 
1 шаг.
Базисные переменные x5, x6, x7
+-------------+-----------+----+------+----+----+----+----+-------------+
|   Basovie   |    x1     | x2 |  x3  | x4 | x5 | x6 | x7 |  Svobodnie  |
|   perem.    |           |    |      |    |    |    |    |   chleni    |
+=============+===========+====+======+====+====+====+====+=============+
| x5          | 5         | 1  | 0    | 2  | 1  | 0  | 0  | 1000        |
+-------------+-----------+----+------+----+----+----+----+-------------+
| x6          | 4         | 2  | 2    | 1  | 0  | 1  | 0  | 600         |
+-------------+-----------+----+------+----+----+----+----+-------------+
|             |     |     |    |      |    |    |    |    |             |
|             |     v     |    |      |    |    |    |    |             |
| x7          | --> 1 <-- | 0  | 2    | 1  | 0  | 0  | 1  | 150         |
|             |     ^     |    |      |    |    |    |    |             |
|             |     |     |    |      |    |    |    |    |             |
+-------------+-----------+----+------+----+----+----+----+-------------+
| F           | -6        | -2 | -5/2 | -4 | 0  | 0  | 0  | 0           |
+-------------+-----------+----+------+----+----+----+----+-------------+
Базисное решение x1 = 0, x2 = 0, x3 = 0, x4 = 0, x5 = 1000, x6 = 600, x7 = 150
2 шаг.
Базисные переменные x5, x6, x1
+-------------+----+-----------+------+----+----+----+----+-------------+
|   Basovie   | x1 |    x2     |  x3  | x4 | x5 | x6 | x7 |  Svobodnie  |
|   perem.    |    |           |      |    |    |    |    |   chleni    |
+=============+====+===========+======+====+====+====+====+=============+
| x5          | 0  | 1         | -10  | -3 | 1  | 0  | -5 | 250         |
+-------------+----+-----------+------+----+----+----+----+-------------+
|             |    |     |     |      |    |    |    |    |             |
|             |    |     v     |      |    |    |    |    |             |
| x6          | 0  | --> 2 <-- | -6   | -3 | 0  | 1  | -4 | 0           |
|             |    |     ^     |      |    |    |    |    |             |
|             |    |     |     |      |    |    |    |    |             |
+-------------+----+-----------+------+----+----+----+----+-------------+
| x1          | 1  | 0         | 2    | 1  | 0  | 0  | 1  | 150         |
+-------------+----+-----------+------+----+----+----+----+-------------+
| F           | 0  | -2        | 19/2 | 2  | 0  | 0  | 6  | 900         |
+-------------+----+-----------+------+----+----+----+----+-------------+
Базисное решение x1 = 150, x2 = 0, x3 = 0, x4 = 0, x5 = 250, x6 = 0, x7 = 0
3 шаг.
Базисные переменные x5, x1, x2
+-------------+----+----+-----+-----------+----+------+----+-------------+
|   Basovie   | x1 | x2 | x3  |    x4     | x5 |  x6  | x7 |  Svobodnie  |
|   perem.    |    |    |     |           |    |      |    |   chleni    |
+=============+====+====+=====+===========+====+======+====+=============+
| x5          | 0  | 0  | -7  | -3/2      | 1  | -1/2 | -3 | 250         |
+-------------+----+----+-----+-----------+----+------+----+-------------+
| x2          | 0  | 1  | -3  | -3/2      | 0  | 1/2  | -2 | 0           |
+-------------+----+----+-----+-----------+----+------+----+-------------+
|             |    |    |     |     |     |    |      |    |             |
|             |    |    |     |     v     |    |      |    |             |
| x1          | 1  | 0  | 2   | --> 1 <-- | 0  | 0    | 1  | 150         |
|             |    |    |     |     ^     |    |      |    |             |
|             |    |    |     |     |     |    |      |    |             |
+-------------+----+----+-----+-----------+----+------+----+-------------+
| F           | 0  | 0  | 7/2 | -1        | 0  | 1    | 2  | 900         |
+-------------+----+----+-----+-----------+----+------+----+-------------+
Базисное решение x1 = 150, x2 = 0, x3 = 0, x4 = 0, x5 = 250, x6 = 0, x7 = 0
И на 4-м шаге
+----------------+-----+----+------+----+----+------+------+------------------+
| Basovie perem. | x1  | x2 |  x3  | x4 | x5 |  x6  |  x7  | Svobodnie chleni |
+================+=====+====+======+====+====+======+======+==================+
| x5             | 3/2 | 0  | -4   | 0  | 1  | -1/2 | -3/2 | 475              |
+----------------+-----+----+------+----+----+------+------+------------------+
| x2             | 3/2 | 1  | 0    | 0  | 0  | 1/2  | -1/2 | 225              |
+----------------+-----+----+------+----+----+------+------+------------------+
| x4             | 1   | 0  | 2    | 1  | 0  | 0    | 1    | 150              |
+----------------+-----+----+------+----+----+------+------+------------------+
| F              | 1   | 0  | 11/2 | 0  | 0  | 1    | 3    | 1050             |
+----------------+-----+----+------+----+----+------+------+------------------+
видим, что в последней строке остались только положительные элементы или равные нулю,
и в столбце свободных членов остались только положительные элементы или равные нулю, зн.
Оптимальное решение x1 = 0, x2 = 225, x3 = 0, x4 = 150, x5 = 475, x6 = 0, x7 = 0
Максимальное значение
                  5*x3       
F = 6*x1 + 2*x2 + ---- + 4*x4
                   2         
Подставляем оптимальное решение, получим:
Fmax=1050