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

Размещено на http://www.allbest.ru/

Задача № 1

Решить графически

max (min) F=3x₁+4x₂

Решение:

В неравенствах системы ограничений перейдем к равенствам и построим соответствующие прямые:

(в скобках указаны номера прямых, изображенных на графике)



Многоугольник АВDEK - область допустимых решений системы. Двигая прямую функции в направлении вектора С, находим точка минимума А, точка максимума D. Найдем их координаты, решив соответствующие системы:

> А(0,) F_min=0+4

> D(8,) F_max=3+4

Ответ: при функция имеет минимальное значение

при функция достигает своего максимума

Задача 2

симплексный целочисленный программирование прибыль

Для производства 4-х видов продукции используется 3 вида сырья. Нормы расхода сырья (кг) запасы (кг) его ценность от реализации единицы продукции заданы таблицей.

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

	Нормы расхода ресурсов за единицу изделия	Запас ресурсов
	Изделие 1	Изделие 2	Изделие 3	Изделие 4
Ресурс 1	5	8	3	8	85
Ресурс 2	7	6	9	3	100
Ресурс3	3	7	10	5	150
Ценность	3,7	3	6	2

Решение:

Составим математическую модель. Обозначим:

х1 - выпуск изделий вида А;

х2 - выпуск изделий вида В;

х3 - выпуск изделий вида С.

Запишем систему ограничений:

Общая стоимость произведенных товаров составляет:

F =

Перейдем от системы неравенств к равенствам и введем три дополнительные переменные:

Векторная форма:

x₁P₁+ x₂ P ₂+ x₃ P ₃+ x₄ P ₄+ x₅ P ₅+ x₆ P ₆+ x₇ P ₇=P_0, где

P₁ = P₂ = P₃ = P₄ = P₅ = P₆ = P₇ = P₀ =

Опорный план: Х=(0, 0, 0, 85, 100, 150)

Составим симплекс-таблицу I итерации и подсчитываем значения F₀ и z_j-c_j

F₀ =(C, P₀) =0, z₁==(C, P₁)=0, z₂==(C, P₂)=0 z₃==(C, P₃)=0 z₄==(C, P₄)=0

z₁ - c₁ = 0 - 3,7 = - 3,7 z₂ - c₂ = 0 - 3 = - 3 z₃ - c₃ = 0 - 6 = - 6

z₄ - c₄ = 0 - 2 = - 2.

Для векторов базиса z_j - c_j =0

i	Базис	Сб	P0	3,7	3	6	2	0	0	0
				P1	P2	P3	P4	P5	P6	P7
1	P5	0	85	5	8	3	8	1	0	0
2	P6	0	100	7	6	9	3	0	1	0
3	P7	0	150	3	7	10	5	0	0	1
4			0	-3,7	-3	-6	-2	0	0	0

Максимальное отрицательное число -6 в 4 строке столбца P₃. Значит в базис введем вектор P₃.

Вектор, подлежащий исключению из базиса?₀ = min(85/3; 100/9; 150/10) = 100/9. Значит, исключаем вектор P₆.

Составляем таблицу II итерации

i	Базис	Сб	P0	3,7	3	6	2	0	0	0
				P1	P2	P3	P4	P5	P6	P7
1	P5	0	155/3	8/3	6	0	7	1	-1/3	0
2	P3	6	100/9	7/9	2/3	1	1/3	0	1/9	0
3	P7	0	350/9	-43/9	1/3	0	5/3	0	-10/9	1
4			200/3	4/45	1	0	0	0	6/9	0

Сначала заполним вторую строку, а затем остальные ячейки.

Элементы строки P₃ получены путем деления соответствующих значений на разрешающий элемент (т.е. 9).

Элементы столбца P₁ получены следующим образом: 5-3 = 3-10 =

Элемент столбца P₁ и строки 4 рассчитан как 6

Остальные элементы рассчитаем аналогично и подставим значения в таблице.

Теперь проверим план на оптимальность: так как строка 4 не содержит отрицательных значений, то план является оптимальным. F_max=200/3

