Оптимальные экономико-математические модели

19. (Транспортная задача) Имеется пять поставщиков однородной продукции с объемами поставок и пять потребителей с объемами потребления .

Решить транспортную задачу Исходная матрица планирования

Решение Так как

и

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

Найдем начальный опорный план методом минимальной стоимости, а затем оптимизируем его методом потенциалов.

1. Построение начального опорного плана Из таблицы стоимостей выберем наименьшую стоимость

.

Заполним клетку (1,1)

.

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

Заполним клетку (5, 5)

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

В оставшейся таблице стоимостей наименьшей является стоимость

.

Заполним клетку (2, 3)

.

В клетку (2, 3) помещаем 280 ед. груза и исключаем из дальнейшего рассмотрения третий столбец (потребности потребителя полностью удовлетворены).

Заполним клетку (3, 4)

.

В клетку (3, 4) помещаем 200 ед. груза и исключаем из дальнейшего рассмотрения третью строку (запасы поставщика полностью израсходованы).

В оставшейся таблице стоимостей наименьшей является стоимость

Заполним клетку (1, 4)

.

В клетку (1, 4) помещаем 90 ед. груза и исключаем из дальнейшего рассмотрения четвертый столбец (потребности потребителя полностью удовлетворены).

Заполним клетку (2, 2)

.

В клетку (2, 2) помещаем 10 ед. груза и исключаем из дальнейшего рассмотрения вторую строку (запасы поставщика полностью израсходованы).

В оставшейся таблице стоимостей наименьшей является стоимость

Заполним клетку (5,2)

.

20 ед. груза помещаем в клетку (5, 2), тем самым полностью расходуя запасы поставщика .

В оставшейся таблице стоимостей наименьшей является стоимость

Заполним клетку (4, 2)

.

110 ед. груза помещаем в клетку (4, 2), тем самым полностью расходуя запасы поставщика .

Заполним клетку (1, 2)

.

70 ед. груза помещаем в клетку (1, 2), тем самым полностью израсходовав запасы поставщика и полностью удовлетворив потребности потребителя .

В результате получаем план

Определим стоимость плана

2. Метод потенциалов Построим систему потенциалов. Положим. Найдем остальные потенциалы по формулам: .

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

Условия оптимальности () нарушаются в клетках (1, 3), (1, 5), (3, 2), (3, 3), (3, 5). Поэтому найденный опорный план не является оптимальным. Следовательно, одна из этих клеток должна быть загружена некоторым объемом поставок. В первую очередь заполняется та клетка, для которой достигается максимум среди:. Значит, включим переменную в число базисных. Пометим ее знаком «х» и построим цикл, который начинается и заканчивается в этой клетке (3, 2), а вершины цикла располагаются в занятых клетках.

(3, 2) — (3, 4) — (1, 4) — (1, 2).

Клетка (3, 2) помечается знаком «+», затем клетки, находящиеся в вершинах цикла отмечаются чередующимися знаками «-» и «+». Величина поставок, перемещаемая в клетку (3, 2), равна минимуму из поставок со знаком «-», т. е.

.

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

В новом опорном плане вычислим потенциалы занятых клеток и оценки незанятых клеток. Положим (т.к. во втором столбце наибольшее число заполненных клеток).

Условия оптимальности () нарушаются в клетках (4, 4). Поэтому найденный опорный план не является оптимальным.

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

Пометим ее знаком «х» и построим цикл, который начинается и заканчивается в этой клетке (4, 4), а вершины цикла располагаются в занятых клетках.

Клетка (4, 4) помечается знаком «+», затем клетки, находящиеся в вершинах цикла отмечаются чередующимися знаками «-» и «+».

Величина поставок, перемещаемая в клетку (4, 4), равна минимуму из поставок со знаком «-», т. е.

.

Величина вычитается из объемов поставок клеток со знаком «-» и прибавляется к объемам поставок клеток со знаком «+».

В результате получаем новый опорный план, затраты на реализацию которого составляют:

В новом опорном плане вычислим потенциалы занятых клеток и оценки незанятых клеток. Положим (т.к. во втором столбце наибольшее число заполненных клеток).

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

Все поставщики полностью израсходовали свои запасы, а потребности полностью удовлетворили свои потребности.

Значение целевой функции Ответ:

29. (Задача о назначениях).

Решить задачу о назначениях со следующей матрицей затрат:

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

Теперь вычтем из элементов каждого столбца минимальное значение в этом столбце:

Получим новую матрицу затрат:

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

.

Получили распределение работ по станкам с минимальными затратами:

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

.

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

Ответ:

49. (Минимизация сети) Построить набор дуг, соединяющих все вершины сети и имеющих минимальную протяженность.

Решение Итерация 1.

Начнем построение с вершины 1. Обозначим:

С — множество связанных вершин

— множество несвязанных вершин.

Тогда

Итерация 2.

Ближе всех к связанному множеству вершин расположена вершина 5, так как Тогда

Итерация 3.

Ближе всех к связанному множеству вершин расположены вершины 2 и 6, так как

.

Включим во множество связанных вершин вершину 2.

Тогда

Итерация 4.

Ближе всех к связанному множеству вершин расположена вершина 6, так как Тогда

Итерация 5.

Ближе всех к связанному множеству вершин расположены вершины 3 и 4, так как Включим во множество связанных вершин вершину 3.

Тогда

Итерация 6.

Ближе всех к связанному множеству вершин расположена вершина 7, так как Тогда

Итерация 7.

Ближе всех к связанному множеству вершин расположена вершина 9, так как Тогда

Итерация 8.

Ближе всех к связанному множеству вершин расположена вершина 11, так как Тогда

Итерация 9.

Ближе всех к связанному множеству вершин расположена вершина 12, так как Тогда

Итерация 10.

Ближе всех к связанному множеству вершин расположена вершина 10, так как Тогда

Итерация 11.

Ближе всех к связанному множеству вершин расположена вершина 4, так как Тогда

Итерация 12.

Ближе всех к связанному множеству вершин расположена вершина 8, так как Тогда

В связанное множество вершин С попали все вершины, значит, минимальная сеть построена, ее суммарная длина равна:

.

Ответ:

69. (СПУ) Задана следующая последовательность работ с их временными характеристиками:

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

Решение Построим сетевой график так, чтобы все дуги — работы были направлены слева направо. Над дугами проставим длительности работ.

I этап — прямой ход Находим ранние сроки всех событий по формуле:

Считаем, что .

Событию 2 предшествует только работа (1, 2), а событию 3 — работа (1, 3). Поэтому:

(из 1)

(из 1)

Далее находим:

(из 2)

(из 2)

(из 4)

(из 5)

(из 7)

(из 7)

(из 9)

Критический путь состоит из работ:

(1, 2) — (2, 5) — (5, 7) — (7, 9) — (9, 10)

и его длительность — 62.

II этап — обратный ход Определим поздние сроки всех событий по формуле:

Считаем, что Тогда ;

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

Таким образом, получим:

1) ранние сроки наступления событий (числители дробей);

2) поздние сроки наступления событий (знаменатели дробей);

3) резервы времени событий (разность между знаменателями и числителями);

4) поздние сроки начала работ (знаменатели дробей конечных событий за вычетом длительностей работ);

5) ранние сроки окончания работ (суммы числителей начальных событий и длительностей работ);

6) общие резервы времени работ (разности между знаменателями конечных событий и числителями событий за вычетом длительностей работ);

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

Временные характеристики некритических работ