Решение. Задача линейного программирования в общем случае формулируется следующим образом: определить максимум (минимум) целевой функции F max (min) при заданной

Задача линейного программирования в общем случае формулируется следующим образом: определить максимум (минимум) целевой функции F max (min) при заданной системе ограничений (2) и граничных условий (3):

F_max(min) =A₁*X₁+ A₂*X₂+...+A_n*X_n (1)

{B₁₁*X₁+B₁₂*X₂+...+B_1n*X_n≤C₁

{B₂₁*X₁+B₂₂*X₂+...+B_2n*X_n≤C₂

.............................................................. (2)

{B_n1*X₁+B_n2*X₂+...+B_nn*X_n≤C_n

X_i≥0, i=1...n (3)

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

60Х₁+70Х₂+120Х₃+130Х₄ = F_max – целевая функция прибыли

{Х₁+Х₂+Х₃+Х₄ ≤16

{6Х₁+5Х₂+4Х₃+Х₄ ≤ 110 – ограничения модели

{4Х₁+6Х₂+10Х₃+13Х₄ ≤ 100

Х_j ≥0 – граничные условия модели

Решение задачи средствами Excel состоит из 3 этапов:

1 этап. Создание формы.

а) Составление формы в виде:

	А	B	C	D	E	F	G	H
	Переменная	X1	X2	X3	X4	формула	знак	св. член
	Значение
	Нули
	Коэф. ЦФ					СП(В2:Е2)(В4:Е4)	max
	Трудовые					СП(В2:Е2)(В5:Е5)
	Сырьевые					СП(В2:Е2)(В6:Е6)
	Финансы					СП(В2:Е2)(В7:Е7)

б) Запись в ячейки В4:Е4 коэффициентов целевой функции F (1), в В5:Е7 коэффициентов из системы ограничений (2) и в ячейки Н5:Н7 - свободных членов из системы (2).

в) Ввод формул с помощью процедуры |f| - Мастер функций.

Для целевой функции: щелкнуть левой клавишей мыши по ячейке F4, затем по значку Мастера функций |f| на панели инструментов, в появившемся окне "Мастер функций, Шаг 1" в левой части выбрать категорию "Математические", в правой части – функцию СУММПРОИЗВ, нажать клавишу Далее, в окне "Мастер функций, Шаг 2" в поле Массив 1 ввести с клавиатуры В2:Е2 (ячейки, в которых будут варьироваться Х₁...Х₄), в поле Массив 2 ввести В4:Е4 (коэффициенты целевой функции ЦФ).

Примечание. Можно вводить В2:Е2 не с клавиатуры, а поставить курсор в окно Массив 1, а затем протащить курсор при нажатой левой клавише мыши по ячейкам В2:Е2, имена ячеек сами запишутся в окно. Аналогично поступить с полем Массив 2.

Нажать клавишу Готово, в ячейку F4 запишется формула 60*Х₁+70*Х₂+120*Х₃+ 130*Х₄ в виде СУММПРОИЗВ(В2:Е2)(В4:Е4).

Для левых частей ограничений аналогично:

- в ячейку F5 вносим СУММПРОИЗВ(В2:Е2)(В5:Е5),

- в ячейку F6 вносим СУММПРОИЗВ(В2:Е2)(В6:Е6),

- в ячейку F7 вносим СУММПРОИЗВ(В2:Е2)(В7:Е7).

Примечание. Чтобы каждый раз для новой ячейки F5...F7 не вызывать Мастер функций |f|, можно скопировать в буфер команду из F4 СУММПРОИЗВ(B$2:E$2)(B4:E4) кнопкой на панели инструментов
Копировать в буфер или командой из пункта меню Правка, затем вставить в выделенную ячейку F5..F7 эту команду с помощью кнопки Вставить из буфера или соответствующей команды из пункта меню Правка, при этом ячейки B$2:E$2 не изменятся, а В4:Е4 поменяются на В5:Е5, В6:Е6 и В7:Е7, т.к. символ абсолютной адресации строк $ в них не введён.

2 этап. Заполнение окна Поиск решения.

Выбрать в пункте меню Сервис команду Поиск решения, поставить курсор в поле целевой функции, выделить ячейку F4 в форме (или ввести F4 с клавиатуры), поставить точку в кружок строки "Максимальному значению".

В поле "Изменяя ячейки" ввести В2:Е2 (с клавиатуры или протащив мышью).

Нажать клавишу "Добавить", в окне "добавление ограничения в поле "Ссылка на ячейку" ввести F5, выбрать через "стрелка вниз" знак "<=", в поле справа ввести Н5.

Аналогично через "Добавить" ввести F6<=H6, F7<=H7 для системы ограничений B2>=B3,C2>=C3,D2>=D3 и Е2>=E3 для граничных условий Х_i>=0.

После ввода последнего граничного условия вместо "Добавить" нажать клавишу ОК, появится окно "Поиск решения".

Для изменения или удаления ограничений и граничных условий используются клавиши Изменить..., Удалить.

3 этап. Параметры поиска.

В окне "Поиск решения" нажать клавишу "Параметры", выбрать по умолчанию Максимальное время - 100 с.(может быть до 2^15=32767 c.> 4 час.), число итераций- 100(для большинства задач это количество просчётов подходит с большим запасом), установить флажок "птичка" в строке "Линейная модель", нажать ОК, в появившемся окне Поиск Решения нажать Выполнить, появится окно (результаты поиска решения с таблицей результатов):

	А	B	C	D	E	F	G	H
	Переменная	X1	X2	X3	X4	формула	знак	св. член
	Значение
	Нули
	Коэф. ЦФ						max
	Трудовые						<=
	Сырьевые						<=
	Финансы						<=

т.е. оптимальный план Х(Х₁,Х₂,Х₃,Х₄)=(10,0,6,0) при минимальном использовании ресурсов в объеме:

-Трудовые - 16 (У₁)

-Сырьевые - 84 (У₂)

-Финансы - 100 (У₃)

даёт максимум прибыли F в 1320 руб.

Вывод: Максимальная прибыль F в 1320 руб. получается при выпуске

только товаров Х₁ и Х₃ в количестве 10 и 6 штук соответственно, товары Х₂ и Х₄ выпускать не нужно (это приведёт к снижению прибыли). Трудовые (У₁) и финансовые (У₃) ресурсы используются полностью, по сырьевым ресурсам (У₂) есть запас в 110-84=26 ед. Кроме того, это означает, что изменение трудовых (У₁) и финансовых (У₃) ресурсов приведёт к изменению прибыли F, а изменение сырьевых ресурсов (У₂) - нет.

Разности между плановыми ресурсами и использованными являются двойственными переменными У₁,У₂ и У₃ сопряжённой задачи линейного программирования. В данном случае У₁=У₃=0, а У₂=26 ед. Таким образом, ресурс У₂ можно уменьшить на 26 ед., тогда план по сырью тоже будет оптимальным.

Задания для самопроверки

1.Сформулировать основную задачу линейного программирования. Записать математическую модель ЗЛП.

2.Основные этапы решения ЗЛП с помощью процессора Excel.

3.Способы ввода формул математической модели ЗЛП в форму.

4.Ввод ограничений и граничных условий математической модели в форму.

5.Ввод параметров поиска решения в процессор Excel.

Дата добавления: 2015-06-30