Ответ: Х=(0, 0, 0, 85, 100, 150) - оптимальный план, при котором F_max=200/3

Составим двойственную задачу исходной и решим симплекс-методом:

F =

Составим симплекс-таблицу I итерации

i	Базис	Сб	P0	85	100	150	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7
1	P4	0	3,7	5	7	3	1	0	0	0
2	P5	0	3	8	6	7	0	1	0	0
3	P6	0	6	3	9	10	0	0	1	0
4	P7	0	2	8	3	5	0	0	0	1
				-85	-100	-150	0	0	0	0

Введем в базис P_3. Исключим P₇

Составим симплекс-таблицу II итерации

i	Базис	Сб	P0	85	100	150	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7
1	P4	0	179/5	1/5	26/5	0	1	0	0	-3/5
2	P5	0	1/5	-16/5	9/5	0	0	1	0	-7/5
3	P6	0	2	-13	3	0	0	0	1	-2
4	P3	150	2/5	8/5	3/5	1	0	0	0	1/5
			60	1500	10	0	0	0	0	30

Теперь проверим план на оптимальность: так как строка 4 не содержит отрицательных значений, то план является оптимальным. F_min=60

Ответ: Y=(0, 0, 2/5, 179/5, 1/5, 2, 0) - оптимальный план, при котором F_min=60

Задача 3

Четыре предприятия данного экономического района для производства продукции использует три вида сырья. Потребности в сырье каждого из предприятий соответственно равны b1, b2, b3 и b4 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны a1, a2, a3 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей. Составить такой план перевозок, при котором общая себестоимость перевозок является минимальной. Задачу решить методом потенциалов.

	В1	В2	В3	В4
А1	1	3	2	5	110
А2	2	4	6	1	70
А2	8	3	1	7	100
	50	60	90	80

Решение: Составим опорный план методом северо-западного угла

	В1	В2	В3	В4
А1	1 50	3 60	2	5	110
А2	2	4	6 70	1	70
А2	8	3	1 20	7 80	100
	50	60	90	80

X₁ =

S₁ =5060 = 1230 ден.ед.

Теперь составим опорный план методом минимальной стоимости.

	В1	В2	В3	В4
А1	1 50	3	2 60	5	110
А2	2	4	6	1 70	70
А2	8	3 60	1 30	7 10	100
	50	60	90	80

X₂ =

S₂ =5060= 520 ден.ед.

Так как сумма по второму плану получилась меньше, чем по первому, то начнем решение с этого плана. Проверим его на оптимальность методом потенциалов.

Проверим критерий оптимальности для пустых клеток

=

=

= плохая точка

=

=

=

=

Данный план не является оптимальным, так как имеется плохая клетка.

Построим цикл пересчета и новый опорный план

	В1	В2	В3	В4
А1	1 50	3	2 60 -	5	110
А2	2	4	6	1 70	70
А2	8	3 60	1 30 +	7 10 -	100
	50	60	90	80

X₃ =

Стоимость перевозок меньше, значит план улучшили. Проверим на оптимальность

Проверим критерий оптимальности для пустых клеток

=

=

=

=

=

=

Данный план не является оптимальным, так как имеется плохая клетка. Построим цикл пересчета и новый опорный план

	В1	В2	В3	В4
А1	1 50	3 +	2 50 -	5 10	110
А2	2	4	6	1 70	70
А2	8	3 60 -	1 40 +	7	100
	50	60	90	80

X₄=

Стоимость перевозок меньше, значит план улучшили. Проверим на оптимальность

Проверим критерий оптимальности для пустых клеток

=

=

=

Критерий оптимальности выполнен, т.е. последний план оптимальный

Ответ: X₄=

S_min =440 ден.ед.

Задача 4

Решить задачи целочисленного программирования геометрическим методом.

F=3x₁ - 4x₂ >max

Решение: Построим многоугольник решений задачи.

Координаты всех точек многоугольника ОАВD удовлетворяют системе линейных неравенств и условию неотрицательности переменных.

Уточним границу области допустимых решений задачи.

