Динамическое программирование и дифференциальное и интегральное исчисление в образах

курсовая работа

3.1.1 Симплекс-метод

Для производства двух видов изделий P1, P2 использует 3 вида сырья. Запасы сырья ограничены: предприятия обеспеченно сырьем первого вида в количестве S1 (кг), сырьем второго вида S2 (кг), сырьем третьего вида S3 (кг). На производство одного изделия P1 необходимо затратить сырья первого вида А1 (кг), сырья второго вида А2 (кг), сырья третьего вида А3 (кг). На производство одного изделия P2 необходимо затратить сырья первого вида В1 (кг), сырья второго вида В2(кг), сырья третьего вида В3 (кг).

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

А1=5

В1=8

S1=6390

C1=17

А2=4

В2=9

S2=6750

C2=26

А3=4

В3=5

S3=4440

Решение:

1) Допустим, что предприятие планирует выпустить х1 единиц изделий первого вида Р1 и х2 единиц изделий второго вида Р2 . Количество числа х1 не должно превышать его запасы:

5х1 + 8х2 ? 6390

4х1 + 9х2 ? 6750

4х1 + 5х2 ? 4440

х1 ? 0; х2 ? 0

Реализация х1 изделия Р1 и х2 единиц изделий Р2, будет соответствовать

17х1 и 26х2 руб. прибыли.

2) Суммарная прибыль х0 =17х1 + 26х2 (max)

Таким образом математическая модель имеет вид:

5х1 + 8х2 ? 6390

4х1 + 9х2 ? 6750 (1) - система ограничения

4х1 + 5х2 ? 4440

х1 ? 0; х2 ? 0 (2) -условие неотрицательности

3) От системы (1) ограничений в виде неравенств переходим к системе ограничений в виде уравнений, обозначив:

х3 = 6390 - 5х1 - 8х2

х4 = 6750 - 4х1 - 9х2 (3)

х5 = 4440 - 4х1 - 5х2

Тогда система ограничений в виде неравенств заменяется системой ограничений в виде уравнений:

5х1 + 8х2 + х3 = 6390

4х1 + 9х2 + х4 = 6750 (4)

4х1 + 5х2 + х5 = 4440

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

х0 - 17х1 - 26х2 = 0 (5)

4) Система разрешима относительно новых переменных х3, х4 , х5 - эти переменные будут базисными, а х1 и х2 - свободные.

х1 =0

х2=0

х3=6390

х4=6750

х5=4440

Базисное решение является опорным, так как все базисных переменных не отрицательны, значения целевой функции х0 =0

5) Составим симплексную таблицу.

(таб. 3.1.1)

Базисные переменные

Значения базисных переменных

х1

х2

х3

х4

х5

х0

0

-17

-26

0

0

0

х3

6390

5

8

1

0

0

х4

6750

4

9

0

1

0

х5

4440

4

5

0

0

1

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

В нулевой строке целевой функции есть отрицательные элементы, поэтому полученное опорное решение не является оптимальным.

7)Выбираем разрешенный столбец: необходимо взять тот столбец, у которого в ноль строке стоит наибольший отрицательный элемент: (-17).

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

6390 : 5 = 1278;

3750 : 4 = 1687,5;

4440 : 4 = 1110

Наименьшее из этих отношений min

9)Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки: 4

Выполним преобразования однократного замещения. В результате базисная переменная х5 переводится в свободную.

Составляем новую симплексную таблицу. Делим все элементы разрешающей строки на 4.

= 1110; 1; 0; 0;

=

=

=

=

(таб. 3.1.2)

Базисные переменные

Значения базисных переменных

х1

х2

х3

х4

х5

х0

18870

0

0

0

х3

840

0

1

0

х4

2310

1

4

0

1

-1

х1

1110

0

0

0

2310 : 4 = 557,5

1110 :

В ноль строке есть отрицательный элемент: , значит решение не оптимальное.

0

1

0

0

Составим симплексную таблицу.

(таб 3.1.3)

Базисные переменные

Значения базисных переменных

х1

х2

х3

х4

х5

х0

21150

0

0

0

х2

480

0

1

0

х4

390

0

0

1

х1

510

1

0

0

Это опорное решение является оптимальным, так как в ноль строке нет отрицательных элементов.

Ответ: предприятие получит максимальную прибыль от реализации продукции, если первого изделия будет выпущено 480 изделий, а второго 510 изделий, то максимальная прибыль составит:

х0 = 17 510 + 26 480 = 21150

Делись добром ;)