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

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение ВПО

Тверской государственный технический университет

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

на тему:

«Решение задачи линейного программирования графически и симплекс-методом»

по дисциплине:

«Теория систем и системный анализ»

 

 

 

 

 

Выполнила: студентка гр. ПИ 12-08

факультета информационных технологий

Кулевая Екатерина Михайловна

Проверил: Кемайкин Валерий Константинович

 

                      

 

 

 

 

 

 

 

 

Тверь 2014

 

Вариант №6. Применение системного анализа на примере молокозавода.

Задание:

Решить графически и симплекс-методом задачу линейного программирования. Записать задачу, двойственную исходной.

Условие задачи:

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

Х1 – количество творога,

Х2 – количество масла.

Ограничения:

Время, которое требуется для изготовления творога – 1 единица, а для изготовления масла – 2 единицы. При этом общее время на изготовление двух видов продукции должно быть не более 4 единиц.

Размер покупательского спроса на творог – 5 единиц, а на масло – 2 единицы. При этом, общий спрос на два вида продукции должен быть не менее 10 единиц.

Затраты, которые требуются для изготовления творога – 4 единицы, а для изготовления масла – 3 единицы. При этом общие затраты на изготовление двух видов продукции должны быть не более 12 единиц.

Количество сырья, которое требуется для изготовления творога – 7 единица, а для изготовления масла – 4 единицы. При этом общее количество сырья для изготовления двух видов продукции должно быть не более 28 единиц.

Цель задачи:

Добиться максимального дохода от продажи творога и масла.

Определить, какое количество творога и масла необходимо продавать.

 

 

 

Условия для 6 варианта:

Решение задачи графическим методом

Необходимо найти максимальное значение целевой функции

F = 2x1+x2 → max, при системе ограничений:

-x1+2x2≤4, (1)
5x1+2x2≥10, (2)
4x1-3x2≤12, (3)
7x1+4x2≤28, (4)
x1≥0,  х2≥0.

 

1 этап. Построение области допустимых решений.

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

Построим уравнение -x1+2x2 = 4 по двум точкам. Для нахождения первой точки приравниваем x1=0. Находим x2=2. Для нахождения второй точки приравниваем x2=0. Находим x1=-4. Соединяем точку (0;2) с (-4;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0;0), определим знак неравенства в полуплоскости: -1*0+2*0-4≤0, т.е. -x1+2x2-4≤ 0 в полуплоскости ниже прямой.

Построим уравнение 5x1+2x2=10 по двум точкам. Для нахождения первой точки приравниваем x1=0. Находим x2=5. Для нахождения второй точки приравниваем x2=0. Находим x1=2. Соединяем точку (0;5) с (2;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0;0), определим знак неравенства в полуплоскости: 5*0+2*0-10≤0, т.е. 5x1+2x2-10≥ 0 в полуплоскости выше прямой.

Построим уравнение 4x1-3x2=12 по двум точкам. Для нахождения первой точки приравниваем x1=0. Находим x2=-4. Для нахождения второй точки приравниваем x2=0. Находим x1=3. Соединяем точку (0;-4) с (3;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0;0), определим знак неравенства в полуплоскости: 4*0-3*0-12≤0, т.е. 4x1-3x2-12≤ 0 в полуплоскости ниже прямой.

Построим уравнение 7x1+4x2=28 по двум точкам. Для нахождения первой точки приравниваем x1=0. Находим x2=7. Для нахождения второй точки приравниваем x2=0. Находим x1=4. Соединяем точку (0;7) с (4;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0;0), определим знак неравенства в полуплоскости: 7*0+4*0-28≤0, т.е. 7x1+4x2-28≤0 в полуплоскости ниже прямой.

Обозначим границы области многоугольника решений:

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

2 этап. Построение вектор-градиент.

Построим прямую, отвечающую значению функции F = 0: F = 2x1+x2 = 0.

Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (2; 1).

3 этап. Построение  произвольного уровня целевой функции.

F(x)=h, (h – произвольное значение).