Таким образом, получили граничные точки (0;3) (1;3) (2;1) (3; -1). Границей области допустимых решений задачи целочисленного программирования является ступенчатая линия EKDO.

Положим F=2 или 3x₁ - 4x₂=2 построим данную прямую и продвинем по вектору С (3;-2,) до тех пор, пока она не пройдет через последнюю общую точку с многоугольником EKDO.

В нашем случае искомой точкой является точка D(2.5; 0), при которой функция принимает максимальное значение F(C) = 7,5

Задача 5.

На предприятии производятся изделия четырех наименований, обладающие различной ценностью. В производственном процессе используют три вида сырья. Информация о ресурсе сырья, о нормах их расхода на единичное изделие и ценности изделий представлена в таблице.

	Нормы расхода ресурсов на единицу изделия	Запас ресурсов
	Изделие 1	Изделие 2	Изделие 3	Изделие 4
Ресурс 1	5	8	3	8	85
Ресурс 2	7	6	9	3	100
Ресурс3	3	7	10	5	150
Ценность	3,7	3	6	2

Решить задачу целочисленного программирования.

Решение: Определим симплексным методом оптимальный план задачи.

Составим математическую модель. Обозначим:

х1 - выпуск изделий вида А;

х2 - выпуск изделий вида В;

х3 - выпуск изделий вида С.

Запишем систему ограничений:

Общая стоимость произведенных товаров составляет:

F =

Перейдем от системы неравенств к равенствам и введем три дополнительные переменные:

Векторная форма:

x₁P₁+ x₂ P ₂+ x₃ P ₃+ x₄ P ₄+ x₅ P ₅+ x₆ P ₆+ x₇ P ₇=P_0, где

P₁ = P₂ = P₃ = P₄ = P₅ = P₆ = P₇ = P₀ =

Опорный план: Х=(0, 0, 0, 85, 100, 150)

Составим симплекс-таблицу I итерации и подсчитываем значения F₀ и z_j-c_j

F₀ =(C, P₀) =0, z₁==(C, P₁)=0, z₂==(C, P₂)=0 z₃==(C, P₃)=0 z₄==(C, P₄)=0

z₁ - c₁ = 0 - 3,7 = - 3,7 z₂ - c₂ = 0 - 3 = - 3 z₃ - c₃ = 0 - 6 = - 6

z₄ - c₄ = 0 - 2 = - 2. Для векторов базиса z_j - c_j =0

Сб	Базис	P0	3,7	3	6	2	0	0	0
			P1	P2	P3	P4	P5	P6	P7
0	P5	85	5	8	3	8	1	0	0
0	P6	100	7	6	9	3	0	1	0
0	P7	150	3	7	10	5	0	0	1
Zk	0	0	0	0	0	0	0	0
Дk= Zk - Ck		-3,7	-3	-6	-2	0	0	0

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

Максимальное отрицательное число -6 в 4 строке столбца P₃. Значит, в базис введем вектор P₃.

Вектор, подлежащий исключению из базиса?₀ = min(85/3; 100/9; 150/10) = 100/9. Значит, исключаем вектор P₆.

Составляем таблицу II итерации

Сб	Базис	P0	3,7	3	6	2	0	0	0
			P1	P2	P3	P4	P5	P6	P7
0	P5	155/3	8/3	6	0	7	1	-1/3	0
6	P3	100/9	7/9	2/3	1	1/3	0	1/9	0
0	P7	350/9	-43/9	1/3	0	5/3	0	-10/9	1
Zk	200/3	29/30	1	6	0	0	2/3	0
Дk= Zk - Ck		-82/30	-2	0	-2	0	2/3	0

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

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

),

где - дробные части чисел величин

Как видно из таблицы II итерации, найденный оптимальный план X= (0, 0, 100/9,0,155/3,0,350/9) не является оптимальным планом задачи целочисленного программирования. Так как максимальная дробная часть соответствует седьмой переменной, составим для нее ограничение:

++0++0+=

или ++- +=

К системе ограничений задачи добавляем неравенство

+f (+- +? f

Решение произведем симплекс-методом, в результате получим таблицу III итерации

Размещено на Allbest.ru

...