Всероссийский заочный финансово-экономический институт

Кафедра Математики и информатики

лабораторная Работа 1, 2

по дисциплине «ЭММ и ПМ»

Уфа

1 Задача об оптимальном использовании ограниченных ресурсов

Небольшая фирма производит два вида продукции: столы и стулья. Для изготовления одного стула требуется 3 м древесины, а для изготовления одного стола – 7 м. На изготовление одного стула уходит 2 часа рабочего времени, а на изготовление стола – 8 часов. Каждый стул приносит 1 ден. ед. прибыли, а каждый стол - 3 ден. ед. Сколько стульев и сколько столов должна изготовить эта фирма для получения максимальной прибыли, если она располагает 200 м древесины и 400 часами рабочего времени?

Экономико-математическая модель задачи

Пусть х1 – количество столов, которое необходимо изготовить; х2 – количество стульев, которое необходимо произвести.

Тогда целевая функция будет задаваться следующим образом:

f (x) = 3х1 + х2           max.

Ограничения задачи имеют вид:

1 + 3х2 ≤ 200    – ограничение по сырью;

1 + 2х2 ≤ 400    – ограничение по труду;

х1 ≥ 0                   – ограничение по столам;

х2 ≥ 0                   − ограничение по стульям.

Решение

1.                Создать форму для ввода условий задачи. Запустить Excel, выбрав Microsoft Excel из подменю Программы главного меню Windows. В открывшейся книге на листе 1 создать текстовую форму – таблицу для ввода условий задачи (рис. 1).

2.                Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). Обозначим через х1, х2 количество столов и стульев соответственно. В задаче оптимальные значения компонент вектора Х = (х1, х2) будут помещены в ячейках В3:C3, оптимальное значение целевой функции – в ячейке D4.

Рис. 1

Рис. 2

3.                Ввести исходные данные задачи в созданную форму – таблицу, представленную на рис. 2.

4.                Сохранить таблицу. Для этого в строке Меню выбрать имя Файл, а в подменю Сохранить как… В появившемся окне выбрать нужную папку для сохранения и в строке Имя файла присвоить имя сохраняемой таблице.

5.                Ввести зависимость для целевой функции:

·                    Поместить курсор в ячейку D4, произойдет выделение ячейки.

·                    Поместить курсор на кнопку Мастер функций, расположенную на панели инструментов.

·                    Нажать Enter. На экране появится диалоговое окно Мастер функций шаг 1 из 2.

·                    В окне Функции выбрать категорию Математические.

·                    В окне Функции выбрать строку СУММПРОИЗВ (рис. 3). На экране появляется диалоговое окно СУММПРОИЗВ (рис. 4).

·                    В строку Массив 1 ввести В3:С3.

·                    В строку Массив 2 ввести В4:С4.

Рис. 3

Рис. 4

Массив 1 будет использоваться при вводе зависимостей для ограничений, поэтому на этот массив надо сделать абсолютную ссылку. На рис. 5 показано, что в ячейку D4 введена функция.

Рис. 5

6.                Ввести зависимости для ограничений (рис. 6).

·                    Поместить курсор в ячейку D4.

·                    На панели инструментов нажать кнопку Копировать в буфер.

·                    Поместить курсор в ячейку D8.

·                    На панели инструментов нажать кнопку Вставить из буфера.

·                    Поместить курсор в ячейку D9.

Рис. 6

·                    На панели инструментов нажать кнопку Вставить из буфера. Содержимое ячеек  D4, D8, D9 необходимо проверить. Они обязательно должны содержать информацию, как это показано на рис. 7.

Рис. 7

·                    В меню Сервис выбрать команду Поиск решения. Появляется диалоговое окно Поиск решения (рис. 8).

Рис. 8

7.                Запустить команду Поиск решения.

8.                Назначить ячейку для целевой функции (установить целевую ячейку), указать адреса изменяемых ячеек.

·                    Поместить курсор в строку Установить целевую ячейку.

·                    Ввести адрес ячейки $D$4.

·                    Внести тип целевой функции в зависимости от условия задачи. Для этого отметим, чему равна целевая функция – Максимальному значению.

·                    Поместить курсор в строку Изменяя ячейки.

