Задание 6. Решение транспортных задач на основе метода потенциалов

Решить транспортную задачу:

5	4	6	3	200
1	10	2	1	300
2	3	3	1	100
150	150	250	50

Решение. Условие баланса выполнено. Следовательно, имеем ТЗ закрытого типа.

Предварительный этап. Находим исходный опорный план X° методом «минимального элемента ».

Число занятых клеток равно 6 и совпадает с рангом матрицы ограничений ТЗ:

r = m + n - 1 = 3+4-1 = 6.

Итерация 1. Для проверки полученного опорного плана на оптимальность находим

систему потенциалов для занятых клеток ( хij>0). Для этого, например, полагаем, что U1= 0 ( записываем U1= 0 в левой вертикальной графе в табл. 2.2). Далее, исходя из занятых клеток (1 , 2) и (1 , 3) , находим V2= С12-U1 = 4 - 0 = 4, V3 = 6 - 0 = 6 (записываем в верхней строке в таблице ). На основе базисной клетки (2 , 3) получаем U2=2 - 6 =-4 , затем V1= 1-(-4) = 5; U3=3 - 4= -1; V4=2.

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

U3+ V1 = 4 > 2,

U3+ V3 = 5 > 3,

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

Так как Δ31= U3+ V1- Cij = 2 = Δ33, то в любую из клеток, например, в (3,1), ставим некоторое число θ1.

Для того чтобы не нарушился баланс в 3-ей строке, вычитаем θ1 из величины перевозки, стоящей в клетке ( 3, 2) , прибавляем к Х12, вычитаем от Х13, прибавляем к Х23 и вычитаем от Х21, т.е. составляем цикл:

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

Знаки + и - в клетках чередуются.

Заметим, что движение от одной клетки к другой происходит только по занятым , кроме первой , в которую θ1 проставляется. Максимальное значение θ1 равно наименьшему уменьшаемому : θ1= 50. Если θ1 взять больше, то получаем отрицательную величину в плане перевозок , а если меньше , то нарушается опорность плана.

Итерация 2 . Проверяем полученный план Х(1) на оптимальность. Находим систему потенциалов. Они записаны в таблице слева и сверху, вычисляем сумму потенциалов для свободных клеток (записаны в левом верхнем углу клетки). Так как U1+ V4 = 4 > 3, то план Х(1) не является оптимальным. Для построения нового опорного плана проставляем величину θ2 в клетку (1,4) и составляем цикл:

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

Определяем значение θ2 =50, при этом две клетки (1,3) и (3, 4) обращаются в нулевые. Следовательно, план Х(2) будет вырожденным. Для дальнейшего решения необходимо оставить нуль в одной из клеток и считать ее за базисную. Целесообразнее нуль оставить в клетке с меньшей стоимостью перевозок, т.е. в клетке (3,4).

Итерация 3. Число занятых клеток равно 6. Находим значения потенциалов и их сумму для свободных клеток. Критерий оптимальности выполняется:

Ui+ Vj≤ Cij для Хij= 0; i=1,m;j=1,n

поэтому полученный план является оптимальным:f (x)* = 1500

-	150	-	50	200
50	-	250	-	300
100	-	-	-	100
150	150	250	50

Решить транспортную задачу методом потенциалов:

3. 

4. 

5. 

6. 

7. 

Задание 7. Решение задач линейного программирования на основе использования вычислителя OpenOffice Calc.org

Для решения задач оптимизации в MS Excel используют надстройку Поиск решения, которая вызывается из пункта главного меню «Сервис» (рис. 7.1).

Рис. 7.1.

Если в версии Excel, установленной на Вашем компьютере, отсутствует данный подпункт меню «Сервис», необходимо вызвать пункт меню «Надстройки» и в предложенном списке дополнительных модулей выбрать «Поиск решения» (рис. 7.2).

Рис. 7.2.

Рассмотрим на примере использование данной надстройки. Математическая модель задачи имеет вид:

Составим шаблон в редакторе Excel, как показано на рис. 7.3.

Рис. 7.3. Шаблон оформления задачи.

Теперь занесём данную в задаче числовую информацию (рис.7.4).

Рис.7.4. Исходные данные задачи

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

Ячейки B4 – С4 называются в Excel изменяемыми (в нашей модели это неизвестные переменные), т.е., изменяя их Поиск решения будет находить оптимальное значение целевой функции. Значения, которые первоначально вводят в эти ячейки, обычно нули (незаполненные клетки трактуются по умолчанию как содержащие нулевые значения).

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

В Excel существует функция СУММПРОИЗВ, которая позволяет найти скалярное произведение векторов. В ячейку Е4 необходимо вызвать данную функцию, а в качестве перемножаемых векторов задать адреса ячеек, содержащих коэффициенты уравнений (в данном случае, это В5:С5) и ячеек, в которые в результате решения будут помещены значения (ячейки В4:С4) (рис. 7.5).

Рис. 7.5. Вызов функции СУММПРОИЗВ.

Каждая левая часть ограничения тоже представляет собой произведение двух векторов: соответствующей строки матрицы затрат и вектора неизвестных. То есть, выражение (для первого ограничения ) будем рассматривать как произведение вектора коэффициентов (1,2) и вектора пока переменных.

В ячейке, отведенной для формулы левой части первого ограничения (D9), вызовем функцию СУММПРОИЗВ. В качестве адресов перемножаемых векторов занесем адрес строки коэффициентов В9:С9 и адрес значений переменных В4:С4 (рис. 7.6).

Рис. 7.6

В четыре оставшиеся ячейки графы «Левая часть» вводим аналогичные формулы, используя соответствующую строку матрицы затрат. Фрагмент экрана с введёнными формулами показан на рис.7.7.

Рис. 7.7

