Среди базисных переменных присутствуют отрицательные значения. Целевая функция не ограничена. Решения не существует.
В полученном плане среди значений базисных переменных имеются отрицательные значения. Поэтому функция цели F(X) не ограничена на множестве допустимых планов, т.е. F(X) → ∞ и задача не имеет решения.

Примечание:

1. По какому методу пересчитываются симплекс-таблицы?

Используется правило прямоугольника (метод жордановских преобразований).

2. Обязательно ли каждый раз выбирать максимальное значение из индексной строки?

Можно не выбирать, но это может привести к зацикливанию алгоритма.

3. В индексной строке в n-ом столбце нулевое значение. Что это означает?

Нулевые значения должны соответствовать переменным, вошедшим в базис. Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов.

Свободную переменную, соответствующую указанному столбцу, можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.

Построим двойственную задачу по следующим правилам.

1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.

2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.

3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.

Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.

---

Расширенная матрица A.

1	-2	0	0	-3
0	2	-3	0	5
0	0	-3	4	-7
1	0	0	4	5
1	2	3	4

Транспонированная матрица A^T.

1	0	0	1	1
-2	2	0	0	2
0	-3	-3	0	3
0	0	4	4	4
-3	5	-7	5

Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.
Неравенства, соединенные стрелочками (↔), называются сопряженными.

y₁+y₄≤1

-2y₁+2y₂≤2

-3y₂-3y₃≤3

4y₃+4y₄≤4

-3y₁+5y₂-7y₃+5y₄ → max

y₁ ≥ 0

y₂ ≥ 0

y₃ ≤ 0

y₄ ≤ 0

Исходная задача I		Двойственная задача II
x1 ≥ 0	↔	y1+y4≤1
x2 ≥ 0	↔	-2y1+2y2≤2
x3 ≥ 0	↔	-3y2-3y3≤3
x4 ≥ 0	↔	4y3+4y4≤4
x1+2x2+3x3+4x4 → min	↔	-3y1+5y2-7y3+5y4 → max
x1-2x2≥-3	↔	y1 ≥ 0
2x2-3x3≥5	↔	y2 ≥ 0
-3x3+4x4≤-7	↔	y3 ≤ 0
x1+4x4≤5	↔	y4 ≤ 0

---

Решение двойственной задачи дает оптимальную систему оценок ресурсов.

№ 31–40. Найдите целочисленное решение задачи графическим методом и методом Гомори.

36. 
    где .
    

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

Определим максимальное значение целевой функции F(X) = x₁+x₂ при следующих условиях-ограничений.

3x₁-x₂≤12

-x₁+2x₂≤8

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x₃. В 2-м неравенстве смысла (≤) вводим базисную переменную x₄.

3x₁-x₂+x₃ = 12

-x₁+2x₂+x₄ = 8

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

Решим систему уравнений относительно базисных переменных: x₃, x₄

Полагая, что свободные переменные равны 0, получим первый опорный план:

X0 = (0,0,12,8)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4
x3	12	3	-1	1	0
x4	8	-1	2	0	1
F(X0)	0	-1	-1	0	0

Переходим к основному алгоритму симплекс-метода.
Итерация №0.

1. Проверка критерия оптимальности

---

.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

min (- , 8 : 2 ) = 4

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	min
x3	12	3	-1	1	0	-
x4	8	-1	2	0	1	4
F(X1)	0	-1	-1	0	0

---

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x₄ в план 1 войдет переменная x₂.

Строка, соответствующая переменной x₂ в плане 1, получена в результате деления всех элементов строки x₄ плана 0 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x₂ записываем нули.

Таким образом, в новом плане 1 заполнены строка x₂ и столбец x₂. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B	x1	x2	x3	x4
12-(8 • -1):2	3-(-1 • -1):2	-1-(2 • -1):2	1-(0 • -1):2	0-(1 • -1):2
8 : 2	-1 : 2	2 : 2	0 : 2	1 : 2
0-(8 • -1):2	-1-(-1 • -1):2	-1-(2 • -1):2	0-(0 • -1):2	0-(1 • -1):2

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4
x3	16	5/2	0	1	1/2
x2	4	-1/2	1	0	1/2
F(X1)	4	-3/2	0	0	1/2

---

Смотрите также файлы

• Охарактеризуйте основные требования к выразительному чтению педагога, дошкольника и учащегося начальной школы.docx

• Вид практикитжірибе трі Студент ваше фио факультет Сестринское делоМейіргер ісі Курс 3 группатоп 329б количество часовСаат саны 150.docx

• Программное содержание.docx

• 1тапсырма. Бастауыш білім берудегі шетелдік тжірибеге шолу теориялы материалын зерделеіз. Зерделеген материал негізінде ментальді карта зірлеіз. 1кн.docx

• Тест начат Пятница, 30 декабря 2022, 02 19 Состояние.docx