Математика 2

<

092613 0037 21 Математика 2Задание № 1

Найти область решение системы неравенств:

092613 0037 22 Математика 2

Найдем точки для построения графиков:

(1) (0; 5) (5; 0)

(2) (5; 0) (0; -5)

092613 0037 23 Математика 2

Ответ: область решение системы неравенств – треугольник с вершинами А (5; 0), В (7; 2) и С (7; -2)

 

Задание № 2

Привести к канонической форме задачу ЛП:

092613 0037 24 Математика 2

Решение.

092613 0037 25 Математика 2

Ответ:

092613 0037 26 Математика 2

 

Задание № 3

Решить графически задачу ЛП:

092613 0037 27 Математика 2

Решение.

092613 0037 28 Математика 2

Найдем точки для построения графиков:

(1) (5;2) (2; 0)

(2) (2; 0) (0; 1)

Градиент увеличения функции 092613 0037 29 Математика 2

Область решения системы неравенств показана на рис. 1 штриховкой.

092613 0037 210 Математика 2

Рис. 1

Точка А: 092613 0037 211 Математика 2

Хопт. = (1; 0,5)

092613 0037 212 Математика 2

Ответ:
092613 0037 213 Математика 2

Задание № 4

 

Решить задачу ЛП симплекс-методом:

092613 0037 214 Математика 2

 

 

 

 

Решение.

Сделаем систему разрешенной методом Жордано-Гаусса:

 

X1

Х2

Х3

Х4

Х5

аi

1.

1 

-2 

0 

0 

1 

2

2 

4 

0 

-1 

0 

8

0 

1 

-1 

0 

0 

3

2.

1 

-2 

0 

0 

1 

2

0

8

0

-1

-2

4

0 

1 

-1 

0 

0 

3

3.

1

0

-2

0

1

8

0

0

-8

1

2

20 

0 

1 

-1 

0 

0 

3

 

Базисные переменные: X1, Х2, Х4

Свободные переменные: X3, Х4

Базисная система:

092613 0037 215 Математика 2

Заполним исходную симплекс-таблицу:

 

Сi

Xi

-5

-2 

-3 

0 

0 

0 

ai0/aip

ai0

X1

X2

X3

X4

Х5

-2 

Х1

8

1 

0 

-2 

0 

1 

 

0 

Х4

20 

0 

0 

-8 

1 

2 

 

-3 

Х2

3 

0 

1 

-1 

0 

0 

 
 

F(Xi)

-20

0 

0 

7 

0

0

 

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

Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент.

3. Определение новой свободной переменной.

Отношение ai0/aip вычислить невозможно, так как все элементы этого столбца отрицательны.

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

 

Ответ: Fmin = F(8; 3;0; 4; 0) = -20.

Задание № 5

Математическая модель транспортной задачи:

F = ∑∑cijxij, (1)

при условиях:

∑xij = ai, i = 1,2,…, m, (2)

∑xij = bj, j = 1,2,…, n, (3)

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

 

1

2

3

Запасы

1

2

3

2

50

2

2

4

5

70

3

6

5

7

60

Потребности

60

60

50

 

 

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 50 + 70 + 60 = 180

∑b = 60 + 60 + 50 = 170

Суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 10 (180—170). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу.

 

 

1

2

3

4

Запасы

1

2

3

2

0

50

2

2

4

5

0

70

3

6

5

7

0

60

Потребности

60

60

50

10

 

 

Этап I. Поиск первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

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

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

Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Первый минимальный элемент в 4 столбце равен 0

Для этого элемента запасы равны 50, потребности 10. Поскольку минимальным является 10, то вычитаем его.

x14 = min(50,10) = 10.

2

3

2

0

50 — 10 = 40

2

4

5

x

70

6

5

7

x

60

60

60

50

10 — 10 = 0

0

 

 

Далее выбираем элемент 2 в первом столбце.

Для этого элемента запасы равны 40, потребности 60. Поскольку минимальным является 40, то вычитаем его.

x11 = min(40,60) = 40.

2

x

x

0

40 — 40 = 0

2

4

5

x

70

6

5

7

x

60

60 — 40 = 20

60

50

0

0

 

 

Следующий элемент равен 2

Для этого элемента запасы равны 70, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x21 = min(70,20) = 20.

2

x

x

0

0

2

4

5

x

70 — 20 = 50

x

5

7

x

60

20 — 20 = 0

60

50

0

0

Искомый элемент равен 4

Для этого элемента запасы равны 50, потребности 60. Поскольку минимальным является 50, то вычитаем его.

x22 = min(50,60) = 50.

2

x

x

0

0

2

4

x

x

50 — 50 = 0

x

5

7

x

60

0

60 — 50 = 10

50

0

0

 

Искомый элемент равен 5

Для этого элемента запасы равны 60, потребности 10. Поскольку минимальным является 10, то вычитаем его.

x32 = min(60,10) = 10.

2

x

x

0

0

2

4

x

x

0

x

5

7

x

60 — 10 = 50

0

10 — 10 = 0

50

<

0

0

Искомый элемент равен 7

Для этого элемента запасы равны 50, потребности 50. Поскольку минимальным является 50, то вычитаем его.

x33 = min(50,50) = 50.

2

x

x

0

0

2

4

x

x

0

x

5

7

x

50 — 50 = 0

0

0

50 — 50 = 0

0

0

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

 

1

2

3

4

Запасы

1

2[40]

3

2

0[10]

50

2

2[20]

4[50]

5

0

70

3

6

5[10]

7[50]

0

60

Потребности

60

60

50

10

 

 

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n — 1 = 6. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 2*40 + 0*10 + 2*20 + 4*50 + 5*10 + 7*50 = 720

