лаб 3 нов

Методические указания

Пример. Производственное объединение имеет в своем составе три завода, которые производят однородную продукцию соответственно в количествах равных 310, 260 и 280 единиц. Эту продукцию необходимо перевезти на торговые склады пяти магазинов, расположенных в разных регионах. Потребности магазинов соответственно равны 180; 80; 200; 160 и 220 единиц. Стоимости перевозок единицы продукции от каждого завода во все магазины задаются матрицей .

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

Внесем все данные в распределительную таблицу.

Рис.1

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

• ставим курсор в ячейку А10,

• нажимаем значок на верхней панели,

• выделяем нужные ячейки,

• нажимаем Enter.

Рис.2

Аналогично в ячейку G6 помещаем сумму мощностей потребителей. Затем в ячейку А11 помещаем разность полученных значений. Т.е. в ячейке А11 печатаем =А10-G6 и нажимаем Enter. Если получили нуль, то задача закрытого типа, если получили положительное число, то мощность поставщиков больше мощности потребителей, поэтому вводим фиктивного потребителя с мощностью, равной полученному числу и тарифами равными нулю. Если получили отрицательное число, то потребности больше предложения и, следовательно, нужно ввести фиктивного поставщика с мощностью, равной модулю полученной разности и нулевыми тарифами.

В рассматриваемой задаче нужно ввести фиктивного потребителя с мощностью 10 единиц.

Рис.3

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

Перейдем к решению полученной задачи в Excel.

Для удобства выделим ячейки с тарифами цветом или рамкой. Зарезервируем место для матрицы перевозок . Для этого скопируем выделенные ячейки и обозначим пункты поставщиков и потребителей. (Рис.4)

Рис.4

Для того чтобы в дальнейшем можно было ввести ограничения (1) и (2), необходимо просуммировать объемы перевозок по строкам и столбцам.

Для этого необходимо выполнить следующие операции:

• поместить курсор в ячейку H16;

• выбрать знак на верхней панели;

• выделить необходимые для суммирования ячейки B16:G16;

• нажать Enter для подтверждения ввода формулы. Аналогичные действия выполнить для ячеек H17, H18, т.е. вычислить количество единиц груза, которое вывозится от каждого поставщика. Если количество строк велико, то можно использовать процедуру Автозаполнения. Для этого нажимаем левую кнопку мышки на маркере автозаполнения и, удерживая её нажатой, перемещаем курсор в ячейку H18. (Рис.5)

Рис.5

Аналогично суммируя по столбцам объемы перевозок потребителям, помещаем результаты в ячейки В19: G19. Т.к. количество столбцов достаточно велико, то, в зависимости от установленной версии Excel, можно суммировать одним из двух способов.

• Выделить ячейки В16:G18;

• выбрать знак на верхней панели, Enter, или использовать процедуру Автозаполнения.

Рис.6

Для вычисления значения целевой функции, соответствующей минимальным суммарным затратам на доставку груза, необходимо выбрать ячейку, например, В21для целевой функции и выделить ее рамкой или цветом;

• поместить курсор в эту ячейку;

• запустить Мастер функций (значок f_x или на верхней панели);

• выбрать Другие функции – Математические - СУММПРОИЗВ;

• нажать кнопку OK;

Рис.7

• выделяя нужные ячейки, в появившемся окне (Рис.8) указать адреса ячеек, элементы которых обрабатываются этой функцией. Нажимаем ОК.

Рис.8

• Выбираем Данные- Поиск решения;

• вводим адрес В21 в поле Установить целевую (ячейку);

• отмечаем Минимальному значению;

• вводим адреса изменяемых ячеек B16:G18, выделяя эти ячейки;

• нажимаем Добавить, выделяем ячейки B19:G19, в среднем поле устанавливаем знак «=», выделяем ячейки B6:G6;

• нажимаем Добавить, выделяем ячейки H16:H18, в среднем поле устанавливаем знак «=», выделяем ячейки A7:A9; нажимаем OK.

Появится окно Поиск решения со всеми введенными ограничениями.

Рис.9

• Нажимаем Параметры;

• отмечаем Линейная модель и Неотрицательные значения;

• ОК (после этого появится окно Поиск решения);

• Выполнить.

Появляется окно Результаты поиска решения. Выделяем Устойчивость - ОК.

Рис.10

Получаем решение.

Т.е. . При этом матрица перевозок имеет вид

.

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

Рассмотрим отчет по устойчивости.

Таблица Изменяемые ячейки.

В столбце Результирующие значения находятся значения переменных по оптимальному плану.

В столбце Нормированные стоимости находятся двойственные оценки (добавочные стоимости), равные , где и – потенциалы клетки . Нормированная стоимость показывает:

а) на какую величину нужно снизить тариф на соответствующую перевозку, чтобы она стала выгодной,

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

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

В столбце Целевой коэффициент находятся тарифы перевозок.

Столбцы Допустимое увеличение и Допустимое уменьшение задают интервал изменения соответствующего тарифа, при котором оптимальное значение будет достигаться в той же угловой точке. Т.е. при изменениях тарифа внутри этого интервала оптимальный план сохраняется, а значение целевой функции может измениться, т.к. меняется и сама функция. Выражение 1E+30 означает бесконечность.

Таблица Ограничения.

В столбце Имя таблицы Ограничения находятся пункты потребителей затем пункты поставщиков. В столбце Результирующие значения находятся значения мощностей потребителей и поставщиков.

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

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

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

• Выбрать Данные - Поиск решения – Выполнить.

В результате получаем новый оптимальный план перевозок.

Рис.11

Суммарная стоимость перевозок . Оптимальный план

.

Общий оптимальный план имеет вид: , где