Реализация симплекс в случае положительных свободных членов

Алгоритм  решения табличным  симплекс-методом:

     Для определенности считаем, что решается задача на максимум:

     Первые  два шага алгоритма были описаны выше.

3. Полученную систему уравнений и линейную функцию записываем в следующем виде:

 (9)

4. Систему (9) записываем в виде симплексной таблицы

Базисные переменные	Свободные члены	Переменные							Оценочное отношение
		x1	x2	…	xn	xn+1	…	xn+m
xn+1 xn+2 … xn+m	b1 b2 … bm	a11	a12	…	a1n	1	0	0
		a21	a22	…	a2n	0	…	0
		…	…	…	…	…	…	…
		am1	am2	…	amn	0	0	1
F	c0	-c1	-c2	…	-cn	0	0	0

5. Проверяем выполнение критерия оптимальности. Максимум F=c₀  достигнут в том случае, если в последней строке симплекс-таблицы нет с_j <0 (j=1,…,n+m). В оптимальном допустимом базисном решении основные  (базисные) переменные (см. первый столбец симплексной таблицы) принимают соответствующие значения в столбце «свободные члены», а неосновные переменные равны 0.

Если  полученное решение оптимальное, то алгоритм завершается, а если нет, то переходим к новому допустимому базисному решению с помощью следующих шагов:

6. Определяем разрешающий столбец, в котором содержится наибольший по модулю отрицательный коэффициент с_s=max|c_j| (c_j<0) (см. последнюю строку). Переменная x_s, соответствующая разрешающему столбцу переводится в основные переменные.
7. Последний столбец заполняем оценочными границами по следующим правилам:

1. ∆_i = ∞, если b_i и a_is имеют разные знаки;
2. ∆ _i = ∞, если b_i = 0 и a_is < 0;
3. ∆ _i = ∞, если  a_is = 0;
4. ∆ _i = 0, если b_i = 0 и a_is <> 0;
5. ∆ _i = , если b_i и a_is имеют одинаковые знаки.

8. Определяем . Если конечного минимума нет, то задача не имеет конечного оптимума, то есть нет решений (F_max = ∞).

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

На  пересечении разрешающей  строки и столбца находится разрешающий элемент a_qs.

9. Переходим к новой таблице по правилам:

Правило 1: В столбце «Базисные переменные»  записываем новый базис: вместо основной переменной x_q (которая становится неосновной)  - новую основную переменную x_s.

Правило 2: Преобразуем элементы таблицы  методом Жордана-Гаусса таким образом, чтобы единица стояла напротив «своей»  основной переменной, 0 – против «чужой» ОП и нули в последней строке для всех ОП.

10. Возвращаемся к пункту 5).

 
 
 

 

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

    Предприятия располагают ресурсами сырья, рабочей  силой  и оборудованием для  производства любого из 4 видов производимых товаров. Затраты ресурсов на изготовление единицы данного вида товара, прибыль, получаемая предприятием, а также  запасы ресурсов представлены в таблице 1.

Таблица 1

Вид ресурса	Вид товара				Объем ресурсов
	1	2	3	4
Сырье, кг	3	5	2	4	60
Рабочая сила, ч	22	14	18	30	350
Оборудование, ст. ч	10	14	8	6	128
Прибыль на ед. товара (т. руб.)	30	25	56	48

    Найти оптимальный ассортимент, максимизирующий  прибыль, при условии, суммарные  издержки не должны превышать 96 т.руб., производственные издержки в т. руб. на 1 единицу каждого изделия 6, 9,12, 3.

    Решение:

    Обозначим через    - количества товара вида 1, 2, 3 и 4 соответственно.

    Целевая функция задачи:

    

    Ограничения задачи: на виды ресурсов

    

     .

    Решим задачу симплексным методом.

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

    

    Целевую функции представим в виде:

    

    Базисные  переменные: х5, х6, х7, х8.

    Свободные переменные: х1, х2, х3, х4.

    Запишем симплекс- таблицу. 

Базис	Своб. члены	Переменные								Оценочное отношение
		x1	x2	x3	x4	x5	x6	x7	x8
x5	60	3	5	2	4	1	0	0	0	15
x6	350	22	14	18	30	0	1	0	0	350/18=19,4
x7	128	10	14	8	6	0	0	1	0	128/8=16
x8	96	6	9	12	3	0	0	0	1	96/12=8
F	0	-30	-25	-56	-48	0	0	0	0

 

    В последней строке есть отрицательные  числа, максимальное по модулю из которых  равно -56. Следовательно, столбец 3 становиться  разрешающим, то есть х3 вводим в базис. Определим, какая переменная уйдет  из базиса. Для этого определим  оценочное отношение для каждой строки.  Например, для первой строки оценочное отношение равно отношению  свободного члена к коэффициенту разрешающего столбца, то есть 60/2=30.

    Аналогично  определятся другие оценочные отношения, которыми заполняем столбец «Оценочное отношение». Минимум из 15, 350/18, 16 и 8 равен 8, следовательно, четвертая строка разрешающая и х8 уходит из базиса.

    Переписываем  таблицу так, чтобы на пересечении  разрешающего столбца и строки стояла 1, для этого всю четвертую строку  делим на 12.  В новой таблице  все остальные элементы разрешающего столбца должны быть равны 0.  Например, получим 0 на пересечении  первой строки разрешающего столбца. Для этого  умножим четвертую строку на (-2) и  сложим с соответствующими элементами первой строки.

Базис	Своб. члены	Переменные								Оценочное отношение
		x1	x2	x3	x4	x5	x6	x7	x8
x5	44	2	3,5	0	3,5	1	0	0	-1/6	44/3,5=12,6
x6	206	13	0,5	0	25,5	0	1	0	-1,5	206/25,5=8,08
x7	64	6	8	0	4	0	0	1	-2/3	64/4=16
X3	8	1/2	3/4	1	1/4	0	0	0	1/12	8/0,25=32
F	448	-2	17	0	-34	0	0	0	14/3