·                    Ввести адреса искомых переменных $В3:$С3 (рис. 9).

Рис. 9

9.                Ввести ограничения.

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

·                    В строке Ссылка на ячейку ввести адрес $D$8.

·                    Ввести знак ограничения.

·                    В строке Ограничения ввести адрес $F$8 (рис. 10).

Рис. 10

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

·                    В строке Ссылка на ячейку ввести адрес $D$9.

·                    Ввести знак ограничения.

·                    В строке Ограничения ввести адрес $F$9 (рис. 11).

Рис. 11

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

·                    В строке Ссылка на ячейку ввести адрес $B3$C3.

·                    Вместо знака выбираем выражение «цел».

·                    После введения последнего ограничения нажать на кнопку ОК.

·                    На экране появится диалоговое окно Поиск решения с введенными условиями (рис. 12).

Рис. 12

10.           Ввести параметры для решения задачи линейного программирования.

·                    В диалоговом окне поместить указатель мышки на кнопку Параметры. На экране появится диалоговое окно Параметры поиска решения (рис. 13).

Рис. 13

·                    Установить флажки в окнах Линейная модель и неотрицательные значения.

·                    Поместить указатель мыши на кнопку ОК. На экране появится диалоговое окно Поиск решения.

·                    Поместить указатель мыши на кнопку Выполнить.

Через непродолжительное время появятся диалоговое окно Результаты поиска решения и исходная таблица с заполненными ячейками В3:С3 для значений х1, х2 и ячейка D4 с максимальным значением целевой функции (рис. 14).

Рис. 14

Вывод: полученное решение задачи об оптимальном использовании ограниченных ресурсов означает, что максимальный доход 85 ден. ед. фирма может получить при выпуске и реализации 28 столов и 1 стула. При этом трудовые ресурсы и сырье будет использовано не полностью: 226 ч из 400 ч и 199 м из 200 м соответственно.

2 Задача о назначениях

Мастер должен назначить на 10 типовых операций 12 рабочих. Данные о времени, которое затрачивают рабочие на выполнение каждой операции, приведены ниже в таблице (матрица эффективностей назначений)

Операции

Рабочие

О1

О2

О3

О4

О5

О6

О7

О8

О9

О10

Р1

29

31

16

16

17

34

20

28

16

13

Р2

29

25

22

30

24

31

37

23

16

27

Р3

27

32

-

14

34

30

27

16

19

17

Р4

21

35

-

32

31

28

30

29

31

16

Р5

21

36

-

14

24

30

21

28

29

27

Р6

28

35

25

30

22

16

-

18

25

18

Р7

27

34

33

26

14

19

18

37

19

16

Р8

27

34

27

30

37

37

26

22

35

33

Р9

16

26

18

26

16

20

31

34

28

29

Р10

16

22

33

22

21

19

19

37

36

24

Р11

26

35

13

14

17

36

17

17

25

21

Р12

34

25

19

14

36

36

17

36

26

33

 В матрице эффективностей назначений проставлен запрет «-», если рабочий не может выполнять соответствующую операцию.

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

Экономико-математическая модель задачи

Пусть хij – число рабочих i, назначенных на выполнение операции j.

              

хij =        0, если рабочий i не назначен на выполнение операции j,

               1, если рабочий i назначен на выполнение операции j.

Тогда целевая функция задается следующим соотношением:

f (x) = х11 + х21 + х31 + х41 + х51 + х61 + х71 + х81 + х91 + х101 + х111 + х121 + х12 + х22 + х32 + х42 + х52 + х62 + х72 + х82 + х92 + х102 + х112 + х122 + х13 + х23 + х33 + х43 + х53 + х63 + х73 + х83 + х93 + х103 + х113 + х123 + х14 + х24 +  х34 + х44 + х54 + х64 + х74 + х84 + х94 + х104 + х114 + х124 + х15 + х25 + х35 +  х45 + х55 + х65 + х75 + х85 + х95 + х105 + х115 + х125 + х16 + х26 + х36 + х46 + х56 + х66 + х76 + х86 + х96 + х106 + х116 + х126 + х17 + х27 + х37 + х47 + х57 + х67 + х77 + х87 + х97 + х107 + х117 + х127 + х18 + х28 + х38 + х48 + х58 + х68 + х78 + х88 + х98 + х108 + х118 + х128 + х19 + х29 + х39 + х49 + х59 + х69 + х79 + х89 + х99 + х109 + х119 + х129 + х110 + х210 + х310 + х410 + х510 + х610 + х710 +  х810 + х910 + х1010 + х1110 +  х1210               min.

