Модель сельскохозяйственного производства на Нарвских островах для внешнего рынка

……………………………………………………………….

Xm+  qm,m+1 Xm+1 + …. + qm,m+n Xm+n =hm

 

В ней m базисных переменных, k свободных переменных. m+k=n - всего переменных.

Fmin= C1X1+ C2X2+ C3X3+....+ CnXn      (3.6)

 

Все hi должны быть больше либо равны нулю, где i=1,2...m.

На первом шаге в качестве допустимого решения принимаем все Xj=0 (j=m+1,m+2,...,m+k). При этом все базисные переменные Xi=Hi.

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

Таблица 3.1

Первая симплекс таблица

C	Б	H	C1	C2	…	Cm	Cm+1	…	Cm+k
			X1	X2	…	Xm	Xm+1	…	Xm+k
C1 C2 C3 : : Cm	X1 X2 X3 : : Xm	h1 h2 h3 : : hm	1 0 0 : : 0	0 1 0 : : 0	: : : : : :	0 0 0 : : 0	q1,m+1 q2,m+1 q3,m+1 : : qm,m+1	: : : : : :	q1,m+k q2,m+k q3,m+k : : qm,m+k
	F=	F0	∆1	∆2	…	∆m	∆m+1	…	∆m+k

 

Первый столбец - коэффициенты в целевой функции при базисных переменных. Второй столбец - базисные переменные. Третий столбец - свободные члены (hi≥0). Самая верхняя строка - коэффициенты при целевой функции. Вторая верхняя строка - сами переменные, входящие в целевую функцию и в систему ограничений.

Основное поле симплекс метода - система коэффициентов из уравнения.

Последняя строка - служит для того, чтобы ответить на вопрос: «оптимален план или нет» [3, с. 81].

Для первой итерации:

        (3.7)

- оценки они рассчитываются  по формуле:

        (3.8)

Индексная строка позволяет нам судить об оптимальности плана:

1. При отыскании Fmin в индексной строке должны быть отрицательные и нулевые оценки.
2. При отыскании Fmax в индексной строке должны быть нулевые и положительные оценки.

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

Ключевым столбцом является тот, в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax.

Ключевой строкой называется та, в которой содержится наименьшее положительное частное от деления элементов столбца H на соответствующие элементы ключевого столбца [1, с. 42].

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

На этом этапе осуществляется к переходу к последующим итерациям.

Переход к итерациям:

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

  (3.9)

 

 

 

 

4. РЕШЕНИЕ  ЗАДАЧИ СИМПЛЕКС-МЕТОДОМ

 

 

4.1. Решение прямой  задачи линейного программирования

       симплексным методом

 

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

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

 

F(X) = 6x1+6x2+8x3+5x4+4x5+5x6

 

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

 

x1+x3+x5≤1400000

x2+x4+x6≤1200000

2x1+3x2+3x3+3x4+3x5+2x6≤5600000

0.2x1+0.2x2+0.1x3+0.1x4+0.3x5+0.3x6≤700000

 

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

В 1-м неравенстве смысла (≤) вводим базисную переменную x7. В 2-м неравенстве смысла (≤) вводим базисную переменную x8. В 3-м неравенстве смысла (≤) вводим базисную переменную x9. В 4-м неравенстве смысла (≤) вводим базисную переменную x10. 

 

1x1 + 0x2 + 1x3 + 0x4 + 1x5 + 0x6 + 1x7 + 0x8 + 0x9 + 0x10 = 1400000

0x1 + 1x2 + 0x3 + 1x4 + 0x5 + 1x6 + 0x7 + 1x8 + 0x9 + 0x10 = 1200000

2x1 + 3x2 + 3x3 + 3x4 + 3x5 + 2x6 + 0x7 + 0x8 + 1x9 + 0x10 = 5600000

0.2x1 + 0.2x2 + 0.1x3 + 0.1x4 + 0.3x5 + 0.3x6 + 0x7 + 0x8 + 0x9 + 1x10 = 700000

 

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

 

1	0	1	0	1	0	1	0	0	0
0	1	0	1	0	1	0	1	0	0
2	3	3	3	3	2	0	0	1	0
0.2	0.2	0.1	0.1	0.3	0.3	0	0	0	1

 

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

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

Решим систему уравнений относительно базисных переменных: x7, x8, x9, x10.

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

X1 = (0,0,0,0,0,0,1400000,1200000,5600000,700000)

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

 

Базис	В	x1	x2	x3	x4
x7	1400000	1	0	1	0
x8	1200000	0	1	0	1
x9	5600000	2	3	3	3
x10	700000	0.2	0.2	0.1	0.1
F(X0)	0	-6	-6	-8	-5

 

x5	x6	x7	x8	x9	x10
1	0	1	0	0	0
0	1	0	1	0	0
3	2	0	0	1	0
0.3	0.3	0	0	0	1
-4	-5	0	0	0	0

 

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

Итерация №0.

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

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

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

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

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

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

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

 

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

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

 

Базис	В	x1	x2	x3	x4
x7	1400000	1	0	1	0
x8	1200000	0	1	0	1
x9	5600000	2	3	3	3
x10	700000	0.2	0.2	0.1	0.1
F(X1)	0	-6	-6	-8	-5

 

x5	x6	x7	x8	x9	x10	min
1	0	1	0	0	0	1400000
0	1	0	1	0	0	-
3	2	0	0	1	0	1866666.67
0.3	0.3	0	0	0	1	7000000
-4	-5	0	0	0	0	0