Транспортная задача. Базисное решение транспортной задачи

Транспортная задача с закрытой моделью

Представим эту задачу в табличной форме:

Здесь в каждой из первых трех строк указаны поставщик, тарифы на перевозку к каждому потребителю и величина запаса. В нижней строке указаны потребности, причем сумма по строке «Потребность» равна сумме по столбцу "Запасы".
Подсчитаем стоимость отдельной перевозки, например 15 единиц продукта от поставщика A₂ к потребителю В₃: она составляет 15·4=60, при этом у поставщика остается еще 25 единиц продукта, а потребителю необходимо привезти от других поставщиков еще 20 единиц.
Общая стоимость перевозок равна сумме стоимостей всех перевозок, т. е. сумме произведений соответствующих тарифов на перевозимые количества продукта. В явном виде ее можно записать так:
F_min=6·x₁₁+2·x₁₂+1·x₁₃+3·x₁₄+
+5·x₂₁ +4·x₂₂+2·x₂₃+5·x₂₄+
+1·х₃₁+3·х₃₂+7·х₃₃+8·х₃₄
Величины х_тп являются искомыми переменными, а вся сумма - целевой функцией, минимальное значение которой надо найти.
Для решения задачи в табличном процессоре необходимо придерживаться определенного алгоритма действий:
1. Создать таблицу с исходными числовыми данными и рабочую таблицу с изменяемыми ячейками, в которые будут записываться получаемые результаты.
2. Составить формулу для целевой функции.
3. Указать адреса исходных и изменяемых данных, ограничения на переменные величины.
4. Сохранить полученные результаты и отчеты для анализа решения.

Выполнение работы

1. Составим на рабочем листе Excel две таблицы - они изображены на рис. 2.35. В таблице «Тарифы» записываются исходные числовые данные.
2. Заполним формулами, необходимыми для создания ограничений на запасы, ячейки F15:F17 столбца «Использовано»:

• 
  В ячейку F15 ввести формулу суммы. Для этого надо выделить эту ячейку, щелкнуть на значке Σ на панели инструментов, провести указателем мыши при нажатой левой кнопке мыши по диапазону ячеек В15:Е15, нажать клавишу Enter.
  

Рис.2.35.

• 
  Выделить ячейку F15, установить указатель мыши на маркер автозаполнения, провести указателем мыши при нажатой левой кнопке мыши по диапазону ячеек F16:F17.
  

3. Заполним формулами, необходимыми для создания ограничений на потребности, ячейки В18:Е18 строки «Удовлетворено»:

• 
  В ячейку B18 ввести формулу суммы. Для этого надо выделить эту ячейку, щелкнуть на значке Σ на панели инструментов, провести указателем мыши при нажатой левой кнопке мыши по диапазону ячеек В15:B17, нажать клавишу Enter.
  
• 
  Выделить ячейку B18, установить указатель мыши на маркер автозаполнения, провести указателем мыши при нажатой левой кнопке мыши по диапазону ячеек C18:E18.
  

4. Для наглядности запишем общие суммы по столбцам и строкам:

• 
  в ячейку G18 - по столбцу «Запасы»: =СУММ(G15:G17);
  
• 
  в ячейку F19- по строке «Потребность»: =СУММ (B19:E19).
  

5. Запишем формулу для целевой функции: выделить ячейку F20 и в строке формул ввести формулу =СУММПРОИЗВ(В7:Е9;В15:Е17). Полученная формула дает сумму из 12 попарных произведений указанных ячеек двух таблиц, которая и является для нас целевой функцией.
В результате выполненных операций получим рабочий лист как на рис. 2.36.
6. Укажем необходимые ссылки на ячейки и ограничения для целевой функции, для этого выполним команду Сервис→ Поиск решения. Появится диалоговое окно Поиск решения (рис. 2.37), в котором требуется:

• 
  В поле Установить целевую ячейку необходимо указать ячейку F20, для этого надо щелкнуть на этой ячейке, если она видна из-под диалогового окна, в противном случае следует щелкнуть на указателе перехода, чтобы свернуть окно (для возврата в диалоговое окно надо снова щелкнуть на указателе перехода). Результатом должна быть абсолютная ссылка $F$20.
  

Рис. 2.36.

• 
  Установить значение минимальному значению переключателя Равной, щелкнув на соответствующем кружке.
  
• 
  В поле Изменяя ячейки указать диапазон ячеек $В$15:$Е$17 либо прямым выделением этого диапазона с помощью мыши, либо с использованием указателя перехода.
  
• 
  В поле Ограничения необходимо создать список всех ограничений нашей задачи, для этого надо щелкнуть на кнопке Добавить. Появится диалоговое окно Добавление ограничения.
  

Рис. 2.37

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

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

Поле Ссылка на ячейку	Тип ограничения	Поле ограничения	Примечание
$В$15:$Е$17	>=	0	Условие неотрицательности перевозимых количеств продуктов
$F$15:$F$17	=	$G$15:$G$17	Условия полного распределения запасов
$В$18:$Е$18	=	$В$19:$E$19	Условия полного удовлетворения потребностей

Заканчивается ввод ограничений по щелчку на кнопке OK, при этом возвращается диалоговое окно Поиск решения. Для корректировки ограничений имеются кнопки Удалить, Изменить, Добавить.

7. После ввода всех параметров щелчок на кнопке Выполнить запустит поиск оптимального решения. Появится диалоговое окно Результаты поиска решения с сообщением об успехе или неуспехе поиска.
В случае, если решение найдено, можно выбрать переключатель Сохранить найденное решение и щелкнуть на кнопке ОК. В изменяемые ячейки В15:Е17 будут записаны значения оптимального плана перевозок, в ячейку F20 - значение целевой функции, а в ячейки столбца «Использовано» и строки «Удовлетворено» запишутся значения, равные значениям соответствующих ячеек столбца «Запасы» и строки «Потребность».
Одним из оптимальных будет план, изображенный на рис. 2.38.
Отменить результаты поиска, не выходя из окна Результаты поиска решения, можно так: либо щелкнуть на кнопке Отмена, либо, установив переключатель Восстановить исходные значения и щелкнуть на кнопке ОК. В случае неудачного поиска решения необходимо закрыть диалоговое окно Результаты поиска решения и проверить ссылки на ячейки и ограничения задачи.


Рис. 2.38.