Понятия линейного программирования

 

3. Все коэффициенты в строке целевой функции – неположительные  ,  следовательно выполнены условия оптимальности решения
4. В столбце свободных членов есть отрицательный элемент , следовательно, выделенное базисное решение не является допустимым (так как все неизвестные должны быть неотрицательными). Строку с отрицательным свободным членом назовём «разрешающей».
5. Находим в разрешающей строке отрицательные элементы. Если таковых нет, задача решения не имеет.
6. В разрешающей строке есть отрицательные элементы . Составляем соотношения коэффициентов целевой функции (они не положительные) к отрицательным элементам разрешающей строки и находим среди этих отношений наименьшее:

.

Столбец коэффициентов в ограничениях задачи с наименьшим отношением назовём  «разрешающим».

7. На пересечении разрешающей строки и разрешающего столбца находится отрицательный разрешающий элемент (в таблице условно выделен элемент –a₃₁). Производим преобразование Гаусса-Жордана с найденным разрешающим элементом.
8. В результате этого преобразования коэффициенты при неизвестных в строке целевой функции останутся неположительными, а число отрицательных элементов в столбце свободных членов уменьшится.
9. Через конечное число шагов или будет получено оптимальное решение, или же будет установлено, что допустимых (неотрицательных) решений нет.

Существует целый класс задач (типа задачи о диете), условия которых  естественным образом формулируются  сразу во 2-й стандартной форме. Для решения таких задач двойственный симплекс метод более удобен, чем  обычный алгоритм.

 

 

2. Практическая часть.

 

1. Решение задачи линейного программирования.
• Графический метод.

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

      

x1	0	2
x2	3	1

     

x1	2	3
x2	4	6

x1	4	4
x2	0	3

x1	0	7
x2	5	5

     - ось Ох₂

- ось Ох₁

 

Рассмотрим целевую функцию  задачи Z = 2x₁+x₂ → max.

Построим прямую, отвечающую значению функции Z = 0: Z = 2x₁+x₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области.

Так как точка D получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим: x₁ = 2.75, x₂ = 2.25

Откуда найдем максимальное значение целевой функции:

Z_max = 2·2.75 + 1·2.25 = 7.75

Рассмотрим целевую функцию  задачи Z = 2x₁+x₂ → min.

Построим прямую, отвечающую значению функции Z = 0: Z = 2x₁+x₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области.

Так как точка A получена в результате пересечения прямых (1) и (4), то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим: x₁ = 0.4286, x₂ = 0.8571

Откуда найдем минимальное значение целевой функции:

Z_min = 2·0.4286 + 1·0.8571 = 1.71

Ответ: Z_max = 7.75; Z_min = 1.71

 

• метод симплекс-таблица.

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

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

Введем искусственные  переменные x: в 1-м равенстве вводим переменную y₁;  в 4-м равенстве вводим переменную y₂;

Из уравнений выражаем искусственные переменные y₁,y₂:

y₁== 3-x₁-3x₂+x₃

y₂=0-2x₁+x₂+x₆

Составим новую линейную функцию h=-(y₁+y₂) .

h=-(3-x₁-3x₂+x₃+0-2x₂+x₆)=-(3-3x₁-2x₂+x₃+x₆)=-3-(-3x₁-2x₂+x₃+x₆)

h=-3-(-3x₁-2x₂+x₃+x₆)

Для постановки задачи на максимум целевую функцию запишем так:

Z=0-(-2x₁-x₂) => max

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

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

y₁, x₄, x₅, y₂,

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

X1 = (0,0,0,6,5,0,3,0)

 

 

 

 

Базис	Свободные член	Переменные								Оценочные отношения
		x1	x2	x3	x4	x5	x6	y1	y2
y1	3	1	3	-1	0	0	0	1	0	3
x4	6	3	-1	0	1	0	0	0	0	2
x5	5	1	1	0	0	1	0	0	0	5
y2	0	2	-1	0	0	0	-1	0	1	0
z	0	-2	-1	0	0	0	0	0	0
h	-3	-3	-2	1	0	0	1	0	0

 

 

 

 

 

 

 

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

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

Итерация №1.

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

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

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

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

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

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

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

max=[3, 2,5,0]=0

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

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

 

 

 

 

 

 

Базис	Свободные член	Переменные								Оценочные отношения
		x1	x2	x3	x4	x5	x6	y1	y2
y1	3	1	3	-1	0	0	0	1	0	3
x4	6	3	-1	0	1	0	0	0	0	2
x5	5	1	1	0	0	1	0	0	0	5
y2	0	2	-1	0	0	0	-1	0	1	0
z	0	-2	-1	0	0	0	0	0	0
h	-3	-3	-2	1	0	0	1	0	0

 

 

 

 

 

 

4. Пересчет симплекс-таблицы.

Формируем следующую часть  симплексной таблицы.

Вместо переменной y₂ в план 1 войдет переменная x₁

Строка, соответствующая  переменной x₁ в плане 1, получена в результате деления всех элементов строки y₂ плана 1 на разрешающий элемент =0

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₂ плана 1 записываем нули.

Таким образом, в новом  плане 1 заполнены строка x₁ и столбец x₁ .

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

Базис	Свободные член	Переменные								Оценочные отношения
		x1	x2	x3	x4	x5	x6	y1	y2
y1	3	0	3,5	-1	0	0	0,5	1	-0,5
x4	6	0	0,5	0	1	0	1,5	0	-1,5
x5	5	0	1,5	0	0	1	0,5	0	-0,5
x1	0	1	-0,5	0	0	0	-0,5	0	0,5
z	0	0	-2	0	0	0	-1	0	1
h	-3	0	-3,5	1	0	0	-0,5	0	1,5