На первой итерации получен оптимальный план злп (4.24).

= (1, 4, 2); = (38, 28, 6),

= (38, 6, 0, 28, 0, 0, 0); f( ) = 242.

Запишем задачу, двойственную к (2.24):

min(50Y1 + 10Y2 +24Y3); Y1 ≥ 4; 2Y1 – 3Y2 + 4Y3 ≥ 1; 3Y1 + Y2 + ≥ 2.	(4.25)
Y2 ≥ 3; –Y1 +2Y2 + Y3 ≥ 0; Y3 ≥ 0; Y1 + 4Y2 – 1/2 Y3 ≥ 0.	(4.26)
не ограничены в знаке.	(4.27)

Ограничения (4.27) являются избыточными, следовательно, их можно отбросить.

Находим решение ЗЛП (2.25) по формуле

= = (4, 3, 1) = (4, 3, 1/2)

или (4.22):

= (0 + 4, 0 + 3, + 0) = (4, 3, );

= 504 + 103 + 24  = 242.

4.3. Решение злп с помощью Ms Excel

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

Рис.4.2

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

Рис.4.3

Рассмотрим на примере использование данной надстройки. Решим с ее помощью задачу производственного планирования - выпуск продуктов А, В, С, Д из трёх типов ресурсов, математическая модель которой имеет вид:

max f ( )=7,5X₁+3X₂+6X₃+12X₄ (целевая функция – суммарная стоимость выпуска)

при

Ограничения по запасам ресурсов и неотрицательности переменных

2 X₁+X₂+0,5Х₃+4Х₄ ≤ 2400

X₁+5X₂+3Х₃ ≤ 1200

3X₁+6X₃+Х₄ ≤ 2000

X_1,2,3,4 ≥0

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

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

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

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

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

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

Теперь необходимо ввести формулы. В нашей математической модели, целевая функция представляет собой произведение вектора коэффициентов на вектор неизвестных. Действительно, выражение 7,5X₁+3X₂+6X₃+12X₄, можно рассматривать как произведение вектора (7,5, 3, 6, 12) на вектор (Х₁,Х₂,X₃,X₄).

В Excel существует функция СУММПРОИЗВ, которая позволяет найти скалярное произведение векторов. В ячейку H5 необходимо вызвать данную функцию, а в качестве перемножаемых векторов задать адреса ячеек, содержащих коэффициенты уравнений (в данном случае, это С5:F5) и ячеек, в которые в результате решения будут помещены значения Х₁, Х₂, X₃, X₄ (ячейки С4:F4) (рис. 4.6).

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

Каждая левая часть ограничения тоже представляет собой произведение двух векторов: соответствующей строки матрицы затрат и вектора неизвестных. То есть, выражение 2X₁+X₂+0,5Х₃+4Х₄ (для первого ограничения 2X₁+X₂+0,5Х₃+4Х₄≤2400) будем рассматривать как произведение вектора коэффициентов (2, 1, 0,5, 4) и вектора переменных (Х₁,Х₂,X₃,X₄).

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

Рис.4.7

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

Рис.4.8

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

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

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

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

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

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

Рис.4.9

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

Рис.4.10

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

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

Рис.4.11

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

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

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

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

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

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

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

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

В окне «Поиск решения» имеется кнопка «Параметры»:

Установим флажок «Показывать результаты итераций», после нажимаем «ОК»:

Затем нажать кнопку «Выполнить»:

Ms Excel выдаст следующее окно:

На рабочем листе будут показаны результаты первой итерации:

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

Затем снова нажимаем кнопку «Продолжить», на рабочем листе отображаются результаты третьей итерации:

При следующим нажатии кнопки «Продолжить», программа выдает окно «Результаты поиска решения», где необходимо сохранить найденное решение и выбрать тип отчета:

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

Отчеты выглядят следующим образом:

1. Отчет по результатам

2. Отчет по устойчивости

3. Отчет по пределам

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

max f ( )=7,5X1+3X2+6X3+12X4 (целевая функция)

при

2X1+X2+0,5Х3+4Х4 ≥ 2400 ограничения

X1+5X2+3Х3 ≤ 1200

3X1+6X3+Х4 ≤ 2000

X1,2,3,4 ≥0

В итоге имеем следующие результаты по отчетам: 1. Отчет по результатам

2. Отчет по устойчивости

б) Теперь предположим, что математическая модель имеет другие ограничения:

max f ( )=7,5X1+3X2+6X3+12X4 (целевая функция)

при

2X1+X2+0,5Х3+4Х4 ≤ 2400 ограничения

X1+5X2+3Х3 ≥ 1200

3X1+6X3+Х4 = 2000

X1, 2, 3, 4 ≥0

В итоге имеем следующие результаты по отчетам: 1. Отчет по результатам

2. Отчет по устойчивости