Ограничения задачи имеют вид:

х11 + х21 + х31 + х41 + х51 + х61 + х71 + х81 + х91 + х101 + х111 + х121 ≤ 1

х12 + х22 + х32 + х42 + х52 + х62 + х72 + х82 + х92 + х102 + х112 + х122 ≤ 1

х13 + х23 + х33 + х43 + х53 + х63 + х73 + х83 + х93 + х103 + х113 + х123 ≤ 1

х14 + х24 + х34 + х44 + х54 + х64 + х74 + х84 + х94 + х104 + х114 + х124 ≤ 1

х15 + х25 + х35 + х45 + х55 + х65 + х75 + х85 + х95 + х105 + х115 + х125 ≤ 1

х16 + х26 + х36 + х46 + х56 + х66 + х76 + х86 + х96 + х106 + х116 + х126 ≤ 1

х17 + х27 + х37 + х47 + х57 + х67 + х77 + х87 + х97 + х107 + х117 + х127 ≤ 1

х18 + х28 + х38 + х48 + х58 + х68 + х78 + х88 + х98 + х108 + х118 + х128 ≤ 1

х19 + х29 + х39 + х49 + х59 + х69 + х79 + х89 + х99 + х109 + х119 + х129 ≤ 1

х110 + х210 + х310 + х410 + х510 + х610 + х710 + х810 + х910 + х1010 + х1110 +  х1210 ≤ 1

хij =        0,           i = 1, 2,…, n

                        1.            j = 1, 2,…, m.

Решение

1.                Создать форму для решения задачи (матрица эффективностей назначений). Для этого необходимо выполнить резервирование изменяемых ячеек: в блок ячеек В3:К14 вводятся «1». Таким образом, резервируется место, где после решения задачи будет находиться распределение по операциям, обеспечивающих выполнение работ за минимальное время.

Рис. 15

2.                Ввод ограничений условий.

·                    Поместить курсор в ячейку А3 и щелкнуть знак «∑».

·                    Выделить необходимые для суммирования ячейки В3:К3 и нажать Enter.

·                    Аналогичные действия выполнить для ячеек А4-А14. Для этого поместить курсор в А3 и на панели инструментов нажать кнопку Копировать в буфер. Далее выделить ячейки А4-А14 и нажать кнопку Вставить из буфера.

·                    Ввести условия заполнения матрицы назначений. Для этого необходимо поместить курсор В15 и щелкнуть значок «∑», при этом автоматически выделяется столбец В3:В14. Нажать Enter.

·                    Аналогичным образом заполнить ячейки С15:К15. Сделать это можно следующим образом: встать на ячейку В15, на панели инструментов нажать кнопку Копировать в буфер, выделить ячейки С15:К15 и нажать кнопку Вставить из буфера.

3.                Назначение целевой функции.

·                    Поместить курсор в ячейку В31, произойдет выделение ячейки.

·                    Поместить курсор на кнопку Мастер функций, расположенную на панели инструментов.

·                    Нажать Enter. На экране появится диалоговое окно Мастер функций шаг 1 из 2.

·                    В окне Функции выбрать категорию Математические.

·                    В окне Функции выбрать строку СУММПРОИЗВ. На экране появляется диалоговое окно СУММПРОИЗВ.

·                    В строку Массив 1 ввести В18:В29.

·                    В строку Массив 2 ввести В3:К14 (рис. 16).

Рис. 16

         В поле В31 появится некоторое числовое значение, равное произведению единичных поставок на удельные коэффициенты затрат по доставке грузов (рис. 17).

Рис. 17

4.                Ввод зависимостей из математической модели (рис. 18).

·                    В меню Сервис выбрать команду Поиск решения.

