Елементи інформаційних технологій в математичному програмуванні

  • Вид работы:
    Контрольная работа
  • Предмет:
    Математика
  • Язык:
    Русский
    ,
    Формат файла:
    MS Word
    132,72 kb
  • Опубликовано:
    2010-06-08
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

Елементи інформаційних технологій в математичному програмуванні

Завдання 1

Розв'язати графічним способом при умовах:

 

Розв'язування

Зобразимо розв’язок системи нерівностей та вектор F (1;2):


Максимум функції досягається в точці А:


Мінімум функції досягається в точці В:

 

Завдання 2

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

Розв'язування

Спочатку перевіримо задачу на замкненість:

.

Задача є замкненою.

Вихідна таблиця:

А/В

10

20

25

40

25

4

 

7

 

2

 

5

 



 

 

15

9

 

3

 

4

 

6

 

 

 



35

8

 

5

 

9

 

3

 

 

 


 

20

2

 

1

 

7

 

4

 

 


 


 

 

 


Складемо початковий план методом мінімального елементу:

А/В

10

20

25

40

25

4

 

7

 

2

 

5

 

 

 

25

 

15

9

 

3

 

4

 

6

 

10

 

 

5

35

8

 

5

 

9

 

3

 

 

 

 

35

20

2

 

1

 

7

 

4

 

 

20

 

 


Опорний план є виродженим, адже число зайнятих клітинок менше ніж m+n-1=8. Зробимо його невиродженим, розміщуючи базисні нулі в клітину з координатами (i,j)=(1,1) та (4,1). Вирішимо задачу методом потенціалів:

А/В

10

20

25

40

U

25

4

 

 

2

 

5

 

0

0

 

25

 

15

9

-

3

 +

4

 

6

 

5

10

 

 

5

35

8

 

5

 

9

 

3

 

2

 

 

 

35

20

2

+

1

 -

7

 

4

 

-2

0

20

 

 


4

3

2

1

295


Сформуємо оціночну матрицю з елементів :

Оціночна матриця

0

4

0

4

0

-5

-3

0

2

0

5

0

0

7

5


План не є оптимальним, адже є від’ємні елементи.

Переміщуємо по циклу вантаж величиною 10 одиниць, додаючи цю величину у клітинах зі знаком «+», та віднімаючи її від клітин зі знаком «- ».

Маємо,

А/В

10

20

25

40

U

25

4

 -

7

 

2

 

5

 +

0

0

 

25

 

15

9

 

3

 +

4

 

6

-

0

 

10

 

5

35

8

 

5

 

9

 

3

 

-3

 

 

 

35

20

2

 +

1

-

7

 

4

 

-2

10

10

 

 

V

3

2

6

245


Оціночна матриця

0

4

0

-1

5

0

2

0

7

5

10

0

0

0

7

0


План не є оптимальним, адже є від’ємні елементи.

Переміщуємо по циклу вантаж величиною 0 одиниць, додаючи цю величину у клітинах зі знаком «+», та віднімаючи її від клітин зі знаком «- ».

Отримаємо,

А/В

10

20

25

40

U

25

4

 

7

 

2

 

5

 

0

 

 

25

0

15

9

 

3

 

4

 

6

 

1

 

10

 

5

35

8

 

5

 

9

 

3

 

-2

 

 

35

20

2

 

1

 

7

 

4

 

-1

10

10

 

 

V

3

2

2

5

245


Оціночна матриця

 

1

5

0

0

 

5

0

1

0

 

7

5

9

0

 

0

0

6

0

 

 


Як бачимо усі . Адже отриманий план є оптимальним.

При цьому загальна вартість перевезень складає 245 і є мінімальною.

Завдання 3

Розв'язати задачу ЛП симплекс-методом:

 

Розв'язування

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


Вирішимо задачу симплекс методом.

Базис

БП

x 1

x 2

x 3

x 4

x 5

x4

6

1

3

-3

1

0

x5

4

-2

1

1

0

1

ИС

3

-2

-1

0

0

Обрано ключовий елемент (1,2)

Базис

БП

x 1

x 2

x 3

x 4

x 5

x2

2

1/3

1

-1

1/3

0

x5

2

-7/3

0

2

-1/3

1

ИС

4

11/3

0

-3

2/3

0

 Обрано ключовий елемент (2,3)

Базис

БП

x 1

x 2

x 3

x 4

x 5

x2

3

-5/6

1

0

1/6

1/2

x3

1

-7/6

0

1

-1/6

1/2

ИС

7

1/6

0

0

1/6

3/2


Отримано оптимальний план x* = (0, 3, 1). За нього fmin = (x*) = -7.

Список використаних джерел

1. Бурий В.В., Шевченко І.В. Математичне програмування. — К.: НАУ, 2007. — 168с.

2. Єгоршин О.О., Малярець Л.М. Математичне програмування. — Х.: ВД "ІНЖЕК", 2006. — 383с.

3. Жильцов О.Б., Кулян В.Р., Юнькова О.О. Математичне програмування (з елементами інформаційних технологій) / Міжрегіональна академія управління персоналом / Олена Олександрівна Юнькова (ред.). — К.: МАУП, 2006. — 184с.

4. Зеленський К.Х. Математичне програмування. — К.: Університет "Україна", 2007. — 241c.

5. Івченко І.Ю. Математичне програмування. — К.: Центр учбової літератури, 2007. — 232с.

Похожие работы на - Елементи інформаційних технологій в математичному програмуванні

 

Не нашел материал для своей работы?
Поможем написать качественную работу
Без плагиата!