Симплекс метод

Схема 1.

В результате получают новую  симплекс-таблицу, отвечающую новому базисному  решению.

Теперь следует просмотреть строку целевой функции (индексную), если в ней нет отрицательных значений (в задачи на нахождение максимального значения), либо положительных (в задачи на нахождение минимального значения) кроме стоящего на месте y₀ (свободного столбца), то значит, что оптимальное решение получено. В противном случае, переходим к новой симплекс таблице по выше описанному алгоритму. [5]

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

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

f =c₁x₁ + c₂x₂ +…+ c_nx_n→max   (4)

при условиях: a₁₁x₁ + a₁₂x₂ +…+ a_1nx_n ≤ b₁

a₂₁x₁ + a₂₂x₂ +…+ a_2nx_n ≤ b₂

…       (5)

a_m1x₁ + a_m2x₂ +…+ a_mnx_n ≤ b_m

x_j ≥ 0 (j = 1, 2,…m, m ≤ n).

Задача, состоящая в нахождении минимального значения функции

f*=b₁y₁ + b₂y₂ +…+ b_my_m→min  (6)

при условиях:  a₁₁y₁ + a₁₂y₂ +…+ a_m1y_m ≥ c₁

a₁₂y₁ + a₂₂y₂ +…+ a_m2y_m ≤ c₂

…       (7)

a_1ny₁ + a_2ny₂ +…+ a_mny_m ≤ c_m

y_i ≥ 0 (i = 1, 2, … k ≤ m)

называется двойственной по отношению к задаче (4) – (5). Задачи (4) – (5) и (6) – (7) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной– на минимум.

2. Матрица

(8)

составленная из коэффициентов  при неизвестных в системе  ограничений (5) исходной задачи, и аналогичная матрица

   (9)

в двойственной задаче получаются друг из друга транспонированием (т. е. заменой строк столбцами, а столбцов – строками).

3. Число переменных  в двойственной задаче равно  числу ограничений в системе  (5) исходной задачи, а число ограничений в системе (7) двойственной задачи – числу переменных в исходной задаче.

4. Коэффициентами при  неизвестных в целевой функции  (6) двойственной задачи являются свободные члены в системе (5) исходной задачи, а правыми частями в соотношениях системы (7) двойственной задачи – коэффициенты при неизвестных в целевой функции (4) исходной задачи.

5. Если i–е соотношение в системе (5) исходной задачи является неравенством, то j–я переменная двойственной задачи y_j ≥ 0. В противном случае переменная у_j может принимать как положительные, так и отрицательные значения.

Двойственные пары задач  обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (5) прямой задачи и соотношения (7) двойственной задачи являются неравенствами вида “ ”. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

Если одна из задач  двойственной пары (4) – (5) или (6) – (7) имеет оптимальный план, то и другая имеет оптимальный план, и значения целевых функций задач при их оптимальных планах равны между собой, т. е. f _max =  f*_min.

Если же целевая функция одной  задачи из двойственной пары неограниченна (для исходной – сверху, для двойственной – снизу), то другая задача вообще не имеет планов. [3]

 

2. ПРАКТИЧЕСКИЙ РАЗДЕЛ

2.1. Описание  производственной ситуации

Фирма по изготовлению мебели для производства 4 видов изделий (комоды, столы, стулья и кресла) должна использовать 3 вида дерева (дуб, сосна, кедр), запасы которых на планируемый месяц составляют соответственно 3000, 3360 и 7120 м². В приведенной ниже таблице 2 даны технологические коэффициенты, т.е. расход каждого вида древесины на изготовление единицы продукции, прибыль от реализации изделия каждого вида, а также количество часов, затрачиваемых на производство одной единицы продукции каждого вида. Сотрудники предприятия за планируемый месяц должны отработать не менее 5040 часов.

Виды       материала	Запасы       древесины, м2	Технологические коэффициенты
		Комод	Стол	Стул	Кресло
Дуб	3000	0	1	0	2
Сосна	3360	0	4	1	3
Кедр	7120	3	1	1	1
Кол-во      часов		2	3	1	4
Прибыль от реализации,      руб.		400	600	200	1000

Таблица 2.

Прямая задача:

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

Двойственная задача:

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

2.2. Математическое описание ситуации

