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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Завдання № 1 (Симплекс метод рішення задачі лінійного програмування.)

Знайти F max = 9 x 1 + 10 x 2 + 16 x 3, при обмеженнях:

Запишемо завдання в канонічному вигляді:

F = 9 x 1 + 10 x 2 + 16 x 3 max

Заповнимо початкову таблицю:

Таблиця 0.


0

9

10

16

0

0

0

Відношення,

θ

i

Базис


1

0

360

18

15

12

1

0

0

30

2

0

192

6

4

8

0

1

0

24

3

0

180

5

3

3

0

0

1

60


Δ j

0

- 9

- 10

- 16

0

0

0



Zj

0

0

0

0

0

0

0


Zj обчислюється за формулою

Оцінки (Δj) обчислюються за формулою , Де - Коефіцієнт з першого рядка таблиці.

Вибираємо мінімальну (негативну) оцінку. Вона визначає направляючий стовпець.

Заповнюємо стовпець «θ», за мінімальним значенням визначаємо напрямну рядок.

На перетині рядка і стовпця знаходиться направляючий елемент.

Заповнюємо нову таблицю

Таблиця 1.


0

9

10

16

0

0

0

Відношення,

θ

i

Базис


1

0

72

9

9

0

1

0

8

2

16

24

1

0

0

48

3

0

108

0

0

-

1

72


Δ j

384

3

-2

0

0

2

0



Zj

384

12

8

0

0

2

0


Змінюється базис в позиції направляючої рядка. Базисним стає вектор, що відповідає направляючому стовпцю, т. е.

Стовпець стає базисним, тобто одиничним.

Нові значення в направляючої рядку отримуємо розподілом елементів цього рядка на направляючий елемент.

Інші елементи в небазисних шпальтах і в стовпці обчислюємо за правилом трикутника.

Вибираємо мінімальну негативну оцінку. Вона визначає направляючий стовпець.

Заповнюємо стовпець «θ»

За мінімальним значенням визначаємо напрямну рядок.

На перетині направляючої рядка і стовпця знаходиться направляючий елемент.

Заповнення другої таблиці здійснюється за аналогією з попередньою.

Таблиця 2.


0

9

10

16

0

0

0

Відношення,

θ

i

Базис


1

10

8

1

1

0

-

0

______

2

16

20

0

1

-

0

______

3

0

96

0

0

-

1

______


Δ j

400

5

0

0

0



Zj

400

14

10

16

0


Так як немає негативних оцінок Δj, отже виконується ознака оптимальності і не вводилися штучні змінні, то отримано оптимальне рішення.

Відповідь:

Максимальне значення функції F max = 400 досягається в точці з координатами:

= 0

= 8

= 20

= 0

= 0

= 96

Завдання № 2 (Метод Літтла)

Знайти найкоротший шлях у графі, заданому графічно у вигляді креслення, методом Літтла.

З креслення запишемо матрицю відстаней. (Відстань від т.1 до т.2 одно:

, І т.д.)


1

2

3

4

5

6

1

18,87

49,48

51,86

80,51

97,42

2

18,87

32,06

34,48

65,15

84,01

3

49,48

32,06

31,76

61,19

83,20

4

51,86

34,48

31,76

32,14

53,15

5

80,51

65,15

61,19

32,14

22,14

6

97,42

84,01

83,20

53,15

22,14

Припустимо що найкоротший шлях буде таким:

т.1 → т.2 → т.3 → т.4 → т.5 → т.6 → т.1 і складе

Рішення: Перший етап.

Крок 1. Наведемо матрицю відстаней по рядках і стовпцях

(У рядку віднімаємо з кожного елемента мінімальний, потім у стовпцях)


1

2

3

4

5

6


1

18,87

49,48

51,86

80,51

97,42

18,87

2

18,87

32,06

34,48

65,15

84,01

18,87

3

49,48

32,06

31,76

61,19

83,20

31,76

4

51,86

34,48

31,76

32,14

53,15

31,76

5

80,51

65,15

61,19

32,14

22,14

22,14

6

97,42

84,01

83,20

53,15

22,14

22,14


1

2

3

4

5

6

1

0

30,61

32,99

61,64

78,55

2

0

13,19

15,61

46,28

65,14

3

17,72

0,30

0

29,43

51,44

4

20,10

2,72

0

0,38

21,39

5

58,37

43,01

39,05

10,00

0

6

75,28

61,87

61,06

31,01

0


0

0

0

0

0

0


1

2

3

4

5

6

1

0

30,61

32,99

61,64

78,55

2

0

13,19

15,61

46,28

65,14

3

17,72

0,30

0

29,43

51,44

4

