Математическое моделирование

Задание №1. Построить на плоскости область решения системы линейных неравенств и найти максимальное и минимальное значение линейной функции в этой области.

Необходимо найти минимальное  и максимальное значение целевой функции z = 5x₁+4x₂, при системе ограничений:

-x1+x2≤1	(1)
x1-2x2≤1	(2)
2x1+x2≤22	(3)
x1≥0	(4)
x2≥0	(5)

Решение задачи линейного  программирования графическим методом  включает следующие этапы:

1. На плоскости X₁0X₂ строят прямые, получаемые из системы ограничений.
2. Определяются полуплоскости.
3. Определяют многоугольник решений;
4. Строят вектор N(c₁,c₂), который указывает направление целевой функции;
5. Передвигают прямую целевую функцию c₁x₂ + c₂x₂ = 0 в направлении вектора N до крайней точки многоугольника решений для нахождения максимума функции или в направлении противоположном вектору N, для нахождения минимума.
6. Вычисляют координаты точки и значение целевой функции в этой точке.

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

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

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

Построим вектор N=(5;4).Построим прямую, отвечающую значению функции z = 5x₁+4x₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

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

Прямая z(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (4) и (5), то ее координаты удовлетворяют уравнениям этих прямых:

x₂=0

x₁=0

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

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

z(X) = 5*0 + 4*0 = 0

Рассмотрим целевую функцию  задачи z = 5x₁+4x₂ → max. Будем двигать прямую z = 5x₁+4x₂ параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

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

Прямая z(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

-x₁+x₂≤1

2x₁+x₂≤22

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

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

z(X) = 5*7 + 4*8 = 67

 

Задание №2.Торговое предприятие при продаже трех групп товаров (j=1,3) использует три вида материально-денежных ресурсов (i=1,3) в количестве единиц. Известны нормы затрат ресурсов на реализацию единицы товарооборота – и доход от реализации единицы товарооборота - . Требуется определить оптимальны план реализации товаров, обеспечивающий торговому предприятию максимальную прибыль симплексным методом.

Исходные данные по каждому  варианту приведены в таблице.

а11	а12	а13	а21	а22	а23	а31	а32	а33	b1	b2	b3	c1	c2	c3
3	4	1	2	3	6	3	4	2	400	500	300	5	3	4

 

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

Определим максимальное значение целевой функции F(X) = 5x₁+3x₂+4x₃ при следующих условиях-ограничений.

3x₁+4x₂+x₃≤400

2x₁+3x₂+6x₃≤500

3x₁+4x₂+2x₃≤300

3x₁ + 4x₂ + 1x₃ + 1x₄ + 0x₅ + 0x₆ = 400

2x₁ + 3x₂ + 6x₃ + 0x₄ + 1x₅ + 0x₆ = 500

3x₁ + 4x₂ + 2x₃ + 0x₄ + 0x₅ + 1x₆ = 300

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

 

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

x₄, x₅, x₆,

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

X1 = (0,0,0,400,500,300)

 

Базис	В	x1	x2	x3	x4	x5	x6
x4	400	3	4	1	1	0	0
x5	500	2	3	6	0	1	0
x6	300	3	4	2	0	0	1
F(X0)	0	-5	-3	-4	0	0	0

 

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

Итерация №0.

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 и из них выберем наименьшее:

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

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

Базис	В	x1	x2	x3	x4	x5	x6	min
x4	400	3	4	1	1	0	0	133.33
x5	500	2	3	6	0	1	0	250
x6	300	3	4	2	0	0	1	100
F(X1)	0	-5	-3	-4	0	0	0	0

 

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

Базис	В	x1	x2	x3	x4	x5	x6
x4	100	0	0	-1	1	0	-1
x5	300	0	0.33	4.67	0	1	-0.67
x1	100	1	1.33	0.67	0	0	0.33
F(X1)	500	0	3.67	-0.67	0	0	1.67

 

Итерация №1.

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3 и из них выберем наименьшее:

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

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

Базис	В	x1	x2	x3	x4	x5	x6	min
x4	100	0	0	-1	1	0	-1	-
x5	300	0	0.33	4.67	0	1	-0.67	64.29
x1	100	1	1.33	0.67	0	0	0.33	150
F(X2)	500	0	3.67	-0.67	0	0	1.67	0

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

Базис	В	x1	x2	x3	x4	x5	x6
x4	164.29	0	0.0714	0	1	0.21	-1.14
x3	64.29	0	0.0714	1	0	0.21	-0.14
x1	57.14	1	1.29	0	0	-0.14	0.43
F(X2)	542.86	0	3.71	0	0	0.14	1.57