Изменение правых частей ограничений

Заменим в правой части второго ограничения 780 на 860 и проверим, как это отразится на текущем решении.

Из соотношения двойственности новые решения можно получить, используя последнюю симплекс-таблицу.

Из последней симплекс-таблицы вектор-столбец базисных переменных равен произведению обратной матрицы на столбец новой правой части.

х₁ 3 -1 0 300 40

х₂ = -2 1 0 860 = 260

х₅ -120 30 1 14400 4 200

 

 

Все элементы правой части таблицы после изменения остались неотрицательными состав базисных переменных не изменился, но они приняли новое значение:

х₁ = 40, х₂ = 260, х₅ = 4200.

 

Новое значение функции: Z=0, 16∙ 40 + 0, 2∙ 260 =58, 4

Теперь заменим 780 на 910.

х₁ 3 -1 0 300 -10

х₂ =- 2 1 0 910 = 310

х₅ -120 30 1 14400 5700

 

Т.к. х₁ имеет отрицательное значение, то решение не допустимое и необходимо выполнить симплекс-итерацию для получения допустимого решения.

В симплекс-таблице для последнего оптимального решения надо записать значение Z, найдем его подставки в Z-уравнение другие новые значения х₁ и х₂:

Z=0, 16∙ х₁ + 0, 2 ∙ х₂ = 0, 16 ∙ (-10)+310∙ 0, 2 = 60, 4

 

Симплекс-таблица примет вид:

Таблица 4

 

Переменные Базис	х1	х2	х3	х4	х5	Решение
Х1				-1	0	-10←
Х2			-2	1
Х5			-120
Z			2⁄ 25	1⁄ 25 ↑		60, 4

 

 

Применим двойственный симплекс-метод.

Когда решение прямой задачи неоптимальное, решение двойственной задачи недопустимое, поэтому оптимальному решению прямой задачи соответствует допустимое решение двойственной задачи.

При использовании двойственного симплекс-метода сначала получаем недопустимое, но «лучшее оптимальное», решение. (При обычном симплекс-методе сначала находим допустимое, но не оптимальное решение). Когда полученное решение оказывается допустимым, итерационный процесс вычислений заканчивается, так как это решение является и оптимальным.

Как и обычный симплекс-метод, двойственный метод основан на условии оптимальности и допустимости.

Условие допустимости. В качестве исключаемой переменной выбирается наибольшая по абсолютной величине отрицательная базисная переменная. В нашем примере это базисная переменная х₁ с коэффициентом – 10

Условие оптимальности. Включаемая в базис переменная выбирается из числа небазисных переменных следующим образом. В столбце Решение выбирается наименьшее по абсолютной величине отрицательное значение. В нашем случаи вводимой переменной будет х₄. Следовательно ведущий элемент будет на пересечении х₄ и х₁, он равен – 1.

После выбора включаемой в базис и исключаемой переменных для получения следующего решения осуществляется обычная операция преобразования строк симплекс-таблицы.

 

 

Таблица 5

 

Пременные Базис	х1	х2	х3	х4	х5	Решение
Х4	-1		-3
Х2
Х5			-40
Z	1⁄ 25		1⁄ 5

 

 

Мы получили новое допустимое и оптимальное решение: х₁=0, х₂=300, х₃=0, х₄= 10, х₅ = 15000, Z= 0, 16 ∙ 0 + 0, 2 ∙ 300 = 60

 

Добавление нового ограничения

Рассмотрим вариант изменения условий задачи, влияющий на допустимость решения, состоящий в добавлении нового ограничения.

Пусть спрос на товар х₁ велик и фирма решила закупить его не менее чем на 130 тыс. руб. т.е. в условиях задачи появилось новое ограничение х₁ ≥ 130, это ограничение касается базисной переменной в оптимальном решении, значит надо проверить как изменится полученное ранее решение.

Введем новую дополнительную переменную х₆ и новое ограничение в стандартной форме запишется как: -х₁ + х₆≤ -130, в текущем решении х₁ является базисной переменной, поэтому необходимо выразить ее через небазисные. В таблице для текущего оптимального решения х₁ уравнение имеет вид:

х₁ + 3х₃ –х₄ = 120, х₁ =120 – 3х₃ + х₄ таким образом новое ограничение, где фигурируются только текущие небазисные переменные можно записать как:

-120 + 3х₃ –х₄ + х₆ = -130

или

3х₃ –х₄ + х₆ = -10

Поскольку х₄ = 0, х₃ = 0, х₆ = -10, значит решение будет недопустимым, а таблица примет вид:

 

Таблица 6

 

Переменные Базис	х1	х2	х3	х4	х5	х6	Решение
Х1				-1
Х2			-2
Х5			-120	30
Х6				-1			-10←
Z			2⁄ 25	1⁄ 25 ↑			55, 2

 

Вводим в базис х₄ и выводим х₆

 

Таблица 7

 

Переменные Базис	х1	х2	х3	х4	х5	х6	Решение
Х1						-1
Х2
Х5			-30	0
Х4			-3	1		-1
Z			2⁄ 25			1⁄ 25	54, 8

 

Новое решение х₁=130, х₂=170, х₃=0, х₄=10, х₅=1500, х₆=0.

Z=0, 16∙ 130+ 0, 2 ∙ 170=54, 8 это решение хуже чем, то, которое соответствовало условиям задачи до введения нового ограничения.

 

2. Изменения условий задачи влияющих на оптимальность решения.

⇐ Предыдущая1234567Следующая ⇒

Поделиться:

Популярное:

1. Do //внешний цикл - изменение аргумента
2. АВТОМАТИЧЕСКОЕ ИЗМЕНЕНИЕ ОТНОСИТЕЛЬНЫХ ССЫЛОК ПРИ КОПИРОВАНИИ И ПЕРЕМЕЩЕНИИ ФОРМУЛ
3. Администрации станции и цеха – «Практическое изменение
4. Анализ и изменение структуры имущества в динамике
5. Болезнь - изменение спектра вибраций
6. Введение должно состоять из следующих частей.
7. Виды издержек и их изменение в краткосрочном периоде
8. Виды ограничений (обременений) прав на земельные участки. Ограничения (обременения) прав на земельные участки, подлежащие государственной регистрации.
9. Военная реформа: изменение системы военного управ-я, комплектования и обеспечения Вооруженных Сил. Устав о воинской повинности 1874 г. Военно-судебная реформа 1867 г.
10. Возникновение, изменение и прекращение обязанности по уплате налога и сбора.
11. Возникновение, изменение и прекращение финансовых правоотношений
12. Вопрос о классификации частей речи в русской грамматической литературе