перейти к решению своей задачи
| Найдем наибольшее значение линейной функции
|
| при следующих ограничениях
|
|
|
| x1
| +
|
| x2
| 
|
|
| -
|
| x1
|
| -2
| x2
|
| -2
|
|
|
| x1
| +
|
| x2
|
|
|
|
|
| x1
| +
| 1/3
| x2
| 
|
|
| В двух словах смысл того, что мы будем делать. Нам необходимо найти начальное опорное (абсолютно произвольное) решение для функции L, которое бы удовлетворяло системе наложенных ограничений. Далее, применяя симплекс таблицы, мы будем получать решения, при которых значение функции будет, как минимум, не убывать. И так до тех пор, пока не достигнем оптимально решения, при котором функция достигает своего максимума. Если, конечно, рассматриваемая нами линейная функция обладаем максимальным значением при заданной системе ограничений. Перед применением симплекс таблиц, необходимо преобразовать систему линейных ограничений и рассматриваемую нами функцию L к вполне определенному виду.
|
|
· Свободные члены системы ограничений должны быть неотрицательными.
|
| Умножим коэффициенты ограничения 2 на -1, свободный член ограничения станет положительным.
|
|
|
|
| x1
| +
|
| x2
|
|
|
|
|
| x1
| +
|
| x2
|
|
|
|
|
| x1
| +
|
| x2
|
|
|
|
|
| x1
| +
| 1/3
| x2
|
|
|
| Свободные члены системы ограничений неотрицательные.
|
|
· Система ограничений должна быть приведена к каноническому виду.
|
| К левой части неравенства 1 системы ограничений прибавляем неотрицательную переменную x3 - преобразуем неравенство 1 в равенство.
|
| От левой части неравенства 2 системы ограничений отнимаем неотрицательную переменную x4 - преобразуем неравенство 2 в равенство.
|
| К левой части неравенства 3 системы ограничений прибавляем неотрицательную переменную x5 - преобразуем неравенство 3 в равенство.
|
| От левой части неравенства 4 системы ограничений отнимаем неотрицательную переменную x6 - преобразуем неравенство 4 в равенство.
|
|
|
|
| x1
| +
|
| x2
| +
|
| x3
|
|
|
|
|
|
|
|
|
| =
|
|
|
|
| x1
| +
|
| x2
|
|
|
| -
|
| x4
|
|
|
|
|
|
| =
|
|
|
|
| x1
| +
|
| x2
|
|
|
|
|
|
| +
|
| x5
|
|
|
| =
|
|
|
|
| x1
| +
| 1/3
| x2
|
|
|
|
|
|
|
|
|
| -
|
| x6
| =
|
|
| Система ограничений приведена к каноническому виду, т.е. все условия системы представляют собой уравнения.
|
|
· Определимся с начальным опорным решением.
|
| Наличие единичного базиса в системе ограничений позволяет легко найти начальное опорное решение. Рассмотрим подробнее:
|
| Переменная x3 входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е x3 - базисная переменная.
|
| В уравнении 2 нет переменной, которая входила бы в него с коэффициентом 1, а в остальные уравнения системы входила бы с коэффициентом ноль. Добавим к данному уравнению искусственную переменную r1. Очевидно, переменная r1 будет являться базисной переменной, т.к. входит в уравнение 2 с коэффициентом 1 и не входит в оставшиеся уравнения системы ограничений.
|
| Переменная x5 входит в уравнение 3 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е x5 - базисная переменная.
|
| В уравнении 4 нет переменной, которая входила бы в него с коэффициентом 1, а в остальные уравнения системы входила бы с коэффициентом ноль. Добавим к данному уравнению искусственную переменную r2. Очевидно, переменная r2 будет являться базисной переменной, т.к. входит в уравнение 4 с коэффициентом 1 и не входит в оставшиеся уравнения системы ограничений.
|
|
|
|
| x1
| +
|
| x2
| +
|
| x3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| =
|
|
|
|
| x1
| +
|
| x2
|
|
|
| -
|
| x4
|
|
|
|
|
|
| +
|
| r1
|
|
|
| =
|
|
|
|
| x1
| +
|
| x2
|
|
|
|
|
|
| +
|
| x5
|
|
|
|
|
|
|
|
|
| =
|
|
|
|
| x1
| +
| 1/3
| x2
|
|
|
|
|
|
|
|
|
| -
|
| x6
|
|
|
| +
|
| r2
| =
|
|
| Переменные, которые не являются базисными называются свободными переменными. Приравняв свободные переменные нулю в получившийся системе ограничений мы получим начальное решение.
|
X нач = (0, 0, 10, 0, 10, 0, 2, 1)
| Для получения единичного базиса нам пришлось ввести искусственные переменные, поэтому наше начальное решение является псевдорешением.
|
| Для нахождения начального опорного решения функции L, сначала придется решить вспомогательную задачу. Введем в рассмотрение вспомогательную функцию W:
|
| Найдем наибольшее значение функции W. Схема решения вспомогательной задачи абсолютно аналогична схеме описанной выше. Есть только одно исключение: вспомогательная задача всегда имеет решение. В процессе решения данной задачи возможны два варианта. Если максимальное значение вспомогательной функции W равно нулю, т.е. все искусственные переменные обращаются в нуль - это будет свидетельствовать о том, что мы нашли начальное опорное решение функции L. В противном случае, не существует решений, удовлетворяющих системе ограничений нашей задачи.
|
|
· Функция L и вспомогательная функция W не должны содержать базисных переменных.
|
| Из уравнения 2 последней системы выразим r1 и подставим в выражение функции W, получим
|
| W =
| -2
| + x1
| + 2 x2
| - x4
| - r2
|
| Из уравнения 4 последней системы выразим r2 и подставим в выражение функции W, получим
|
| W =
| -3
| + 2 x1
| + 7/3 x2
| - x4
| - x6
|
| Значение функции W для начального решения: W (X нач) = -3
|
| Вернемся к рассмотрению функции L.
|
| Функция L и вспомогательная функция W не содержат базисных переменных.
|
| Для составления начальной симплекс таблицы мы выполнили все условия.
|
| Обратите внимание: При составлении исходной симплекс таблицы, коэффициенты при переменных функции L записываются с противоположными знаками, а свободный член со своим знаком. Для функции W правило аналогичное.
|
| За ведущий выберем столбец 2, так как -7/3 наименьший элемент в W строке. Элемент W строки, принадлежащий столбцу свободных членов не рассматриваем.
|
| За ведущую выберем строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для 2 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 2.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| r1
| r2
| свободные члены
| отношение
|
| x3
|
|
|
|
|
|
|
|
|
|
|
| r1
|
|
|
| - 1
|
|
|
|
|
|
|
| x5
|
|
|
|
|
|
|
|
|
|
|
| r2
|
| |
|
|
| - 1
|
|
|
|
|
| L
| - 1
| - 2
|
|
|
|
|
|
|
| -
|
| W
| - 2
| |
|
|
|
|
|
| - 3
| -
|
| Разделим элементы строки 2 на 2.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| r1
| r2
| свободные члены
| отношение
|
| x3
|
|
|
|
|
|
|
|
|
|
|
| r1
| |
|
| |
|
| |
|
|
|
| x5
|
|
|
|
|
|
|
|
|
|
|
| r2
|
| |
|
|
| - 1
|
|
|
|
|
| L
| - 1
| - 2
|
|
|
|
|
|
|
| -
|
| W
| - 2
| |
|
|
|
|
|
| - 3
| -
|
| От элементов строки 1 отнимает соответствующие элементы строки 2, умноженные на 2.
|
| От элементов строки 3 отнимает соответствующие элементы строки 2.
|
| От элементов строки 4 отнимает соответствующие элементы строки 2.
|
| От элементов строки L отнимает соответствующие элементы строки 2, умноженные на -2.
|
| От элементов строки W отнимает соответствующие элементы строки 2, умноженные на -7/3.
|
| Элементы столбца r1 можно не пересчитывать, так как переменная r1 больше не является базисной.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| r2
| свободные члены
|
| x3
|
|
|
|
|
|
|
|
|
| x2
| |
|
| |
|
|
|
|
| x5
| |
|
| |
|
|
|
|
| r2
| |
|
| |
| - 1
|
| |
| L
|
|
|
| - 1
|
|
|
|
|
| W
| |
|
| |
|
|
| |
X 1 = (0, 1, 8, 0, 9, 0, 2/3)
| W =
| -2/3
| + 5/6 x1
| + 1/6 x4
| - x6
|
| Значение функции W для данного решения: W (X 1) = -2/3
|
| За ведущий выберем столбец 1, так как -5/6 наименьший элемент в W строке. Элемент W строки, принадлежащий столбцу свободных членов не рассматриваем.
|
| За ведущую выберем строку 4, так как отношение свободного члена к соответствующему элементу выбранного столбца для 4 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 1.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| r2
| свободные члены
| отношение
|
| x3
|
|
|
|
|
|
|
|
| -
|
| x2
| |
|
| |
|
|
|
|
|
| x5
| |
|
| |
|
|
|
|
|
| r2
| |
|
| |
| - 1
|
| | |
| L
|
|
|
| - 1
|
|
|
|
| -
|
| W
| |
|
| |
|
|
| | -
|
| Разделим элементы строки 4 на 5/6.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| r2
| свободные члены
| отношение
|
| x3
|
|
|
|
|
|
|
|
| -
|
| x2
| |
|
| |
|
|
|
|
|
| x5
| |
|
| |
|
|
|
|
|
| r2
|
|
|
| |
| | | | |
| L
|
|
|
| - 1
|
|
|
|
| -
|
| W
| |
|
| |
|
|
| | -
|
| От элементов строки 2 отнимает соответствующие элементы строки 4.
|
| От элементов строки 3 отнимает соответствующие элементы строки 4, умноженные на 3/2.
|
| От элементов строки W отнимает соответствующие элементы строки 4, умноженные на -5/6.
|
| Элементы столбца r2 можно не пересчитывать, так как переменная r2 больше не является базисной.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| свободные члены
|
| x3
|
|
|
|
|
|
|
|
| x2
|
|
|
| |
| | |
| x5
|
|
|
| |
| | |
| x1
|
|
|
| |
| | |
| L
|
|
|
| - 1
|
|
|
|
| W
|
|
|
|
|
|
|
|
X 2 = (4/5, 3/5, 8, 0, 39/5, 0)
| Значение функции W для данного решения: W (X 2) = 0
|
| Строка W нам больше не нужна.
|
| · Мы нашли начальное опорное решение функции L.
|
X нач. = (4/5, 3/5, 8, 0, 39/5, 0)
| Значение функции для данного решения: L (X нач.) = 2
|
| За ведущий выберем столбец 4, так как -1 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу свободных членов не рассматриваем.
|
| За ведущую выберем строку 4, так как отношение свободного члена к соответствующему элементу выбранного столбца для 4 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 4.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| свободные члены
| отношение
|
| x3
|
|
|
|
|
|
|
|
|
| x2
|
|
|
| |
| | | -
|
| x5
|
|
|
| |
| | |
|
| x1
|
|
|
| |
| | |
|
| L
|
|
|
| - 1
|
|
|
| -
|
| Разделим элементы строки 4 на 1/5.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| свободные члены
| отношение
|
| x3
|
|
|
|
|
|
|
|
|
| x2
|
|
|
| |
| | | -
|
| x5
|
|
|
| |
| | |
|
| x1
|
|
|
|
|
| - 6
|
|
|
| L
|
|
|
| - 1
|
|
|
| -
|
| От элементов строки 1 отнимает соответствующие элементы строки 4.
|
| От элементов строки 2 отнимает соответствующие элементы строки 4, умноженные на -3/5.
|
| От элементов строки 3 отнимает соответствующие элементы строки 4.
|
| От элементов строки L отнимает соответствующие элементы строки 4, умноженные на -1.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| свободные члены
|
| x3
| - 5
|
|
|
|
|
|
|
| x2
|
|
|
|
|
| - 3
|
|
| x5
| - 1
|
|
|
|
|
|
|
| x4
|
|
|
|
|
| - 6
|
|
| L
|
|
|
|
|
| - 6
|
|
X 1 = (0, 3, 4, 4, 7, 0)
| Значение функции L для данного решения: L (X 1) = 6
|
| За ведущий выберем столбец 6, так как -6 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу свободных членов не рассматриваем.
|
| За ведущую выберем строку 1, так как отношение свободного члена к соответствующему элементу выбранного столбца для 1 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 6.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| свободные члены
| отношение
|
| x3
| - 5
|
|
|
|
|
|
| |
| x2
|
|
|
|
|
| - 3
|
| -
|
| x5
| - 1
|
|
|
|
|
|
| |
| x4
|
|
|
|
|
| - 6
|
| -
|
| L
|
|
|
|
|
| - 6
|
| -
|
| Разделим элементы строки 1 на 6.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| свободные члены
| отношение
|
| x3
| |
| |
|
|
| | |
| x2
|
|
|
|
|
| - 3
|
| -
|
| x5
| - 1
|
|
|
|
|
|
| |
| x4
|
|
|
|
|
| - 6
|
| -
|
| L
|
|
|
|
|
| - 6
|
| -
|
| От элементов строки 2 отнимает соответствующие элементы строки 1, умноженные на -3.
|
| От элементов строки 3 отнимает соответствующие элементы строки 1, умноженные на 3.
|
| От элементов строки 4 отнимает соответствующие элементы строки 1, умноженные на -6.
|
| От элементов строки L отнимает соответствующие элементы строки 1, умноженные на -6.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| свободные члены
|
| x6
| |
| |
|
|
| |
| x2
| |
| |
|
|
|
|
| x5
| |
| |
|
|
|
|
| x4
|
|
|
|
|
|
|
|
| L
|
|
|
|
|
|
|
|
X 2 = (0, 5, 0, 8, 5, 2/3)
| Значение функции L для данного решения: L (X 2) = 10
|
| Учитывая, что все x i 0 по условию задачи, наибольшее значение функции L равно свободному члену 10, т.е. мы получили оптимальное решение.
|
X опт 1 = (0, 5, 0, 8, 5, 2/3)
| Оптимальное решение не единственное, так как существует нулевой элемент L строки, который соответствует свободной переменной x 1.
|
| Решение единственное, если нули в L строке соответствуют только базисным переменным.
|
| Чтобы найти второе оптимальное решение, столбец 1 принимает за ведущий.
|
| За ведущую выберем строку 3, так как отношение свободного члена к соответствующему элементу выбранного столбца для 3 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 1.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| свободные члены
| отношение
|
| x6
| |
| |
|
|
| | -
|
| x2
| |
| |
|
|
|
|
|
| x5
| |
| |
|
|
|
| |
| x4
|
|
|
|
|
|
|
| -
|
| L
|
|
|
|
|
|
|
| -
|
| Разделим элементы строки 3 на 3/2.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| свободные члены
| отношение
|
| x6
| |
| |
|
|
| | -
|
| x2
| |
| |
|
|
|
|
|
| x5
|
|
| |
| |
| | |
| x4
|
|
|
|
|
|
|
| -
|
| L
|
|
|
|
|
|
|
| -
|
| От элементов строки 1 отнимает соответствующие элементы строки 3, умноженные на -5/6.
|
| От элементов строки 2 отнимает соответствующие элементы строки 3.
|
| базисные переменные
| x1
| x2
| x3
| x4
| x5
| x6
| свободные члены
|
| x6
|
|
| |
| |
| |
| x2
|
|
| |
| |
| |
| x1
|
|
| |
| |
| |
| x4
|
|
|
|
|
|
|
|
| L
|
|
|
|
|
|
|
|
| Нашли второе оптимальное решение.
|
X опт 2 = (10/3, 10/3, 0, 8, 0, 31/9)
| Теперь можем записать ответ.
|
| Общее решение записывается, как комбинация решений X опт 1 и X опт 2
|
| X опт = t1 * X опт 1 +t2 * X опт 2, где t1 + t2 = 1, t1 0, t2 0
|
2015-08-21
369
