«Методы оптимальных решений» (стр. 7 )

Предварительный этап. Находим исходный опорный план 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

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

1.  

2.  

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).