Важно! К моменту вызова сервиса «Поиск решения» на рабочем листе с задачей должны быть занесены формулы для левых частей ограничений и формула для значения целевой функции.

В меню Сервис выбираем Поиск решения. В появившемся окне задаём следующую информацию:

1. в качестве целевой ячейки устанавливаем адрес ячейки для значения целевой функции Е4;

2. «флажок» устанавливаем на вариант «максимальному значению», т.к. в данном случае, целевая функция дохода подлежит максимизации;

3. в качестве изменяемых ячеек заносится адрес строки значений переменных В4:С4;

4. справа от окна, предназначенного для занесения ограничений, нажимаем кнопку «Добавить», появится форма для занесения ограничения (рис. 7.8)

Рис.7.8. Форма для занесения одного ограничения ЗЛП.

5. в левой части формы «Ссылка на ячейку» заносится адрес формулы для левой части первого ограничения D9, выбирается требуемый знак неравенства (в нашем случае, <=), в поле «Ограничение» заносится ссылка на правую часть ограничения F9 (рис. 7.9).

Рис.7.9. Занесение первого ограничения задачи.

Аналогично заносятся все ограничения задачи, после чего нажимается кнопка «ОК».

Таким образом, окно «Поиск решения» с занесенной информацией выглядит следующим образом (рис.7.10):

Рис. 7.10.

Далее необходимо нажать кнопку Параметры, установить «флажки» «Линейная модель» и «Неотрицательные значения», поскольку в данном случае задача является ЗЛП, а ограничение 6) требует неотрицательности значений (рис.7.11).

Рис. 7.11. Установка параметров

Затем следует нажать «ОК», «Выполнить», после чего появляется окно результата решения (рис.7.12).

Рис. 7.12. Окно результата решения

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

Рис.7.13. Результат применения «Поиска решения»

Если в результате решения задачи выдано окно с сообщением о невозможности нахождения решения (рис.7.14), это означает, что при оформлении задачи была допущена ошибка (не заполнены формулы для ограничений, неправильно установлен «флажок» максимизации/минимизации и т.д.).

Рис.7.14. Сообщение об ошибке

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

Например, можно установить условие на целочисленность некоторых переменных.

Задание 8. Решение транспортных задач на основе использования вычислителя MS Office Excel или OpenOffice Calc.org

Решить транспортную задачу:

5	4	6	3	200
1	10	2	1	300
2	3	3	1	100
150	150	250	50

Решение. Условие баланса выполнено. Следовательно, имеем ТЗ закрытого типа.

Для решения задач оптимизации в MS Excel используют надстройку Поиск решения, которая вызывается из пункта главного меню «Данные» (рис. 8.1).

Рис. 8.1.

Составим шаблон в редакторе Excel, как показано на рис. 8.2.

Рис.8.2

Введем исходные данные по рассматриваемой задаче, как показано на рисунке 8.3.

Рис.8.3

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

Ячейки А13 – D15 называются изменяемыми, т.е., изменяя их Поиск решения будет находить оптимальное значение целевой функции. Теперь необходимо ввести формулы. В нашей математической модели, целевая функция представляет собой произведение матрицы стоимостей перевозок на матрицу изменяемых ячеек, являющейся матрицей перевозок. Для этого используем функцию СУММПРОИЗВ, которая позволяет найти искомую общую стоимость перевозок. В ячейку J4 необходимо вызвать данную функцию, а в качестве перемножаемых матриц задать адреса ячеек, содержащих стоимости перевозки единиц запасов (в данном случае, это А4 – D6) и ячеек, в которые в результате решения будут помещены значения объемов перевозок (ячейки А13 – D15) (рис. 8.4).

Рис.8.4.

В ячейке, отведенной для формулы левой части первого ограничения (L9), вызовем функцию СУММА. В качестве адресов занесем адрес строки матрицы перевозок А13:D13 (рис.8.5).

Рис.8.5

Таким образом вводятся ограничения на перевозки первой базы запаса. Аналогично вводятся ограничения для второй (L10) и третьей (L11) баз запасов (суммы ячеек А14:D14, А15:D15 соответственно). В ячейки L12-L15 вводятся ограничения на перевозки потребителей с 1 по 4 как суммы ячеек столбцов матрицы перевозок от A13:А15 до D13:D15.

В меню Данные выбираем Поиск решения. В появившемся окне задаём следующую информацию:

1. в качестве целевой ячейки устанавливаем адрес ячейки для значения целевой функции J4.

2. «флажок» устанавливаем на вариант «минимальному значению», т.к. в данном случае, целевая функция транспортных издержек подлежит минимизации;

3. в качестве изменяемых ячеек заносится адрес ячеек А13 – D15;

4. справа от окна, предназначенного для занесения ограничений, нажимаем кнопку «Добавить», появится форма для занесения ограничения (рис. 8.6)

Рис.8.6.

5. в левой части формы «Ссылка на ячейки» заносится адрес формулы для левой части первого ограничения L9, выбирается требуемый знак неравенства (в нашем случае, =), в поле «Ограничение» заносится ссылка на правую часть ограничения N9 (рис. 8.7).

Рис.8.7.

Аналогично заносятся все ограничения задачи, после чего нажимается кнопка «ОК». Общий вид готовой экранной формы приведена на рисунке 8.8.

Рис.8.8.

После нажатия кнопки Найти решение выводится результат решения (рис.8.9)

Рис.8.9.

После сохранения результата в ячейках А13 – D15, окрашенных желтым цветом, приводится решение транспортной задачи (8.10).

Рис.8.10.

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

Рассмотренный пример решения транспортной задачи в MS Excel практически не отличается от аналогичного в OpenOffice Calc.org, только там вместо инструмента Поиск решения применяется Решатель.