·                    В открывшемся окне в поле установить целевую ячейку ввести адрес $В$31.

·                    Установить направление изменения целевой функции, равное «минимальному значению».

·                    Ввести адреса изменяемых ячеек В3:К14.

·                    Ввести ограничения задачи. Для этого нужно щелкнуть на кнопку Добавить. В поле Ссылка на ячейку ввести адреса $А$3:$А$14, в среднем поле установить знак «≤», а поле Ограничение установить адреса $А$18:$А$29. Нажать ОК.

·                    Для ввода следующего ограничения опять нажать кнопку Добавить. В поле Ссылка на ячейку ввести адреса $В$15:$К$15, в среднем поле установить знак «=», а поле Ограничение установить адреса $В$17:$К$17. Нажать ОК.

·                    Здесь же необходимо учесть, что при решении задач о назначении в Excel необходимо учитывать, что переменные xij являются булевыми. Следовательно необходимо ввести еще одно ограничение. Нажать кнопку Добавить. В поле Ссылка на ячейку ввести адреса $В$3:$К$14, в среднем поле установить значение «двоич». Нажать ОК.

Рис. 18

5.                Ввод ограничений

·                    В диалоговом окне поместить указатель мышки на кнопку Параметры. На экране появится диалоговое окно Параметры поиска решения (рис. 13).

·                    Установить флажки в окнах Линейная модель и неотрицательные значения.

·                    Поместить указатель мыши на кнопку ОК. На экране появится диалоговое окно Поиск решения.

·                    Поместить указатель мыши на кнопку Выполнить.

Рис. 19

6.                После выполнения всех вышеуказанных действий на экран выводится окно результаты поиска решения (рис. 14). В окне Тип отчета выбрать интересующий вид отчета. Нажать ОК.

1. 

2. 

3. 

4. 

5. 

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

·                    Первого работника на операцию О10 (ячейка К3);

·                    Второго работника на операцию О9 (ячейка J4);

·                    Третьего работника на операцию О8 (ячейка I5);

·                    Четвертого работника ни на какую операцию;

·                    Пятого работника на операцию О4 (ячейка Е7);

·                    Шестого работника на операцию О6 (ячейка G8);

·                    Седьмого работника на операцию О5 (ячейка F9);

·                    Восьмого работника ни на какую операцию;

·                    Девятого работника на операцию О1 (ячейка В11);

·                    Десятого работника на операцию О2 (ячейка С12);

·                   Одиннадцатого работника на операцию О3 (ячейка D13);

·                   Двенадцатого работника на операцию О7 (ячейка Н14).

3 Транспортная задача

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

Таблица тарифов на перевозку продукции и объемов запасов на складе и заказов:

 Магазин

Склад

«Колбасы»

«Мясо»

«Мясные деликатесы»

«Дина»

Запасы на складе (ед. продукции)

Черкизово

1

0

0,5

2

45

Царицыно

3

2

4

1

50

Бородино

0

2,5

2

3

15

Вешняки

4

3

1,5

2

20

Объем заказа (ед. продукции)

30

40

20

25

Экономико-математическая модель задачи

Задача является открытой, т.к. объем заказа меньше запасов на складе. Пусть хij – количество единиц продукции, которое нужно перевести с i-ого склада в j-ый магазин.

Тогда целевая функция имеет следующий вид:

f (x) = х11 + 3х21 + 4х41 + 2х22 + 2,5х32 + 3х42 + 0,5х13 + 4х23 + 2х33 +1,5 х43 + 2х14 + х24 + 3х34 + 2х44                    min.

Ограничения задачи задаются так:

х11 + 3х21 + 4х41 = 30,

22 + 2,5х32 + 3х42 = 40,

0,5х13 + 4х23 + 2х33 + 1,5х43 = 20,

14 + х24 + 3х34 + 2х44 = 25.

х11 + 0,5х13 + 2х14 ≤ 45,

21 + 2х22 + 4х23 + х24 ≤ 50,

2,5х32 + 2х33 + 3х34 ≤ 15,

41 + 3х42 + 1,5х43 + 2х44 ≤ 20.

            хij ≥ 0,  i = 1, 2,…, n    j = 1, 2,…, m

Решение

