Основные теоретические положения симплексного метода при решении задач линейного программирования

1. найти координаты точки пересечения прямых (4) и (6) - точки М (координаты вершин В и Е известны):

решая систему уравнений

20x+40y= 4000,

4x+4y= 600,

находим значения х и у: х = 100, у = 50;

2. вычислить значения z в точках В(0,100), E(150,0), M(100,50):

Z_B = 10000, Z_E = 12000, Z_M = 13000;

3. выбрать наибольшее:

Z_max = 13000.

 

Ответ: х = 100, у = 50, Z_max = 13000.

 

 

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

 

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

 

Затраты	Партия из 100 плит		Имеющиеся ресурсы  на месяц
	обычных	улучшенных
Материал (фунты)	20	40	4000
Время на прессование (часы)	4	6	900
Время на отделку (часы)	4	4	600
Средства (доллары)	30	50	6000

 

Найдем наибольшее значение линейной функции:

L = 80 x₁+100 x₂

при следующих ограничениях:

20x₁ + 40x₂  4000

4x₁ +  6x₂ 900

4x₁ +  4x₂ 600

30x₁ + 50x₂   6000

x₁ 0

x₂ 0

 

 

Решение:

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

• Свободные члены системы ограничений должны быть неотрицательными.
• Свободные члены системы ограничений неотрицательные.
• Система ограничений должна быть приведена к каноническому виду.

К левой части неравенства 1 системы ограничений прибавляем неотрицательную переменную x₃ - преобразуем неравенство 1 в равенство.

К левой части неравенства 2 системы ограничений прибавляем неотрицательную переменную x₄ - преобразуем неравенство 2 в равенство.

К левой части неравенства 3 системы ограничений прибавляем неотрицательную переменную x₅ - преобразуем неравенство 3 в равенство.

К левой части неравенства 4 системы ограничений прибавляем неотрицательную переменную x₆ - преобразуем неравенство 4 в равенство.

От левой части неравенства 5 системы ограничений отнимаем неотрицательную  переменную x₇ - преобразуем неравенство 5 в равенство.

От левой части неравенства 6 системы ограничений отнимаем неотрицательную  переменную x₈ - преобразуем неравенство 6 в равенство.

 

20

x1

+

40

x2

+

x3

=

4000

4

x1

+

6

x2

+

x4

=

900

4

x1

+

4

x2

+

x5

=

600

30

x1

+

50

x2

+

x6

=

6000

x1

-

x7

=

0

x2

-

x8

=

0

 

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

Определимся с начальным  опорным решением.

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

Переменная x₃ входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x₃ - базисная переменная.

Переменная x₄ входит в уравнение 2 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x₄ - базисная переменная.

Переменная x₅ входит в уравнение 3 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x₅ - базисная переменная.

Переменная x₆ входит в уравнение 4 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x₆ - базисная переменная.

В уравнении 5 нет переменной, которая входила бы в него с  коэффициентом 1 , а в остальные  уравнения системы входила бы с коэффициентом ноль. Добавим  к данному уравнению искусственную  переменную r₁. Очевидно, переменная r₁ будет являться базисной переменной, т.к. входит в уравнение 5 с коэффициентом 1 и не входит в оставшиеся уравнения системы ограничений.

В уравнении 6 нет переменной, которая входила бы в него с  коэффициентом 1 , а в остальные  уравнения системы входила бы с коэффициентом ноль. Добавим  к данному уравнению искусственную  переменную r₂. Очевидно, переменная r₂ будет являться базисной переменной, т.к. входит в уравнение 6 с коэффициентом 1 и не входит в оставшиеся уравнения системы ограничений.

20

x1

+

40

x2

+

x3

=

4000

4

x1

+

6

x2

+

x4

=

900

4

x1

+

4

x2

+

x5

=

600

30

x1

+

50

x2

+

x6

=

6000

x1

-

x7

+

r1

=

0

x2

-

x8

+

r2

=

0

 

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

X _нач = (0 , 0 , 4000 , 900 , 600 , 6000 , 0 , 0 , 0 , 0)

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

Для нахождения начального опорного решения функции L, сначала  придется решить вспомогательную задачу.

Введем в рассмотрение вспомогательную функцию W :

W =   - r₁  - r₂

Найдем наибольшее значение функции W.

Схема решения вспомогательной  задачи абсолютно аналогична схеме  описанной выше. Есть только одно исключение: вспомогательная задача всегда имеет  решение.

В процессе решения данной задачи возможны два варианта.

Если максимальное значение вспомогательной функции W равно  нулю, т.е. все искусственные переменные, обращаются в нуль - это будет  свидетельствовать о том, что  мы нашли начальное опорное решение  функции L.

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

Функция L и вспомогательная  функция W не должны содержать базисных переменных.

Из уравнения 5 последней  системы выразим r₁ и подставим в выражение функции W, получим

W =   x₁  - x₇  - r₂

Из уравнения 6 последней  системы выразим r₂ и подставим в выражение функции W, получим

W =   x₁  + x₂  - x₇  - x₈

Значение функции W для  начального решения: W (X _нач) = 0

Вернемся к рассмотрению функции L.

L =   80 x₁  + 100 x₂

Функция L и вспомогательная  функция W не содержат базисных переменных.

Для составления начальной  симплекс таблицы мы выполнили все  условия.

Обратите внимание:

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

Для функции W правило аналогичное.

Шаг 1

За ведущий выберем  столбец 1 , так как -1 наименьший элемент  в W строке. Элемент W строки, принадлежащий  столбцу свободных членов не рассматриваем.

За ведущую выберем  строку 5, так как отношение свободного члена к соответствующему элементу выбранного столбца для 5 строки является наименьшим. Обратите внимание, что  отношение мы вычисляем только для  положительных элементов столбца 1.

базисные  переменные	x1	x2	x3	x4	x5	x6	x7	x8	r1	r2	свободные  члены	отношение
x3	20	40	1	0	0	0	0	0	0	0	4000	200
x4	4	6	0	1	0	0	0	0	0	0	900	225
x5	4	4	0	0	1	0	0	0	0	0	600	150
x6	30	50	0	0	0	1	0	0	0	0	6000	200
r1	1	0	0	0	0	0	- 1	0	1	0	0	0
r2	0	1	0	0	0	0	0	- 1	0	1	0	-
L	- 80	- 100	0	0	0	0	0	0	0	0	0	-
W	- 1	- 1	0	0	0	0	1	1	0	0	0	-