Лабораторная работа - решение задач по дисциплине Методы исследования операций - файл n1.doc

Лабораторная работа - решение задач по дисциплине Методы исследования операций
Скачать все файлы (214.5 kb.)

Доступные файлы (1):
n1.doc215kb.17.02.2014 05:15скачать

n1.doc







«Методы исследования операций»

(математика-2)

вариант № 3

Задание 1.

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

;

.

Решение.

Составим функцию Лагранжа:

.

Найдем частные производные этой функции по приравняем их к нулю, получим следующую систему уравнений:



Решая систему, получим:



Откуда находим ; . Выбираем наименьшее значение функции .

Задание 2.

При помощи симплекс-метода решить линейную задачу: найти максимум функции на множестве :

;

.

Решение.

Введем дополнительные переменные и перейдем от ограничений-неравенств к ограничениям-равенствам:



Составим симплекс таблицу для 1-ой итерации. В качестве базисных возьмем переменные .

Базис

Св. члены











4

2

4

1

0



5

3

2

0

1



0

-3

-5

0

0

Отмечаем столбец соответствующий наибольшему по модулю отрицательному числу из последней строки таблицы (столбец ). Переменную будем вводить в базис.

Разделим свободные члены на соответствующий положительные числа из выделенного столбца и выберем наименьшее частное: . Отмечаем строку соответствующую наименьшему частному (строка ). Переменную будем выводить из базиса. На пересечении выделенного столбца и строки отметим разрешающий элемент: число 4.

Разделим элементы выделенной строки на разрешающий элемент и запишем на месте прежней в новой таблице.

Базис

Св. члены









Множитель



1

0,5

1

0,25

0






3

2

0

-0,5

1

-2



5

-0,5

0

1,25

0

5

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

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

Отмечаем столбец соответствующий наибольшему по модулю отрицательному числу из последней строки таблицы (столбец ). Переменную будем вводить в базис.

Разделим свободные члены на соответствующий положительные числа из выделенного столбца и выберем наименьшее частное: . Отмечаем строку соответствующую наименьшему частному (строка ). Переменную будем выводить из базиса. На пересечении выделенного столбца и строки отметим разрешающий элемент: число 2.

Разделим элементы выделенной строки на разрешающий элемент и запишем на месте прежней в новой таблице.

Базис

Св. члены









Множитель



0,25

0

1

0,375

-0,25

-0,5



1,5

1

0

-0,25

0,5






5,75

0

0

0

0,25

0,5

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

Так как в последней строке нет отрицательных чисел, то оптимальное решение найдено.

При и функция достигает своего максимума .

Задание 3.

Методом динамического программирования решить задачу распределения ресурсов: распределить 200 единиц ресурса между четырьмя предприятиями при условии, что эффективность вложений (функции ) заданы в таблице











40

5

6

4

6

80

8

9

7

10

120

12

13

13

12

160

15

16

17

15

200

19

18

20

17

Решение.

Обозначим через количество средств, выделенных -ому предприятию, .

Суммарная прибыль .

Переменные удовлетворяют ограничениям: .

Уравнения состояний в данной задаче имеют вид:

,

где - параметр состояния – количество средств, оставшихся после -го шага.

Введем в рассмотрение функцию - условную оптимальную прибыль, полученную от -го, -го, …, 4-го предприятий, если между ними распределялись оптимальным образом средства ().

Уравнения для решения задачи:



Последовательно решаем записанные уравнения, проводя условную оптимизацию каждого шага. Ход решения представим в виде таблицы:































1

2

3

4

5

6

7

8

9

10

11

12

0

0

0

0

0

0

0

0

0

0

0

0

40

0

40

40

0

0+6=6

4+0=4

6

40

0+6=6

6+0=6

6

0

40

0+6=6

5+0=5

6

0

80

0

40

80

80

40

0

0+10=10

4+6=10

7+0=7

10

0

40

0+10=10

6+6=12

9+0=9

12

40

0+12=12

5+6=11

8+0=8

12

0

120

0

40

80

120

120

80

40

0

0+12=12

4+10=14

7+6=13

13+0=13

14

40

0+14=14

6+10=16

9+6=15

13+0=13

16

40

0+16=16

5+12=17

8+6=14

12+0=12

17

40

160

0

40

80

120

160

160

120

80

40

0

0+15=15

4+12=16

7+10=17

13+6=19

17+0=17

19

120

0+19=19

6+14=20

9+10=19

13+6=19

16+0=16

20

40

0+20=20

5+16=21

8+12=20

12+6=18

15+0=15

21

40

200

0

40

80

120

160

200

200

160

120

80

40

0

0+17=17

4+15=19

7+12=19

13+10=23

17+6=23

20+0=20

23

120

160

0+23=23

6+19=25

9+14=23

13+10=23

16+6=22

18+0=18

25

40

0+25=25

5+20=25

8+16=24

12+12=24

15+6=21

19+0=19

25

0

40

Выбираем максимальное из столбца 11, получаем: . Тогда . в столбце 9 находим . Далее . Из столбца 6: . Наконец, и . Т.е. или

Получаем два оптимальных распределения средств между предприятиями:

1 вариант: максимум суммарной прибыли равен 25 усл. ед. при условии, что 1-му предприятию выделено 0 усл.ед.; 2-му предприятию – 40 усл.ед.; 3-му предприятию – 120 усл.ед.; 4-му предприятию – 40 усл.ед.

2 вариант: максимум суммарной прибыли равен 25 усл. ед. при условии, что 1-му предприятию выделено 40 усл.ед.; 2-му предприятию – 40 усл.ед.; 3-му предприятию – 40 усл.ед.; 4-му предприятию – 80 усл.ед.
Учебный текст
© perviydoc.ru
При копировании укажите ссылку.
обратиться к администрации