Решение с помощью таблицы

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

Рассмотрим, как это можно сделать в среде электронных таблиц Microsoft Excel на примере следующей задачи.

ЗАДАЧА: В пунктах A и B находятся соответственно 150 и 190 т горючего. Пунктам 1, 2, 3 требуются соответственно 60, 70, 110 т горючего. Стоимость перевозки 1 т горючего из пункта A в пункты 1, 2, 3 равна 60, 10, 40 тыс. руб. за 1 т соответственно, а из пункта B в пункты 1, 2, 3 - 120, 20, 80 тыс. руб. за 1 т соответственно.

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

Составим для наглядности таблицу исходных данных.

Поставщики	Потребители	Запасы
A	60	10	40	150
B	120	20	80	190
Потребность	60	70	110

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

• в случае превышения объема запасов - фиктивного потребителя; стоимость перевозок единицы продукции этому фиктивному потребителю полагается равной стоимости складирования, а объемы перевозок этому потребителю равны объемам складирования излишек продукции у поставщиков;
• в случае дефицита - фиктивного поставщика; стоимость перевозок единицы продукции от фиктивного поставщика полагается равной стоимости штрафов за недопоставку продукции, а объемы перевозок от этого поставщика равны объемам недопоставок продукции потребителям.

Для решения данной задачи построим ее математическую модель. Неизвестными здесь являются объемы перевозок. Пусть x_ij - объем перевозок от i-того поставщика j-тому потребителю. Функцией цели являются суммарные транспортные расходы, т.е.

где c_ij - стоимость перевозки единицы продукции от i-того поставщика j-тому потребителю. Кроме того, неизвестные должны удовлетворять следующим ограничениям:

· неотрицательность объема перевозок;

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

Таким образом, мы имеем следующую модель:

где a_i - запасы горючего у i- того поставщика; b_j - спрос у j-того потребителя.

В табличном процессоре Microsoft Excel для решения подобных задач предусмотрена надстройка Поиск решения. Если в меню Сервис отсутствует команда Поиск решения, для ее установки нужно выбрать команду Сервис | Надстройки, в появившемся диалоговом окне выбрать Поиск решения и нажать кнопку Ok.

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

1. Введите в ячейки диапазона B4:D5 стоимости перевозок.

2. Отведите ячейки диапазона B8:D9 под значения неизвестных (объемов перевозок). Ячейки должны быть пустыми!

3. Введите в ячейки диапазона F8:F9 объемы запасов горючего у поставщиков.

4. Введите в ячейки диапазона B11:D11 потребность в горючем у потребителей.

5. В ячейку B14 введите функцию цели: =СУММПРОИЗВ(B4:D5;B8:D9). Сделать это можно при помощи мастера функций выбрав в разделе Математические функцию СУММПРОИЗВи указав необходимый диапазон.

6. В ячейки диапазонов E8:E9 введите формулы вычисляющие объемы запасов у поставщиков, в ячейки диапазона B10:D10 - формулы расчета объемов доставляемого топлива к потребителям.

А именно:

Ячейка	Формула	Ячейка	Формула
E8	=СУММ(B8:D8)	C10	=СУММ(C8:C9)
E9	=СУММ(B9:D9)	D10	=СУММ(D8:D9)
B10	=СУММ(B8:B9)

При этом на экране должно отображаться следующее:

7. Выберите в меню Сервис команду Поиск решения и заполните диалоговое окно Поиск решения, как показано на рисунке.

Описание элементов окна Поиск решения смотри здесь

8. Нажмите кнопку Выполнить. Средство Поиск решения найдет оптимальный план поставок горючего и соответствующие ему транспортные расходы

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

Поставщики	Потребители
A	60	0	90
B	0	70	20

Значение целевой функции составило 10200 денежных единиц.

При этом, экономическая интерпретация результатов будет следующая. Поставщик A перевозит потребителям 1 и 3 - 60 и 90 т горючего соответственно, поставщик В - потребителям 2 и 3 - 70 и 20 т горючего соответственно. При этом затраты на перевозку продукции будут минимальными и составят 10200 денежных единиц.

