Методы оптимальных решений

Вариант №7

 

          Задача № 1

Вариант 1.7

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

max (min) F=3x1+4x2

 

 

Решение:

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

 

 

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

 

 

 

 

 

 

 

 

 

 

 

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

 

 → А(0,) Fmin=0+4

 → D(8, ) Fmax=3 +4

 

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

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

 

                                         Задача № 2

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

 

Вариант 7

 

	Нормы расхода ресурсов за единицу изделия				Запас ресурсов
	Изделие 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-выпуск изделий вида С;

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

 

5х1+8х2+3х3+8х4≤85

7х1+6х2+9х3+3х4≤100

3х1+7х2+10х3+5х4≤150

 

 

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

 

F=3,7х1+3х2+6х3+2х4

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

 

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

 

5х1+8х2+3х3+8х4+х5=85   

7х1+6х2+9х3+3х4+х6=100

3х1+7х2+10х3+5х4+х7=150

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

х1Р1+х2Р2+х3Р3+х4Р4+х5Р5+х6Р6+х7Р7=Р0,где

      

Р1= P2 = P3 = P4 = P5 = P6 = P7 = P0 =

 

 

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

Составим симплекс-таблицу Ι итерации и подсчитываем значение F0  и   zj-cj

 

F0=(C,P0)=0,z1=(C,P1)=0,z2=(C,P2)=0,z3=(C,P3)=0,z4=(C,P4)=0

z1-c1=0-3,7=-3,7; z2-c2=0-3=-3; z3-c3=0-6=-6; z4-c4=0-2=-2.

 

Для векторов базиса zj-cj=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 строке столбца Р3.Значит в базис введем вектор Р3.

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

 

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

 

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

 

 

 

 

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

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

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

 

 

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

 

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

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

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

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

 

    5у1+7у2+3у3≥3,7

    8у1+6у2+7у3≥3

    3у1+9у2+10у3≥6

    8у1+3у2+5у3≥2

 

 F=85y1+100y2+150y3

 

       5y1+7y2+3y3+y4=3,7

    8y1+6y2+7y3+y5=3

    3y1+9y2+10y3+y6=6

    8y1+3y2+5y3+y7=2

 

   Составим симплекс-таблицу 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

 

 

   Введем в базис Р3.Исключим Р7

 

   Составим симплекс-таблицу 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 не содержит отрицательных значений, то план является оптимальным. Fmin=60

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

                                                     Задача № 3

Четыре предприятия данного экономического района для производства

продукции  использует  три  вида  сырья.  Потребности  в  сырье  каждого  из

предприятий соответственно равны b1, b2, b3 и b4 ед. Сырье сосредоточено в

трех местах его получения, а запасы соответственно равны  a1, a2, a3  ед. На

каждое из предприятий сырье может завозиться из любого пункта его полу-

чения. Тарифы перевозок являются известными величинами и задаются мат-

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

 

Вариант 7

 

 

 

	В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

 

X1 =

 

S1 =50 60 = 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

 

 

X2 =

S2 =50 60 = 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