Решение задачи линейного программирования

Создание модели в MS Excel предполагает использование надстройки «Поиск решения». Сначала мы решаем модель при удалении всех условий, получив, таким образом, задачу линейного программирования (ЛП). Такова общепринятая практика для очень больших моделей, т.к. задачи линейного программирования намного легче решить, чем задачи целочисленного программирования (ЦП). В данном случае это проиллюстрирует некоторые общие отношения между решением задачи линейного программирования (ЛП-решением) и задачи целочисленного программирования (ЦП-решением). ЛП-решение показано на рисунке 4.5.

	A	B	C	D	E	F	G	H	I
	Варианты прибыли	А	В	С		Альтернативы	А	В	С
	Уч 1					Уч 1
	Уч 2					Уч 2
	Уч 3					Уч 3			0,52
	Уч 4					Уч 4
	Затраты	А	В	С		Доход
	Уч 1					40,89
	Уч 2
	Уч 3					Затраты		Бюджет
	Уч 4						<=

Рисунок 4.5 – Решение задачи ЛП в MS Excel

Диапазон ячеек G2:I5 представляет переменные решения.

Диапазон ячеек B2:D5 представляет переменные решения

Диапазон ячеек B9:D12 представляет переменные решения

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

F9 = СУММПРОИЗВ(B2:D5;G2:I5).

Затраты вычисляются в ячейке F12 формулой

F12 = СУММПРОИЗВ(B9:D12;G2:I5).

Надстройка «Поиска решения» имеет следующий вид (Рис.4.6 a,b):

a)

b)

Рис. 4.6. Решение задачи ЛП с помощью надстройки «Поиск решения»

После нажатия кнопки «Выполнить» «Поиск решения» находит максимальное значение функции, заданной формулой в ячейке F9, за счет изменения ячеек диапазона G2:I5 (Чтобы задать диапазон изменяемых ячеек, достаточно установить курсор в окно «Изменяемые ячейки», а затем, перейдя на основную таблицу, установить курсор «мыши» на ячейку G2 и, удерживая нажатой левую клавишу, «протянуть» курсор до ячейки I5).

Ограничениями являются неравенства F12 ≤ H12 (затраты не превышают бюджета) и G2:I5 ≤ 1 (значения ячеек в указанном диапазоне, отражающие факт использования данного участка для каждого проекта, не превышают 1) (Рис. 4.6a). (Чтобы задать эти ограничения, надо нажать кнопку «Добавить» и в открывшемся диалоговом окне указать ячейки или диапазоны, а также знак равенства или неравенства). Условие неотрицательности, относящееся к «изменяемым ячейкам», задано в окне «Параметры» (рис. 4.6b). Отметим, что условие целочисленности пока не включено в ограничения.

Решение задачи ЛП (рис.4.5.):

z = 40.89, A₁ = 1, B₃ = 1, B₄ = 1, C₁ = 1, C₃ = 0.52.

Равенство F12=H12 показывает, что такое решение использовало бы весь свой бюджет.

Модель ЛП является редукцией модели ЦП, потому что снято одно из ограничений модели ЦП, а именно требование целочисленности значений переменных. Ошибочно считать, что округление решения ЛП-задачи позволит получить целочисленное решение. В нашем случае С₃ округляется до 1, что дает невозможное решение, потому что оно нарушает бюджетное ограничение. Округление С₃ до 0 дает возможное решение, но оно не является оптимальным ЦП-решением. В общем случае округление нецелочисленных оптимальных решений задачи ЛП до целого не обеспечивает оптимальное решение задачи ЦП. В более сложных задачах часто бывает трудно найти возможные решения путем округления.

Обратим внимание на то, что в найденном решении все переменные кроме одной принимают целое значение, хотя целые значения и не заданы условиями. Это происходит потому, что, как отмечено выше, оптимальное решение задачи ЛП находится на границе ОДР и является одним из базисных решений, а базисные решения имеют столько же базисных переменных, сколько существует ограничений. Каждая небазисная переменная находится на верхней (1) или нижней (0) границе, в то время как базисным переменными могут придаваться дробные значения. С одним ограничением можно было бы ожидать не более одного дробного значения, как мы видим в нашем случае. Вполне возможно, что базисная переменная будет достигать одной из своих границ.

Дата добавления: 2015-07-15