Поиск решения

Процедура поиска решения (solver) предназначена для решения задач по оптимизации, при этом значения исходных ячеек изменяются, оставляя другие данные в указанных пределах. При необходимости получить конкретное значение в определенной ячейке, изменяя всего один параметр, удобнее использовать процедуру подбора параметра (см. раздел "Подбор параметра").
Для использования процедуры поиска решения на рабочем листе необходимо сначала загрузить надстройку Поиск решения (Solver). При отсутствии файла Solver.xla на жестком диске его необходимо установить. Для этого установите диск, содержащий программу установки Excel 2002, откройте папку X:\PFILES\MSOFFICE\OFFICE\LIBRARY\ и перепишите папку SOLVER в папку Н:\Program Files\Microsoft Office\Office\Library\. Здесь X и H - имена, определяющие устройство CD-ROM и системный каталог соответственно. После этого необходимо перезагрузить приложение Excel. Более подробную информацию о надстройках можно получить в разделе "Надстройки" в главе "Специальные возможности".

Создание

Процедура поиска решения предназначена для решения задач по оптимизации, при этом значения исходных ячеек изменяются, оставляя другие данные в указанных пределах. При необходимости получить конкретное значение в определенной ячейке, изменяя всего один параметр, удобнее использовать процедуру подбора параметра (см. раздел "Подбор параметра".)
Для проведения поиска решения на рабочий лист необходимо внести изменяемые ячейки, целевую формулу, результат которой будет оптимизироваться, а также ограничения, которые указывают пределы для решения. В Office 2002 включен файл Solvsamp.xls (находящийся в папке Program Files\Microsoft Office\Office\Samples), представляющий рабочую книгу с примером выполнения процедуры поиска решения. В нем для каждого рабочего листа выбраны целевые и изменяемые ячейки, а также ограничения.

Шаг за шагом

1. Внесите на рабочий лист изменяемые ячейки, целевую формулу, результат которой будет оптимизироваться, а также ограничения, которые указывают пределы для решения. Ячейки должны быть связаны через формулы. В противном случае изменения в одной ячейке не повлияют на другие.
2. Выберите команду Сервис (Tools) Поиск решения (Solver). В окне диалога Поиск решения (Solver Parameters) в поле Установить целевую ячейку (Set Target Cell) введите адрес или имя целевой ячейки - ячейки, содержащей формулу.
3. Укажите, на какой результат следует ориентироваться при поиске решения: Максимальному значению (Max), Минимальному значению (Min) или Значению (Value of). В последнем случае укажите конкретное значение в текстовом поле.
4. В поле Изменяя ячейки (By changing cells) следует ввести адреса или имена для всех влияющих ячеек, разделяя несмежные ячейки запятыми.
5. Чтобы дать возможность надстройке автоматически составить список изменяемых ячеек, нажмите кнопку Пред-положить (Guess).
6. В поле Ограничения (Subject to the Constraints) введите необходимые условия и нажмите кнопку Выполнить (Solve).
7. После того как решение найдено, на экране появится окно диалога Результаты поиска решения (Solver Results), в котором будут представлены несколько типов отчетов (см. раздел "Поиск решения: Создание отчета"):
• Отчет по результатам (Answer) описывает исходные и конечные значения целевой и влияющих ячеек модели, а также наложенные ограничения;
• Отчет по устойчивости (Sensitivity) содержит сведения о чувствительности решения к малым изменениям в формуле модели или в формулах ограничений;
• Отчет по пределам (Limits) показывает, как изменяются решения, когда значения целевой и влияющих ячеек максимизируются или минимизируются, в то время как остальные переменные остаются постоянными.
8. Выделите один или, удерживая клавишу Shift, несколько необходимых типов отчетов и нажмите кнопку OK.

СОВЕТ Чтобы восстановить исходные значения на рабочем листе после завершения работы с надстройкой Поиск решения (Solver), в окне диалога Результаты поиска решения (Solver Results) установите переключатель в положение Восстановить исходные значения (Restore original values).