1.                Создать форму для решения задачи (матрица эффективностей назначений). Для этого необходимо выполнить резервирование изменяемых ячеек: в блок ячеек В3:К14 вводятся «1». Таким образом, резервируется место, где после решения задачи будет находиться распределение по операциям, обеспечивающих выполнение работ за минимальное время.

Рис. 20

2.                Ввод ограничений условий.

·          Поместить курсор в ячейку А3 и щелкнуть знак «∑».

·          Выделить необходимые для суммирования ячейки В3:Е3 и нажать Enter.

·          Аналогичные действия выполнить для ячеек А4-А6. Для этого поместить курсор в А3 и на панели инструментов нажать кнопку Копировать в буфер. Далее выделить ячейки А4-А6 и нажать кнопку Вставить из буфера.

·          Ввести условия заполнения матрицы назначений. Для этого необходимо поместить курсор В7 и щелкнуть значок «∑», при этом автоматически выделяется столбец В3:В6. Нажать Enter.

·          Аналогичным образом заполнить ячейки С7:Е7. Сделать это можно следующим образом: встать на ячейку В15, на панели инструментов нажать кнопку Копировать в буфер, выделить ячейки С7:Е7 и нажать кнопку Вставить из буфера.

3.                Назначение целевой функции.

·          Поместить курсор в ячейку В15, произойдет выделение ячейки.

·          Поместить курсор на кнопку Мастер функций, расположенную на панели инструментов.

·          Нажать Enter. На экране появится диалоговое окно Мастер функций шаг 1 из 2.

·          В окне Функции выбрать категорию Математические.

·          В окне Функции выбрать строку СУММПРОИЗВ. На экране появляется диалоговое окно СУММПРОИЗВ.

·          В строку Массив 1 ввести В10:Е13.

·          В строку Массив 2 ввести В3:Е6 (рис. 21).

Рис. 21

         В поле В15 появится некоторое числовое значение, равное произведению единичных поставок на удельные коэффициенты затрат по доставке грузов (рис. 22).

Рис. 22

4.                               Ввод зависимостей из математической модели (рис. 23).

·                    В меню Сервис выбрать команду Поиск решения.

·                    В открывшемся окне в поле установить целевую ячейку ввести адрес $В$15.

·                    Установить направление изменения целевой функции, равное «минимальному значению».

·                    Ввести адреса изменяемых ячеек В3:Е6.

·                    Ввести ограничения задачи. Для этого нужно щелкнуть на кнопку Добавить. В поле Ссылка на ячейку ввести адреса $А$3:$А$6, в среднем поле установить знак «≤», а поле Ограничение установить адреса $А$10:$А$13. Нажать ОК.

·                    Для ввода следующего ограничения опять нажать кнопку Добавить. В поле Ссылка на ячейку ввести адреса $В$7:$Е$7, в среднем поле установить знак «=», а поле Ограничение установить адреса $В$9:$Е$9. Нажать ОК.

Рис. 23

5.                               Ввод ограничений

·                    В диалоговом окне поместить указатель мышки на кнопку Параметры. На экране появится диалоговое окно Параметры поиска решения (рис. 13).

·                    Установить флажки в окнах Линейная модель и неотрицательные значения.

·                    Поместить указатель мыши на кнопку ОК. На экране появится диалоговое окно Поиск решения.

·                    Поместить указатель мыши на кнопку Выполнить.

Рис. 20

6.                 После выполнения всех вышеуказанных действий на экран выводится окно результаты поиска решения (рис. 14). В окне Тип отчета выбрать интересующий вид отчета. Нажать ОК.

Вывод: минимум затрат на доставку продукции, равный  90 ден. ед., будет обеспечен при следующем плане поставок:

·                    Со склада Черкизово в магазин «Колбасы» в объеме 5 единиц и магазин «Мясо» в объеме 40 единиц;

·                    Со склада Царицыно в магазин «Колбасы» в объеме 10 единиц и магазин «Дина» в объеме 25 единиц;

·                    Со склада Бородино в магазин «Колбасы» в объеме 15 единиц;

·                    Со склада Вешняки в магазин «Мясные деликатесы» в объеме 20 единиц.