Обозначим через x₁ , x₂ , x₃ , x₄ количество единиц соответствующих изделий: Комоды, столы, стулья и кресла. Тогда можно записать экономико-математическую модель задачи. 

Прямая задача:

Найти максимум функции

f=400x₁+600x₂+200x₃+1000x₄→max,

при выполнении системы ограничений:

x₂+2x₄ ≤ 3000

4x₂+x₃+3x₄ ≤ 3360

3x₁+x₂+x₃+x₄ ≤ 7120

2x₁+3x₂+x₃+4x₄ ≥ 5040,

где x₁ , x₂ , x₃ , x₄ ≥0.

Двойственная задача:

Найти минимум  функции

          f=3000x₅+3360x₆+7120x₇+5040(-x₈+x₉)→min - общая оценка сырья, используемого на производство продукции,

при выполнении системы ограничений:

   3х₇+2(-х₈+х₉) ≥ 400

х₅+4х₆+х₇+3(-х₈+х₉) ≥ 600

х₆+х₇+(-х₈+х₉) ≥ 200

2х₅+3х₆+х₇+4(-х₈+х₉) ≥ 1000

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

2.3. Решение  задачи

Обратим систему ограничений-неравенств в систему уравнений. Для этого введем 4 переменные x₅, x₆, x₇, x₈ ≥ 0 получим:

   x₂+2x₄+x₅ = 3000

4x₂+x₃+3x₄+x₆ = 3360

3x₁+x₂+x₃+x₄+x₇ = 7120

2x₁+3x₂+x₃+4x₄-x₈ = 5040

Система ограничений  предлагает только 3 допустимых базисных переменных x₅, x₆, x₇ - они входят только в одно уравнение соответственно в 1-е, 2-е, и 3-е с коэффициентом 1. В 4-е уравнение добавляем искусственную переменную x₉ ≥ 0. Чтобы можно было применить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это x₅, x₆, x₇ и x₉. Эти добавочные переменные в условиях данной задачи имеют конкретное экономическое содержание, а именно: объем остатков сырья каждого вида после выполнения плана выпуска продукции. [4] Итак, имеем:

f=400x₁+600x₂+200x₃+1000x₄→max,

x₂+2x₄+x₅ = 3000

4x₂+x₃+3x₄+x₆ = 3360

3x₁+x₂+x₃+x₄+x₇ = 7120

2x₁+3x₂+x₃+4x₄-x₈+ x₉ = 5040.

Данная система является системой с базисом, в которой x₅, x₆, x₇ и x₉ базисные переменные, а x₁, x₂, x₃, x₄ и x₈ свободные переменные, свободные члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:

	cj	400	600	200	1000	0	0	0	0	0	0
cбазис	базис	x1	x2	x3	x4	x5	x6	x7	x8	x9	b	δ
0	x5	0	1	0	2	1	0	0	0	0	3000	1500
0	x6	0	4	1	3	0	1	0	0	0	3360	1120
0	x7	3	1	1	1	0	0	1	0	0	7120	7120
0	x9	2	3	1	4	0	0	0	-1	1	5040	1260
Оценка		-400	-600	-200	-1000	0	0	0	0	0	0

Таблица 3.

В строке индексных оценок таблицы 3 имеются отрицательные значения, следовательно, решение можно улучшить. Среди коэффициентов этой строки (исключая столбец свободных членов b) выбирается наименьшее отрицательное число (-1000). Данный столбец является разрешающим.

Определяем разрешающую строку. Для этого находим наименьшее из отношений свободных членов к положительным коэффициентам разрешающего столбца (1120).

Таким образом, отыскивается разрешающий элемент таблицы, расположенный на пересечении разрешающих столбца и строки (3).

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

 

	cj	400	600	200	1000	0	0	0	0	0	0
cбазис	базис	x1	x2	x3	x4	x5	x6	x7	x8	x9	b	δ
0	x5	0	-1 2/3	- 2/3	0	1	- 2/3	0	0	0	760
1000	x4	0	1 1/3	1/3	1	0	1/3	0	0	0	1120
0	x7	3	- 1/3	2/3	0	0	- 1/3	1	0	0	6000	2000
0	x9	2	-2 1/3	- 1/3	0	0	-1 1/3	0	-1	1	560	280
Оценка		-400	733 1/3	133 1/3	0	0	333 1/3	0	0	0	0