Стариков А.В., Кущева И.С. Экономико-математическое и компьютерное моделирование: методические указания

Подождите немного. Документ загружается.

В транспортную таблицу вводится дополнительный столбец,

соответствующий пункту назначения B

, в нём проставляются нулевые

стоимости перевозок. После этого задача решается как сбалансированная (или

закрытая) ТЗ, и для неё находится оптимальный план перевозок

m™mnm

™n

xxx

...

............

...

2222

1112

При этом все перевозки, стоящие в правом столбце, фактически никуда не

отправляются, а остаются на соответствующих ПО.

Если запасов не хватает для удовлетворения всех заявок:

∑∑

то аналогично предыдущему случаю вводится фиктивный поставщик А

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

Стоимость перевозок от этого поставщика к любому потребителю с

принимается равной нулю. При таком подходе не учитывается, в каком порядке

удовлетворяются заявки (не учитывается важность заявки).

Задание 4. Решить открытую ТЗ в соответствии с вариантом задания,

полученного от преподавателя. Определить, сколько и на какой лесосеке

останется не вывезенной древесины, либо сколько древесины останется на

одном из перегрузочных пунктов.

Решение ТЗ с помощью процедуры «Поиск решения»

Записывается математическая модель указанной задачи

+2x

+6x

+11x

+4x

+7x

+12x

+8x

+9x

+1x

+3x

+10x

→min ,











===≥

=++

=+++