F(x)=10; 2x1+x2=5.

Координаты для отражения прямой на графике:

х1=0, х2=5 и х1=2,5, х2 =0. 

4 этап. Определение  точки выхода за пределы ОДР.

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

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

Прямая пересекает область в точке E. Так как точка E получена в результате пересечения прямых (3) и (4), то ее координаты удовлетворяют уравнениям этих прямых: 
   4x1-3x2=12, 
   7x1+4x2=28. 
Решив систему уравнений, получим: x1=132/37=3,5676, x2=28/37=0,7568. Откуда найдем максимальное значение целевой функции: F(X)=2*3,5676+1*0,7568 =292/37= 7,8919.

Вывод:

Получили максимальное значение целевой функции F(X)=292/37=7,8919 и точку максимума целевой функции F (132/37; 28/37).

Таким образом, наилучшим вариантом продажи продукции молокозавода является продажа творога в количестве 3,5676 единиц и продажа масла в количестве 0,7568 единиц. Доход от продажи творога и масла составит 7,8919 единицы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

F(X) = 2x1+x2 max при следующих ограничениях:

-x1+2x2≤4,

5x1+2x2≥10,

4x1-3x2≤12,

7x1+4x2≤28.

1. Приведение задачи к форме ОЗЛП (основная задача линейного программирования).

Для этого, все ограничения представим равенствами, введя дополнительные переменные:

Z(X) = -2x1-x2 min

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

-x1+2x2+ω1=4,

5x1+2x2-ω2=10,

4x1-3x2+ω3=12,

7x1+4x2+ω4=28,

х1,2 ≥0, ω1,2,3,4≥0.

 

ω1=x1-2x2+4,

ω2=5x1+2x2-10,

ω3=-4x1+3x2+12

ω4 =-7x1-4x2+28

х1,2 ≥0, ω1,2,3,4≥0

 

Составим исходную Симплекс - таблицу:

	X1	X2	b
ω1	1	-2	4
ω2	5	2	-10
ω3	-4	3	12
ω4	-7	-4	28
Z	-2	-1	0

 

Получено базисное решение:

ω1=4,

ω2=-10,

ω3=12,

ω4=28,

Z =0,

X1,2=0.

2. Поиск опорного решения.

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

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

min {|4/1| ; |-10/5| , |12/-4| , |28/-7|}={4;2;3;4}=2

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

 

 

 

	X1	X2	b
ω1	1	-2	4
ω2		2	-10
ω3	-4	3	12
ω4	-7	-4	28
Z	-2	-1	0

 

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

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

	ω2	Х2	b
ω1	1/5	-12/5	6
X1	1/5	-2/5	2
ω3		23/5	4
ω4	-7/5	-6/5	14
Z	-2/5	-1/5	-4

 

ω1=6,

Х1=2,

ω3=4,

ω4=14,

Z =-4,

ω2=0,

Х2=0.

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

3. Поиск оптимального  решения.

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

Min {|6:(1/5)|, |2:1/5|, |4:-4/5|, |14:(-7/5)|}= {30;10;5;10}=5

Соответственно, разрешающий элемент находится на пересечении переменной  ω2 и ω3 и равен -4/5.

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

	ω3	Х2	b
ω1	-1/4	-5/4	7
X1	-1/4	3/4	3
ω2	-5/4	23/4	5
ω4	7/4		7
Z	1/2	-5/2	-6

 

Решение пока не является оптимальным, поэтому выполняем очередной шаг ОЖИ:

В качестве разрешающего столбца выберем столбец х2, в качестве разрешающей строки ω4.

Min {|7:-5/4|, |3:3/4|, |5:23/4|, |7:-37/4|}={5,6;4;0,87;0,757}=0,757

Разрешающий элемент: -37/4.

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

 

	ω3	ω4	b
ω1	-18/37	5/37	224/37
X1	-4/37	-3/37	132/37
ω2	-6/37	-23/37	346/37
Х2	7/37	-4/37	28/37
Z	1/37	10/37	-292/37