Реферат: Линейное программирование, решение задач симплексным методом

Х₁ = 20, Х₂ = 14,

при этом Z_max = 10 * 20 + 5 * 14 = 270 руб.

Таким образом, mах прибыль в 270 руб. будет получена, если предприятие произведет 20 изделий вида А и 14 изде­лий вида В.

Отыскание максимума линейной функции

В основе симплексного метода решения задач линейного программирования лежит с некоторыми дополнениями разоб­ранный ранее метод последовательных исключений, представ­ляющий собой совокупность удобных вычислительных алгорит­мов, построенных на последовательном применении тождествен­ных (симплексных) преобразований системы уравнений.

Добавляя к левой части неравенств

14X₁ + 5Х₂ ≤ 350,

14Х₁ + 8Х₂ ≤ 392,

6Х₁ + 12Х₂ ≤ 408,

некоторую нео­трицательную величину Y_j ≥ 0 (i = 1, 2, 3), (1.2)

называемую выравнивающей или базисной переменной, пре­вратим их в уравнения:

14	Х1 + 5Х2 + У1	= 350,
14	Х1 + 8Х2	+ У2	= 392,
6	X1 + 12Х2	+ У3	= 408,
-10	X1 - 5Х2	+ Z = 0.

(1.3)

При этом можно показать, что каждому решению систе­мы неравенств (1.1) соответствует единственное решение си­стемы уравнений (1.3) и неравенств (1.2) и наоборот.

Каждая из переменных Y_1, У₂ , У₃ входит только в одно уравнение и зависит от переменных Х₁ и X₂ , которые мы на­зываем свободными.

Системе (1.3) соответствует исходное допустимое базис­ное решение X₁ = X₂ = 0;

Y₁ = 350; Y₂ = 392; Y₃ = 408 и Z = 0.

Выполняем первое тождественное преобразование системы уравнений (1.3). Выбираем разрешающий столбец, соот­ветствующий наименьшему отрицательному элементу в Z стро­ке, ибо теоретически установлено, что при этом можно ожи­дать при прочих равных условиях большего увеличения фун­кции Z. Правую часть уравнений делим на элементы разре­шающего столбца и выбираем наименьшее положительное отношение, соответствующее разрешающей строке (уравне­нию). На пересечении выделенных столбца и строки стоит разрешающее число.

Первое уравнение делим на разрешающее число и вы­писываем получившееся уравнение. Умножая это уравнение на 14, 6 и -10 и вычитая соответственно из 2-го, 3-го и 4-го уравнений системы (1.3), придем к следующей системе (1.4):

X1 +	5/14	X2 + 1/4 Y1 = 25,
3	Х2 – Y1 + Y2	« 1 2 3 4 5 6 7 8 » К-во Просмотров: 749 Бесплатно скачать Реферат: Линейное программирование, решение задач симплексным методом >>> Скачать <<< Меню Поиск