Решение задач линейным программированием
Департамент
образования города Москвы
Самарский
филиал Государственного образовательного учреждения
высшего
профессионального образования города Москвы
«Московский
городской педагогический университет»
Факультет
информатики
Кафедра
высшей математики и информатики
Контрольная
работа по дисциплине:
Компьютерное
моделирование.
Студента 5 курса
заочного отделения
Антонов С.Ю.
Проверил: Макарова И.С.
Самара
2012 г.
Задача №1. Решить задачу линейным
программированием
Магазин реализует три группы
товаров. Затраты ресурсов на тысячу рублей товарооборота даны в таблице.
|
Ресурсы
|
Затраты на тысячу рублей товарооборота
|
Имеющиеся ресурсы
|
|
|
|
|
|
|
(х1) 1
|
(х2) 2
|
(х3) 3
|
|
|
А
|
10
|
30
|
25
|
4400
|
|
В
|
6
|
5
|
8
|
1180
|
|
С
|
26
|
40
|
32
|
6420
|
|
Прибыль на тысячу рублей товарооборота, руб.
|
60
|
90
|
80
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рассчитать структуру и объём
товарооборота, обеспечивающих максимальную прибыль.
Составим систему ограничения:
х1+30х2+25х3≤
4400
х1+5х2+8х3≤
1180
х1+40х2+32х30х8
≤ 6420
линейное программирование excel
Составим целевую функцию задачи:
=60х1+90х2+80х3
max9
Условия не отрицательности задачи
имеют вид: Х1, Х2,х3 ≥ 0.
Решение задачи в электронной таблице
Excel:
Создаем форму и заполняем, вписывая
переменные и формулы ограничения:
Выполняем команду в поиске решений:
найти решение:
Решение найдено.
Задача №2. Решить транспортную
задачу
На трёх хлебокомбинатах ежедневно
производится 110, 190, и 90 т муки. Эта мука потребляется четырьмя
хлебозаводами, ежедневные потребности которых равны соответственно 80, 60, 170,
80 т. Составить такой план доставки муки, при котором общая стоимость перевозок
является минимальной, тарифы перевозок 1т муки с хлебокомбинатов к каждому из
хлебозаводов задаются матрицей.
С=
Составляем транспортную таблицу:
|
хлебозавод
|
I х/з 80
|
II х/з 60
|
III х/з 170
|
IV х/з 80
|
|
хлебокомбинат
|
|
|
|
|
|
I х/к (110)
|
80
|
8
|
30
|
1
|
|
9
|
|
7
|
|
II х/к (190)
|
|
4
|
30
|
6
|
160
|
2
|
|
12
|
|
III х/к (90)
|
|
3
|
|
5
|
10
|
8
|
80
|
9
|
Составим целевую функцию задачи:
=80*8+30*1+30*6+160*2+10*8+80*9=640+30+180+320+80+720=1970
д.е.
Решим транспортную задачу в
электронной таблице Excel:
Заполняем окно поиска решений:
Выполняем команду в поиске решений:
найти решение:
Решение найдено.
Задача №3. Решить задачу о
назначениях
Назначить пятерых рабочих на пять
должностей на основе матрицы стоимостей, приведенной ниже.
|
Должности
|
|
|
1
|
2
|
3
|
4
|
5
|
|
1
|
14
|
15
|
19
|
18
|
17
|
|
Рабочие
|
2
|
16
|
14
|
18
|
13
|
|
3
|
17
|
13
|
20
|
18
|
16
|
|
4
|
15
|
12
|
15
|
16
|
18
|
|
5
|
12
|
17
|
13
|
14
|
19
|
Решим задачу Венгерским методом:
|
должность кандидат
|
Д I
|
Д II
|
Д III
|
Д IV
|
Д VI
|
|
К I
|
14
|
15
|
19
|
18
|
17
|
|
К II
|
16
|
14
|
18
|
13
|
15
|
|
К III
|
17
|
13
|
20
|
18
|
16
|
|
К IV
|
15
|
12
|
15
|
16
|
18
|
|
К VI
|
12
|
17
|
13
|
14
|
19
|
этап (строчки, столбцы).
|
должность кандидатД IД IIД IIIД IVД VI
|
|
|
|
|
|
|
К I
|
0
|
1
|
5
|
4
|
3
|
|
К II
|
3
|
1
|
5
|
0
|
2
|
|
К III
|
0
|
7
|
5
|
3
|
|
К IV
|
3
|
0
|
3
|
4
|
6
|
|
К VI
|
0
|
5
|
1
|
2
|
7
|
|
должность кандидатД IД IIД IIIД IVД VI
|
|
|
|
|
|
|
К I
|
0
|
1
|
4
|
4
|
1
|
|
К II
|
3
|
1
|
4
|
0
|
0
|
|
К III
|
4
|
0
|
6
|
5
|
1
|
|
К IV
|
3
|
0
|
2
|
4
|
4
|
|
К VI
|
0
|
5
|
0
|
2
|
5
|
этап. Построение решения.
|
должность кандидатД IД IIД IIIД IVД VI
|
|
|
|
|
|
|
К I
|
0
|
1
|
4
|
4
|
1
|
|
К II
|
3
|
1
|
4
|
0
|
0
|
|
К III
|
4
|
0
|
6
|
5
|
1
|
|
К IV
|
3
|
0
|
4
|
4
|
|
К VI
|
0
|
5
|
0
|
2
|
5
|
Количество выделенных нулей не
совпадает с размерностью таблицы.
Переходим к III этапу.
этап. Получение дополнительных
нулей.
|
должность кандидатД IД IIД IIIД IVД VI
|
|
|
|
|
|
|
К I
|
0
|
1
|
4
|
4
|
1
|
|
К II
|
3
|
1
|
4
|
0
|
0
|
|
К III
|
4
|
0
|
6
|
5
|
1
|
|
К IV
|
3
|
0
|
2
|
4
|
4
|
|
К VI
|
0
|
5
|
0
|
2
|
5
|
Находим минимальное значение среди
не зачеркнутых элементов= 1
|
должность кандидатД IД IIД IIIД IVД VI
|
|
|
|
|
|
|
К I
|
0
|
2
|
4
|
4
|
1
|
|
К II
|
3
|
2
|
4
|
0
|
0
|
|
К III
|
3
|
0
|
5
|
4
|
0
|
|
К IV
|
2
|
0
|
1
|
3
|
3
|
|
К VI
|
0
|
0
|
2
|
5
|
Найденное решение не единственное.
Составим целевую функцию задачи:
Z=14+13+16+12+13=68.
Решим задачу о назначениях в
электронной таблице Excel:
Создаем форму и заполняем, вписывая
переменные и формулы ограничения:
Заполняем окно поиска решений:
Выполняем команду в поиске решений:
найти решение:
Задача решена.