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

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

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)

.

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

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

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

.

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

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

.

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

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

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

. Метод потенциалов

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

5

- 17

+ 7

67

9+ 7

х9- 6

810

118

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

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

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

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

.

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

поставка опорный план потребитель

5

67

9+ 7

- 6

8- 10

+ 7

118

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

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

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

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

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

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

.

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

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

5

67

97

810

118

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

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

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

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

Ответ:

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

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

Решение

Вычтем из элементов каждой строки минимальное значение в этой строке

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

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

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

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

.

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

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

.

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

Ответ:

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, так как

Тогда

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

.

Ответ:

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

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

Решение

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

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)      поздние сроки наступления событий (знаменатели дробей);

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

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

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

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

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

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