20,10

2,72

0

0,38

21,39

5

58,37

43,01

39,05

10,00

0

6

75,28

61,87

61,06

31,01

0

Крок 2. Визначимо оцінки нульових клітин:

Крок 3. Викреслюємо клітку з максимальною оцінкою. Включаємо дану клітку в шлях обходу. (5 - 6)

Крок 4. Переписуємо матрицю відстаней, накладаючи заборону на одну з кліток для виключення передчасного замикання контуру (в клітку 6-5 ставимо ∞).


1

2

3

4

5

1

0

30,61

32,99

61,64

2

0

13,19

15,61

46,28

3

17,72

0,30

0

29,43

4

20,10

2,72

0

0,38

6

75,28

61,87

61,06

31,01

Далі повторюємо кроки 1 - 4, поки не дійдемо до однієї клітини.

Другий етап.

Крок 1. Наведемо матрицю відстаней по рядках і стовпцях.


1

2

3

4

5

1

0

30,61

32,99

61,64

2

0

13,19

15,61

46,28

3

17,72

0,30

0

29,43

4

20,10

2,72

0

0,38

6

75,28

61,87

61,06

31,01


0

0

0

0

0,38


1

2

3

4

5

1

0

30,61

32,99

61,26

2

0

13,19

15,61

45,90

3

17,72

0,30

0

29,05

4

20,10

2,72

0

0

6

75,28

61,87

61,06

31,01

Крок 2. Визначимо оцінки нульових клітин:

Крок 3. Викреслюємо клітку з максимальною оцінкою. Включаємо дану клітку в шлях обходу. (1 - 2)

Крок 4. Переписуємо матрицю відстаней, накладаючи заборону на одну з кліток для виключення передчасного замикання контуру (в клітку 2 - 1 ставимо ∞).


1

3

4

5

2

13,19

15,61

45,90

3

17,72

0

29,05

4

20,10

0

0

6

75,28

61,06

31,01

Третій етап.

Крок 1. Наведемо матрицю відстаней по рядках і стовпцях.


1

3

4

5

2

13,19

15,61

45,90

3

17,72

0

29,05

4

20,10

0

0

6

75,28

61,06

31,01


17,72

0

0

0


1

3

4

5


2

13,19

15,61

45,90

13,19

3

0

0

29,05

0

4

2,38

0

0

0

6

57,56

61,06

31,01

31,01


1

3

4

5

2

0

2,42

32,71

3

0

0

29,05

4

2,38

0

0

6

26,55

30,05

0

Крок 2. Визначимо оцінки нульових клітин:

Крок 3. Викреслюємо клітку з максимальною оцінкою. Включаємо дану клітку в шлях обходу. (4 - 5)

Крок 4. Переписуємо матрицю відстаней, накладаючи заборону на одну з кліток для виключення передчасного замикання контуру (в клітку 6 - 4 ставимо ∞).


1

3

4

2

0

2,42

3

0

0

6

26,55

30,05

Четвертий етап.

Крок 1. Наведемо матрицю відстаней по рядках і стовпцях.


1

3

4


2

0

2,42

0

3

0

0

0

6

26,55

30,05

26,55


1

3

4

2

0

2,42

3

0

0

6

0

3,50

Крок 2. Визначимо оцінки нульових клітин:

Крок 3. Викреслюємо клітку з максимальною оцінкою. Включаємо дану клітку в шлях обходу. (3 - 4)

Крок 4. Переписуємо матрицю відстаней, накладаючи заборону на одну з кліток для виключення передчасного замикання контуру (в клітку 6 - 3 ставимо ∞).


1

3

2

0

6

0

П'ятий етап.

Залишилися не задіяними зв'язку 2 - 3 і 6 - 1.

У результаті отримуємо наступний ланцюжок:

1 → 2 → 3 → 4 → 5 → 6 → 1

Довжина шляху становить:

L = 18, 87 +32,06 +31,76 +32,14 +22,14 +97,42 = 234,39

це і є найкоротший шлях.

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Завдання
70.6кб. | скачати


Схожі роботи:
Рішення задачі лінійного програмування симплекс методом
Рішення задач лінійного програмування симплекс методом
Рішення задачі лінійного програмування графічним методом
Рішення задачі лінійного програмування симплексним методом
Графічне рішення задачі лінійного програмування в економіці
Графічний метод розв язання задачі лінійного програмування Основи аналізу моделі на чутливість
Основні поняття математичного програмування Побудова моделі задачі лінійного програмування
Розвязок задачі лінійного програмування
Побудова математичної моделі задачі лінійного програмування
© Усі права захищені
написати до нас
Рейтинг@Mail.ru