Вопросы для самоконтроля

1. Сформулируйте алгоритм метода северо-западного угла.

2. Сформулируйте признак оптимальности опорного решения

3. Как осуществляется сдвиг по циклу.

Методы решения транспортных задач с неправильным балансом

1) Пусть суммарные запасы поставщиков превосходят суммарные запросы потребителей, т.е. .

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

Чтобы задача в рассматриваемом случае имела решение, необходимо ввести фиктивного потребителя с запросами , и нулевыми стоимостями перевозок единиц груза =0, .

2) Пусть суммарные запросы потребителей превосходят суммарные запасы поставщиков, т.е. .

Тогда необходимо ввести фиктивного поставщика с запасами , и нулевыми стоимостями перевозок единиц груза =0, .

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

Пример. Для транспортной задачи составить первоначальный опорный план методом северо-западного угла.

ПН ПО	1		2		3			4		Запасы
1		1		2			3		1	100
2		2		3		4			6	200
3		3		4		7			12	300
Потреб- ности	100		100		300			300

Вопросы для самоконтроля

1. При каком условии вводится фиктивный пункт отправления?

2. При каком условии вводится фиктивный пункт потребления?

3. Что делают, если суммарные запросы потребителей превосходят суммарные запасы поставщиков?

4. Что делают, суммарные запасы поставщиков превосходят суммарные запросы потребителей?

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

Лекция 7-8 Сетевые модели

1. Построение сетевых моделей

1.1. Теоретическое введение

Построение сетевой модели (структурное планирование) начинается с разбиения проекта на четко определенные работы, для которых определяется продолжительность. Работа – это некоторый процесс, приводящий к достижению определенного результата, требующий затрат каких-либо ресурсов и имеющий протяженность во времени. По количеству затрачиваемого времени работа может быть:

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

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

Фиктивная работа может реально существовать, например, "передача документов от одного отдела к другому". Если продолжительность такой работы несоизмеримо мала по сравнению с продолжительностью других работ проекта, то формально ее принимают равной 0. Существуют фиктивные работы, которым в реальности не соответствуют никакие действия. Такие фиктивные работы только представляют связь между другими работами сетевой модели.

Работы связаны друг с другом таким образом, что выполнение одних работ может быть начато только после завершения некоторых других. Событие – это момент времени, когда завершаются одни работы и начинаются другие. Событие представляет собой результат проведенных работ и, в отличие от работ, не имеет протяженности во времени.

Взаимосвязь работ и событий, необходимых для достижения конечной цели проекта, изображается с помощью сетевого графика (сетевой модели). Работы изображаются стрелками, которые соединяют вершины, изображающие события. Начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Поэтому для указания конкретной работы используют код работы , состоящий из номеров начального (i-го) и конечного (j-го) событий (рис.1.1).

Рис.1.1. Кодирование работы

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