Использование линейного программирования для решения задач оптимизации

х3 = 432 - 5х2 ≥ 0;                            х2 ≤ 432;

х4 = 424 - 4х2 ≥ 0; откуда                х2 ≤ 424;

х5 = 532- 3х2 ≥ 0;                             х2 ≤ 532.

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

Очевидно, что сохранение неотрицательности всех переменных возможно, если не нарушается ни одна из полученных границ. В данном примере наибольшее возможное значение для переменной х2 определяется как х2 = min {432/5, 106, 532/3} = 86. При х2 = 86 переменная х = 0 и переходит в не основные.

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

II шаг.

Основные переменные: х2, х4, х5.

Не основные переменные: х1, х.3 .

Выразим основные переменные через новые не основные, начиная с разрешающего уравнения(его используем для записи выражения для х2 ) :

х2 =86- 0,4 х1 - 0,2х3;

х4 =78 –1,4х1 + 0,8х3;

х 5=273 – 3,8х1 + 0,6х3.

Второе базисное решение Х2 = (0, 86, 0, 78, 273 ) является допустимым.

Выразив линейную функцию через не основные переменные на этом шаге, получаем:

F = 4320  + 14 x1-10 x3

Значение линейной функции F2 = F(X2) =  4320

Поскольку необходимо сохранять допустимость решений, то должны выполняться следующие неравенства(при этом х1 = 0 как не основная переменная):

х2 =86 - 0,2х3 ≥ 0;                           х3 ≤ 430;

х4 =78 + 0,8х3 ≥ 0; откуда              х3 ≤ -98;  (11)

х5 =273 + 0,6х3 ≥ 0.                        х3 ≤ -455.

Обнаруживаем возможность дальнейшего увеличения линейной функции за счёт переменной х1, входящей в выражение для F с положительным коэффициентом. Система уравнений (11) определяет наибольшее возможное значение для х5 :

Х3 = min {430,-98,-455} = -98 .

При х3 = -98 х4 = 0 переходит в неосновные переменные.

Разрешающим будет третье уравнение.

III шаг.

Основные переменные: х1, х2, х5.

Неосновные переменные: х4, х3.

Выразим основные переменные через неосновные:

х1= 56 – 3/7х3 -2/7х4;

х2 = 64 + 4/7х3 - 5/7х4;

х5 = 60 - 11/7х3 + 19/7х4.

Третье базисное решение Х3 = (56, 64,0, 0, 60) является допустимым.

Выразим линейную функцию через неосновные переменные:

F = 5104  -2 x3-10 x4.

Значение линейной функции F3 = F(X3) = 5104.

Учитывая, что все x i0, по условию задачи, наибольшее значение функции F равно свободному члену 5104, т.е. мы получили оптимальное решение.

Теперь можем записать ответ.

Ответ: максимальная прибыль от реализации продукции равна 5104 ден. ед. X опт = (56 , 64 , 0 , 0 , 60).

2 способ:симплекс-метод табличный

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

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

2x1+5x2≤432

3x1+4x2≤424

5x1+3x2≤532

2x1 + 5x2 + 1x3 + 0x4 + 0x5 = 432

3x1 + 4x2 + 0x3 + 1x4 + 0x5 = 424

5x1 + 3x2 + 0x3 + 0x4 + 1x5 = 532

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

x3, x4, x5,

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

X1 = (0,0,432,424,532)

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

№1

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai2

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

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

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

После преобразований получаем новую таблицу:

№2

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai1

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

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

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