Применение Excel для решения транспортной задачи

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

Но есть одно общее: в диалоговом окне «Параметры поиска решений» не надо вводить Линейная модель. Таким образом, алгоритм решения транспортной задачи линейного программирования в Excel будет включать в себя следующие этапы:

1. Открыть Excel для ввода условий задачи.

2. Ввести условия, которые указаны в задаче:

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

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

- в ячейку, в которой будет записана целевая функции, вставить формулу СУММПРОИЗ из категории Математические Мастера функций и в качестве первого массива указать адрес блока ячеек, содержащего таблицу стоимостей, а вторым массивом указать адрес таблицы искомых переменных;

- заполнить ячейки ограничениями используя формулу СУММ из категории Математические Мастера функций;

- выполнить команду Сервис, в диалоговом окне Поиск решения задать все условия задачи:

1) ввести адрес ячейки целевую функцию;

2) указать минимизацию (если нужно максимизацию) задачи;

3) указать изменяемые ячейки ( адрес таблицы с переменными;

4) ввести условия ограничений.

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

Параметры поиска решения

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

- максимальное время по умолчанию = 100;

- предельное число итераций = 100.

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

Анализ оптимального решения

После успешного завершения поиска оптимальных решений на экране появится диалоговое окно Результаты поиска решения.

С помощью него можно вызвать отчеты трех типов:

- отчет по результатам (состоящий из трех таблиц: сведения о целевой функции, значение переменных, результаты оптимальных решений для ограничений и граничных условий);

- отчет по пределам (состоящий из двух таблиц: значение x в оптимальном решении, нижние пределы изменения значения x);

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

Рассмотрим алгоритм решения транспортной задачи помощью Excel на примере

Пример. На 3-х железнодорожных станциях А₁, A₂ и А₃ скопилось 120, 110 и 130 незагруженных вагонов. Эти вагоны необходимо перегнать на станции B₁ – B₅. На каждой из этих станций потребность в вагонах соответственно равна 80, 60, 70, 100 и 50. Учитывая, что со станции А₂ не представляется возможным перегнать вагоны на станции В₂ и В₄ и зная, что тарифы перегонки одного вагона определяются матрицей:

.

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

Решение. Методом двойного предпочтения получим следующий опорный план в виде таблицы 4.7,

Таблица 4.7 – Построение первоначального опорного плана транспортной задачи методом двойного предпочтения

Поставщики	Потребители	Запасы ai
В 1	В 2	В 3	В 4	В 5
A1	2 V	–	1 VV		–
A2		–	–	–	2 VV
A3		3 VV	–	3 VV	–
Потребности bj

 

где x ₁₁=20, x ₁₃=70, x ₁₄=30, x ₂₁=60, x ₂₅=50, x ₃₂=60, x ₃₄=70.

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

Z = 20·2+70·1+30·6+60·3+50·2+60·3+70·3 = 960 (ед.).

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

1. Создать таблицу согласно условию задачи (например, диапазон A₁: G₈, рисунок 4.1).

Рисунок 4.1 – Матрица стоимостей

2. Заполнить диапазон ячеек, которые необходимо изменять и в которые будут выводиться значения количества перевозок нулями (например, диапазон I₂: M₄, рисунок 4.2).

Рисунок 4.2 – Матрица стоимостей (A₁: G₈ )и матрица перевозок (I₂: M₄ )

3. Записать целевую функцию, например, в ячейку I₆, рисунок 4.3. Можно формулу набирать с помощью клавиатуры: установить курсор в ячейку; набрать значок «=«, щелкнуть мышкой в ячейке B3, набрать значок «·» щелкнуть мышкой в ячейке I₂, набрать значок «+»; и т.д. или вставить формулу СУММПРОИЗ из категории Математические Мастера функций и в качестве первого массива указать адрес блока ячеек (А₃: F₇), содержащего таблицу стоимостей, а вторым массивом указать адрес (I₂: M₄) ячеек таблицы, где находятся искомые переменные.

4. Ввести ограничения по наличию запасов и потребностей в ячейки I8: I15, аналогично вводу целевой функции (обратите внимание на формулу в ячейке I8, рисунок 4.4) или, используя формулу СУММ из категории Математические Мастера функций.

Рисунок 4.3 – Ввод формулы целевой функции

 

Рисунок 4.4 – Ввод условий ограничений

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

Аппаратура и материалы. Для выполнения лабораторной работы необходим персональный компьютер с характеристиками, позволяющими установить операционную систему Windows XР, интегрированный пакет Microsoft Officе.

Указания по технике безопасности. Самостоятельно не производить установку и удаление программного обеспечения; ремонт персонального компьютера. Соблюдать правила технической эксплуатации и техники безопасности при работе с электрооборудованием.

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. A. затраты АТП на выполнение перевозок в денежной форме, расчитанные на единицу транспортной продукции.
2. A. эксплуатируемые вручную или с применением ручного труда; без применения ручного труда (механические, автоматические и др.).
3. C.Для предоставления возможности сравнивать рыночные стоимости акций компаний одной отрасли
4. I. Предмет и задачи дидактики
5. I. Составить схему транспортной классификации грузов.
6. II этап. Обоснование системы показателей для комплексной оценки, их классификация.
7. II. Исходное состояние в области транспортной безопасности
8. II. Исходное состояние в области транспортной безопасности
9. II. Предполагаемые союзники и их задачи
10. II. ТЕМЫ ДЛЯ КОНТРОЛЬНЫХ РАБОТ
11. III. Источники для изучения Греческой церкви XVII в.
12. III. Целевые установки, задачи и направления обеспечения транспортной безопасности