Экономика и менеджмент \ Модели и моделирование на транспорте

Постановка транспортной задачи в матричной форме. Симплекс метод решения задачи линейного программирования, страница 11

N1

N2

N3

N4

A

0

1

0*

1

B

3

4

2

0

C

0

0*

0

2

D

0*

1

2

0

Итого

N1

N2

N3

N4

A

6

5

6

7

B

3

2

4

7

C

7

7

7

7

D

5

4

3

7

В оптимальном плане работа N1 выполняется исполнителем D, работа N2  - исполнителем C, работа N3  - исполнителем A,  работа N4  - исполнителем B. Fопт=7*1+5*1+6*1+7*1=25

4. Симплекс метод решения задачи линейного программирования.

Алгоритм симплекс- метода состоит из двух этапов. На первом этапе осуществляется построение допустимого плана. Для этого строится каноническая форма. На втором этапе выполняется оптимизация целевой функции.

Среди многих приложений наибольшую популярность и широкое распространение получила задача связанная с планирования производства.

Пусть на производстве (в цеху, на участке) имеется возможность четырех видов изделий, например, х1, х2, х3, х4. для их производства привлекают пять видов ресурсов: b1=740, b2=760, b3=770, b4=800, b5=700. Цех заинтересован в максимилизации прибыли, поэтому в качестве критерия оптимальности используется прибыль на одно изделие c1=10, с2=8, с3=9, с4=12 .

В качестве неизвестных примем выпуск изделий хj.

Алгоритм симплекс- метода

Алгоритм симплекс- метода состоит из двух этапов. На первом этапе осуществляется построение допустимого плана

Шаг 1. Построение канонической формы. Для каждого ограничения вводим

-- дополнительную переменную.

4x1+2x2+0x3+1x4  740

   2x1+0x2+2x3+1x4  760

   2x1+2x2+2x3+0x4  770

   2x1+2x2+1x3+1x4  800

   0x1+2x2+2x3+2x4  700

10x1+8x2+9x3+12x4 =F( max)

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х9

Шаг 2. Строится базис допустимого плана относительно этих переменных.

4x1+2x2+0x3+1x4+1x5+0x6+0x7+0x8+0x9= 740

   2x1+0x2+2x3+1x4 +0x5+1x6+0x7+0x8+0x9=  760

   2x1+2x2+2x3+0x4 +0x5+0x6+1x7+0x8+0x9=  770

   2x1+2x2+1x3+1x4 +0x5+0x6+0x7+1x8+0x9=   800

   0x1+2x2+2x3+2x4 +0x5+0x6+0x7+0x8+1x9=   700

10x1+8x2+9x3+12x4 +0x5+0x6+0x7+0x8+0x9=  =F( max)

X1=0, X2=0, X3=0, X4=0,

X5=740, X6=760, X7=770, X8=800, X9=700

ci

pi,

xi

10

8

9

12

0

0

0

1

1

X1

X2

X3

X4

X5

X6

X7

X8

X9

0

x5

740

4

2

0

1

1

0

0

0

0

0

x6

760

2

0

2

1

0

1

0

0

0

0

x7

770

2

2

2

0

0

0

1

0

0

0

X8

800

2

2

1

1

0

0

0

1

0

0

X9

700

0

2

2

2

0

0

0

0

1

zj-cj

F

Шаг 3. Рассчитываются симплекс- множители

и показатели индексной строки

На втором этапе выполняются итеративные процедуры оптимизации базиса задачи.

ci

pi,

xi

10

8

9

12

0

0

0

1

1

X1

X2

X3

X4

X5

X6

X7

X8

X9

0

x5

740

4

2

0

1

1

0

0

0

0

0

x6

760

2

0

2

1

0

1

0

0

0

0

x7

770

2

2

2

0

0

0

1

0

0

0

X8

800

2

2

1

1

0

0

0

1

0

0

X9

700

0

2

2

2

0

0

0

0

1

zj-cj

F=0

-10

-8

-9

-12

0

0

0

0

0
Скачать файл