Этап II. Улучшение опорного плана методом потенциалов.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v1 = 2; 0 + v1 = 2; v1 = 2

u2 + v1 = 2; 2 + u2 = 2; u2 = 0

u2 + v2 = 4; 0 + v2 = 4; v2 = 4

u3 + v2 = 5; 4 + u3 = 5; u3 = 1

u3 + v3 = 7; 1 + v3 = 7; v3 = 6

u1 + v4 = 0; 0 + v4 = 0; v4 = 0

 

v1=2

v2=4

v3=6

v4=0

u1=0

2[40]

3

2

0[10]

u2=0

2[20]

4[50]

5

0

u3=1

6

5[10]

7[50]

0

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

(1;2): 0 + 4 > 3; ∆12 = 0 + 4 — 3 = 1

(1;3): 0 + 6 > 2; ∆13 = 0 + 6 — 2 = 4

(2;3): 0 + 6 > 5; ∆23 = 0 + 6 — 5 = 1

(3;4): 1 + 0 > 0; ∆34 = 1 + 0 — 0 = 1

max(1,4,1,1) = 4

Выбираем максимальную оценку свободной клетки (1;3): 2

Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

1

2

3

4

Запасы

1

2[40][-]

3

2[+]

0[10]

50

2

2[20][+]

4[50][-]

5

0

70

3

6

5[10][+]

7[50][-]

0

60

Потребности

60

60

50

10

 

 

Цикл приведен в таблице (1,3; 1,1; 2,1; 2,2; 3,2; 3,3; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 40. Прибавляем 40 к объемам грузов, стоящих в плюсовых клетках и вычитаем 40 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

1

2

3

4

Запасы

1

2

3

2[40]

0[10]

50

2

2[60]

4[10]

5

0

70

3

6

5[50]

7[10]

0

60

Потребности

60

60

50

10

 

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v3 = 2; 0 + v3 = 2; v3 = 2

u3 + v3 = 7; 2 + u3 = 7; u3 = 5

u3 + v2 = 5; 5 + v2 = 5; v2 = 0

u2 + v2 = 4; 0 + u2 = 4; u2 = 4

u2 + v1 = 2; 4 + v1 = 2; v1 = -2

u1 + v4 = 0; 0 + v4 = 0; v4 = 0

 

v1=-2

v2=0

v3=2

v4=0

u1=0

2

3

2[40]

0[10]

u2=4

2[60]

4[10]

5

0

u3=5

6

5[50]

7[10]

0

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

(2;3): 4 + 2 > 5; ∆23 = 4 + 2 — 5 = 1

(2;4): 4 + 0 > 0; ∆24 = 4 + 0 — 0 = 4

(3;4): 5 + 0 > 0; ∆34 = 5 + 0 — 0 = 5

max(1,4,5) = 5

Выбираем максимальную оценку свободной клетки (3;4): 0

Для этого в перспективную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

1

2

3

4

Запасы

1

2

3

2[40][+]

0[10][-]

50

2

2[60]

4[10]

5

0

70

3

6

5[50]

7[10][-]

0[+]

60

Потребности

60

60

50

10

 

 

Цикл приведен в таблице (3,4; 3,3; 1,3; 1,4; ).

В результате получим новый опорный план.

 

1

2

3

4

Запасы

1

2

3

2[50]

0

50

2

2[60]

4[10]

5

0

70

3

6

5[50]

7[0]

0[10]

60

Потребности

60

60

50

10

 

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v3 = 2; 0 + v3 = 2; v3 = 2 u3 + v3 = 7; 2 + u3 = 7; u3 = 5

u3 + v2 = 5; 5 + v2 = 5; v2 = 0 u2 + v2 = 4; 0 + u2 = 4; u2 = 4

u2 + v1 = 2; 4 + v1 = 2; v1 = -2 u3 + v4 = 0; 5 + v4 = 0; v4 = -5

 

v1=-2

v2=0

v3=2

v4=-5

u1=0

2

3

2[50]

0

u2=4

2[60]

4[10]

5

0

u3=5

6

5[50]

7[0]

0[10]

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

(2;3): 4 + 2 > 5; ∆23 = 4 + 2 — 5 = 1

Выбираем максимальную оценку свободной клетки (2;3): 5. Строим цикл для клетки (2;3).

 

1

2

3

4

Запасы

1

2

3

2[50]

0

50

2

2[60]

4[10][-]

5[+]

0

70

3

6

5[50][+]

7[0][-]

0[10]

60

Потребности

60

60

50

10

 

 

Цикл приведен в таблице (2,3; 2,2; 3,2; 3,3; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

1

2

3

4

Запасы

1

2

3

2[50]

0

50

2

2[60]

4[10]

5[0]

0

70

3

6

5[50]

7

0[10]

60

Потребности

60

60

50

10

 

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v3 = 2; 0 + v3 = 2; v3 = 2

u2 + v3 = 5; 2 + u2 = 5; u2 = 3

u2 + v1 = 2; 3 + v1 = 2; v1 = -1

u2 + v2 = 4; 3 + v2 = 4; v2 = 1

u3 + v2 = 5; 1 + u3 = 5; u3 = 4

u3 + v4 = 0; 4 + v4 = 0; v4 = -4

 

v1=-1

v2=1

v3=2

v4=-4

u1=0

2

3

2[50]

0

u2=3

2[60]

4[10]

5[0]

0

u3=4

6

5[50]

7

0[10]

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.

Минимальные затраты составят:

F(x) = 2*50 + 2*60 + 4*10 + 5*50 + 0*10 = 510

 

 

<

Комментирование закрыто.

MAXCACHE: 1.04MB/0.02823 sec

WordPress: 21.84MB | MySQL:118 | 2,536sec