4). 3, 2, 1,j 3; 2, 1,(i x0x

; 25

; 65

; 10

; 30

; 50

; 45

; 35

ijij

342414

332313

322212

312111

34333231

24232221

14131211

целые

xxx

xxxx

;

Исходные данные и математическая модель вводятся в виде таблицы

(Рис. 3.1).

Рис. 3.1

В ячейках B2 : E4 введены стоимости перевозок, в ячейках F2 : F4, B5 : E5

– количество запасов и заявок соответственно. B8 : E10 – рабочие (изменяемые)

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

. В них

вводятся начальные значения равные 0. В ячейках F8 : F10 записываются

формулы для вычисления левых частей ограничений:

в F8 должна быть сумма ячеек B8 : E8,

в F9 должна быть сумма ячеек B9 : E9,

в F10 должна быть сумма ячеек B10 : E10,

в B11 должна быть сумма ячеек B8 : B10,

в C11 должна быть сумма ячеек C8 : C10,

в D11 должна быть сумма ячеек D8 : D10,

в E11 должна быть сумма ячеек E8 : E10.

Целевая функция помещается в ячейку G6:

СУММПРОИЗВ (B3 : E5; B8 : E10).

Далее вызывается процедура Поиск решения, и заполняются все ее поля

ввода. В окне Параметры устанавливается Линейная модель, что

соответствует решению задачи симплекс-методом. Выполнив процедуру Поиск

решения, получают результаты (Рис. 3.2):

Рис. 3.2

Задание 5. Решить ТЗ, полученную в качестве индивидуального задания,

с помощью процедуры «Поиск решения» табличного процессора Excel.

Контрольные вопросы

1. В чем состоит особенность ТЗ как частного случая ЗЛП?

2. Что называется перевозками и планом перевозок в ТЗ?

3. Чему соответствует число уравнений ТЗ и каково число независимых

уравнений?

4. Что такое базисные и свободные переменные ЗЛП?

5. Как определить для ТЗ общее число решений (перевозок), число

базисных и свободных решений?

6. Что называется допустимым планом ТЗ? Опорным планом?

Оптимальным планом? Транспортной таблицей?

7. В чем состоит метод СЗУ? Метод наименьшего элемента? Метод

Фогеля? Для чего используется метод потенциалов?

8. На основании каких перевозок и как определяются потенциалы

поставщиков и потребителей?

9. Как определяется цена цикла? Что она характеризует?

10. Как определяется наименьшее количество единиц груза,

переносимого по циклу?

11. Каково число уравнений в системе при определении потенциалов?

12. Что такое псевдостоимость? Теневая стоимость?

13. Как определить оптимальность полученного плана?

14. Чем характеризуется вырожденный опорный план?

15. Что понимается под «склеиванием» опорных точек плана?

16. Как ищется оптимальное решение при вырожденном опорном плане?

17. Что такое несбалансированная или открытая ТЗ?

18. Как привести открытую ТЗ к закрытой?

19. Что понимается под естественным базисом ЗЛП?

20. В каких случаях и как вводится искусственный базис в ЗЛП?

21. Зачем вводится искусственный базис и как интерпретируются его

переменные?

ЛАБОРАТОРНАЯ РАБОТА №4 (4 часa)

Тема работы: Формулировка задачи о назначениях и построение ее

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

оптимального решения с помощью процедуры «Поиск решения».

Содержание работы и порядок ее выполнения

Лабораторная работа включает в себя вариант задачи составления

оптимального по наибольшей компетентности плана распределения работников

по вакантным местам и рассчитана на 4 часа лабораторных занятий. Условие

задачи выдается студентам преподавателем, руководящим лабораторными

занятиями.

На занятии студент знакомится с содержанием работы, а во

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

исходным данным математическую модель задачи. Затем с помощью

процедуры Поиск решения табличного процессора Excel производится

нахождение оптимального решения задачи. Методика использования

процедуры «Поиск решения» описана в лабораторной работе №2.

На втором занятии студент отчитывается по теоретической части

лабораторной работы, предоставляет отчет о работе преподавателю и защищает

полученные результаты.

Формулировка задачи о назначениях и построение

ее математической модели

Задача о назначениях – это распределительная задача, в которой для

выполнения каждой работы требуется один и только один ресурс (один

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

одной и только одной работе. Другими словами − ресурсы не делимы между

работами, а работы не делимы между ресурсами. Таким образом, задача о

назначениях является частным случаем ТЗ. Задача о назначениях имеет место

при назначении людей на должности или работы, автомашин на маршруты,

водителей на машины, при распределении групп по аудиториям, научных тем

по научно-исследовательским лабораториям и т.п.

Исходные параметры модели задачи о назначениях

1. n – количество ресурсов, m – количество работ.

2. a

= 1 – единичное количество ресурса A

(i = n,1 ), например: один

работник; одно транспортное средство; одна научная тема и т.д.

3. b

= 1 – единичное количество работы B

(j = m,1 ), например: одна

должность; один маршрут; одна лаборатория.

4. c

– характеристика качества выполнения работы B

с помощью ресурса

. Например, компетентность i-го работника при работе на j-й должности;

время, за которое i-е транспортное средство перевезет груз по j-му маршруту;

степень квалификации i-й лаборатории при работе над j-й научной темой.

Искомые параметры

1. x

– факт назначения или не назначения ресурса A

на работу B







.работу ю- на назначен ресурс й-i если , 1

,работу ю- на назначен не ресурс -i если ,0

2. L(x) – общая (суммарная) характеристика качества распределения

ресурсов по работам.

Общий вид транспортной матрицы задачи о назначениях

Работы, B

Ресурсы, A

… B

Количество

ресурсов

… c

… … … … … …

… c

Количество работ

1 1 … 1

∑∑

Модель задачи о назначениях

( )

min

1 1

→=

∑∑

= =

ijij

xcXL ,

( )

















∑

. m1,j ;n1,i

,m1,j 1

,n1,i 1

(4.1)

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

так называемый венгерский метод ее решения. Поэтому, хотя в Excel такие

задачи решаются обычным симплекс-методом, в лабораторной работе

требуется построить модель задачи о назначениях вида (4.1). В некоторых

случаях, например, когда c

– это компетентность, опыт работы, или

квалификация работников, условие задачи может требовать максимизации ЦФ,

в отличие от (4.1). В этом случае ЦФ L(x) заменяют на L

(x)= – L(x) и решают

задачу с ЦФ L

(x)→min, что равносильно решению задачи с ЦФ L(x)→max.

Постановка задачи о назначениях

Отдел кадров предприятия устроил конкурсный набор специалистов на

две вакантные должности. На эти новые места (НМ) претендуют 3 прежних

сотрудника (ПС), уже работающие в других отделах, и 4 новых сотрудника

(НС). Номера новых сотрудников, новых и прежних мест выбираются по

вариантам преподавателем, руководящим лабораторными занятиями. Номера

прежних мест (ПМ) являются номерами прежних сотрудников (ПС).

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

сотрудников (табл.4.1) и прежних сотрудников (табл.4.2) для работы и на

новых местах, и на прежних местах (ПМ), то есть занимаемых прежними

сотрудниками. Необходимо учесть, что руководство предприятия, во-первых,

предпочитает, чтобы прежние сотрудники не претендовали на места друг друга,

и, во-вторых, не намерено увольнять прежних сотрудников. Необходимо

распределить сотрудников по должностям наилучшим образом.

Рекомендации к решению задачи о назначениях

1. Процесс приведения задачи о назначениях к сбалансированному виду

имеет свои особенности по сравнению с ТЗ. Если условие сбалансированности

задачи (4.1) не выполняется из-за нехватки работ или исполнителей в

количестве k

, то для создания баланса надо ввести такое же количество k

фиктивных строк или столбцов.

2. Особенностью решения данной задачи является моделирование

системы предпочтений, сложившейся у руководства предприятия по

описанному в условии задачи кадровому вопросу.

3. В задаче о назначениях увольнение прежнего сотрудника или

непринятие на работу нового сотрудника моделируется попаданием единицы в

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

разрешения таких ситуации необходимо использовать соответствующие

«тарифы».

4. Значения «тарифов»

c выбираются в зависимости от направления

оптимизации ЦФ задачи о назначениях (L(x)→max или L(x)→min). При этом

руководствуются принципом «невыгодности» запрещенных назначений. Так,

если L(x) – это общая компетентность работников, то в качестве запрещающих

надо выбирать нулевые компетентности

c . А если L(x) – это общее время

прохождения машинами транспортных маршрутов, то в качестве запрещающих

надо выбирать значения

c , превосходящие по величине максимальные

реальные значения c

5. При решении задач о назначении в Excel необходимо учитывать, что

переменные x

являются булевыми.

Таблица 4.1

Компетентность новых сотрудников

НМ1 НМ2 НМ3 НМ4 ПМ1 ПМ2 ПМ3 ПМ4 ПМ5 ПМ6

НС1 6 5 7 6 5 6 7 6 7 5

НС2 5 5 8 8 7 6 4 5 8 8

НС3 6 7 5 6 4 5 4 5 6 6

НС4 7 8 7 6 5 7 6 8 5 5

НС5 7 6 6 5 5 4 5 5 4 6

НС6 8 8 9 7 6 7 8 7 9 8

НС7 9 8 9 9 8 7 8 9 8 7

НС8 7 7 8 9 7 8 9 6 7 8

Таблица 4.2

Компетентность прежних сотрудников

НМ1 НМ2 НМ3 НМ4 Компетентность на занимаемом месте

ПС1 7 6 6 7 7

ПС2 8 9 7 7 8

ПС3 6 5 6 6 6

ПС4 7 9 6 8 8

ПС5 8 7 8 8 7

ПС6 4 5 6 4 5

Примерные вопросы на защите работы

1. Какова постановка задачи о назначениях?

2. В чем отличие модели задачи о назначениях от модели ТЗ?

3. Каковы исходные и искомые параметры задачи о назначениях?

4. Как записывается математическая модель задачи о назначениях.

5. Как записать модель задачи о назначениях, подразумевающую

максимизацию ЦФ, в виде (4.1)?

6. Каким образом в модели задачи о назначениях можно запретить

конкретное назначение?

7. В чем особенности процесса приведения задачи о назначениях к

сбалансированному виду?

8. Пояснить модель задачи о назначениях, построенную по заданному

варианту.

ЛАБОРАТОРНАЯ РАБОТА № 5 (6 часов)

Тема работы: Методы сетевого планирования. Основные понятия

сетевой модели. Расчет и анализ сетевых моделей. Определение временных

параметров работ и событий. Поиск критических путей и полных резервов

работ.

Содержание работы и порядок ее выполнения

Лабораторная работа включает в себя вариант задачи составления

сетевого графика и рассчитана на 4 часа лабораторных занятий. Условия задачи

выдаются студентам руководителем лабораторных занятий.

Студент должен построить сетевой график работ, рассчитать временные

параметры событий и работ, построить график привязки сетевой модели,

определить критические пути и их длительность. Определить численные

значения свободных и полных резервов каждой работы, результаты свести в

таблицу.

Результаты выполнения лабораторной работы оформляются студентом в

виде отчета.

Основные понятия сетевой модели

Построение сетевой модели (структурное планирование) начинается с

разделения проекта на четко определенные работы, для которых определяется

продолжительность. Работа – это некоторый процесс, приводящий к

достижению определенного результата, требующий затрат каких-либо ресурсов

и имеющий протяженность во времени. Работа может быть:

1. Действительной, т.е. требующей затрат времени и ресурсов;

2. Фиктивной, т.е. формально не требующей затрат времени и ресурсов;

3. Ожидание, т.е. требующей временных затрат, но не требующей

расхода ресурсов.

Событие – это момент времени, когда завершаются одни работы и

начинаются другие. Событие не имеет протяженности во времени. Взаимосвязь

работ и событий, необходимых для достижения конечной цели проекта,

изображается с помощью сетевого графика (сетевой модели). Работы

изображаются стрелками, которые соединяют вершины, изображающие

события. Начало и окончание любой работы описываются парой событий,

которые называются начальным и конечным событиями.

Для указания конкретной работы используют код работы (i, j), состоящий

из номеров начального (i-го) и конечного (j-го) событий. Событие считается

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

Поэтому работы, выходящие из некоторого события, не могут начаться, пока не

будут завершены все работы, входящие в это событие. Событие, не имеющее

предшествующих ему событий, называют исходным. Событие, которое не

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

завершающим.

При построении сетевого графика необходимо выполнять следующие

правила:

– для действительных работ используются сплошные стрелки, а для

фиктивных – пунктирные;

– каждая операция должна быть представлена только одной стрелкой;

– между одними и теми же событиями не должно быть параллельных

работ (работ с одинаковыми кодами);

– следует избегать пересечения стрелок;

– не должно быть стрелок, направленных справа налево;

– не должно быть висячих событий (не имеющих предшествующих

событий), кроме исходного;

– не должно быть тупиковых событий (не имеющих последующих

событий), кроме завершающего;

– не должно быть циклов.

Построение сетевого графика начинают с выявления исходных работ

модели. Это некоторая работа (несколько работ), которая может выполняться,

не ожидая окончания каких-либо других работ. Ее начальным событием

является исходное событие. Завершающей работой (работами) является та,

после которой не должны выполняться никакие другие работы. Если несколько

работ имеют общее начальное и общее конечное события, то они являются

параллельными, имеют одинаковый код, что недопустимо. Для устранения

параллельности работ вводят дополнительное событие и фиктивную работу

таким образом, чтобы конечные события работ различались.

Пример построения сетевой модели

Задача. Построить сетевую модель программы опроса общественного

мнения, которая включает разработку анкет (A; 1 день), распечатку анкет (B; 0,5

дня), прием на работу (C; 2 дня) и обучение персонала (D; 2 дня), выбор

опрашиваемых лиц (E; 2 дня), рассылку им анкет (F; 1 день), анализ

полученных данных (G; 5 дней).

Решение. Из условия задачи известно содержание работ, но явно не

указаны взаимосвязи между ними. Поэтому необходимо проанализировать

смысл каждой работы и выяснить, какие работы должны ей непосредственно

предшествовать. Исходной работой, начинающей сетевой график, в данном

случае является прием на работу (С), поскольку все остальные работы должны

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

работ по опросу общественного мнения сотрудников необходимо обучить

персонал (D). Перед тем как разослать анкеты (F), их надо разработать (A),

распечатать (B) и выбрать опрашиваемых лиц (E), причем работу с анкетами и

выбор лиц можно выполнять одновременно. Завершающей работой проекта

является анализ полученных данных (G), который нельзя выполнить без

предварительной рассылки анкет (F). В результате получается сетевая модель

(рис. 5.1.):

1 2 3

5 6

A B

C D

F G

Рис. 5.1.

Задание 1. На основе условия, выданного преподавателем построить

сетевую модель.

Расчет и анализ сетевых моделей

Календарное планирование предусматривает

определение моментов начала и окончания каждой работы и

других временных характеристик сетевого графика. Это

позволяет проанализировать сетевую модель, выявить

критические работы, непосредственно определяющие срок

выполнения проекта, провести оптимизацию использования

ресурсов (временных, финансовых, исполнителей). Расчет сетевой модели

начинают с временных параметров событий, которые вписывают

непосредственно в вершины сетевого графика:

(i) – ранний срок наступления события i, минимально необходимый для

выполнения всех работ, которые предшествуют событию i,

(i) – поздний срок наступления события i, превышение которого

вызовет аналогичную задержку наступления завершающего события сети,

R(i)= T

(i) – T

(i) – резерв события i, т.е. время, на которое может быть

отсрочено наступление события i без нарушения сроков завершения проекта.

Ранние сроки свершения событий T

(i)

рассчитываются от исходного (И) к

завершающему (З) событию следующим

образом:

1) для исходного события T

(И) =0 ,

2) для всех остальных событий

[

]

),()(max)(

),(

iktkTiT

∀

i T

(i)

(i)R(i)

(i)

)

t(k

,i)

t(k

,i)