Инструкция по использованию Microsoft Excel. Найти максимум и минимум функции при заданных ограничениях:

Найти максимум и минимум функции при заданных ограничениях:

Решить задачу линейного программирования тремя способами:

· симплекс-методом

· графическим методом

· средством «Поиск решения» в программе Microsoft Excel

1. Решим поставленную задачу графическим методом.

Изобразим область допустимых решений, соответствующую системе ограничений-неравенств.

Найдем градиент функции :

На плоскости переменных и изобразим вектор-градиент и перпендикулярную ему линию уровня . Перемещая линию уровня вдоль вектора-градиента, мы придем в бесконечность, т.е. . Таким образом, исследуемая функция не имеет точки максимума. Перемещая линию уровня в направлении антиградиента , получим «точку выхода» с координатами A(2;2). При этом исследуемая функция принимает свое минимальное значение равное

2. Решим поставленную задачу симплекс-методом.

Найдем минимум исследуемой функции.

Так как симплекс-метод разработан для задач линейного программирования в канонической форме, то требуется перейти от ограничений-неравенств к ограничениям-равенствам путем введения балансовых переменных.

(1)

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

(2)

Если положить все свободные переменные равные нулю, то, используя систему уравнений (2), получим базисное решение:

Это базисное решение является недопустимым, так как не выполняются условия:

Пусть . Тогда из системы уравнений (2) следует, что:

Используя систему уравнений (2) найдем базисное решение с учетом :

Так как свободными переменными стали и , то необходимо «переразрешить» систему уравнений (2), а именно выразить переменную , ставшей базисной, через переменные , и подставить полученное выражение в оставшиеся уравнения системы:

(3)

Этому набору свободных и базисных переменных соответствует базисное решение:

Значение целевой функции при данном базисном решении:

Найденное базисное решение является недопустимым, поскольку не выполняется условие

В выражении целевой функции , которая выражена через свободные переменные и , коэффициент при отрицателен. Значит, увеличивая , можно уменьшить значение целевой функции .

Пусть . Тогда из системы уравнений (3) следует, что:

Используя систему уравнений (3) найдем базисное решение с учетом :

Так как свободными переменными стали и , то необходимо «переразрешить» систему уравнений (3), а именно выразить переменную , ставшей базисной, через переменные , и подставить полученное выражение в оставшиеся уравнения системы:

(4)

Этому набору свободных и базисных переменных соответствует базисное решение:

Значение целевой функции при данном базисном решении:

Найденное базисное решение является допустимым, поскольку .

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

Найдем максимум исследуемой функции.

Для того, чтобы применить симплекс-метод необходимо перейти от задачи максимизации к эквивалентной задаче минимизации и от ограничений-неравенств к ограничениям-равенствам. Задача, удовлетворяющая указанным требованиям и эквивалентная исходной, будет выглядеть следующим образом:

(5)

Из системы уравнений (5) видно, что в качестве свободных переменных проще всего выбрать . Тогда базисные переменные выражаются через свободные так:

(6)

Если положить все свободные переменные равные нулю, то, используя систему уравнений (6), получим базисное решение:

Это базисное решение является недопустимым, так как не выполняются условия:

Пусть . Тогда из системы уравнений (6) следует, что:

(7)

Используя систему уравнений (6) найдем базисное решение с учетом :

Так как свободными переменными стали , и , то необходимо «переразрешить» систему уравнений (6), а именно выразить переменную , ставшей базисной, через переменные , , и подставить полученное выражение в оставшиеся уравнения системы:

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

(8)

Этому набору свободных и базисных переменных соответствует базисное решение:

Значение целевой функции при данном базисном решении:

Найденное базисное решение является допустимым, поскольку .

В выражении целевой функции , которая выражена через свободные переменные и , коэффициент при отрицателен. Значит, увеличивая , можно уменьшить значение целевой функции .

Пусть . Тогда из системы уравнений (8) следует, что:

(9)

Из системы неравенств (9) видно, что свободная переменная неограниченна сверху. Это значит, что ее значение можно увеличивать до бесконечности. При этом минимальное значение целевой функции равно . Возвращаясь к первоначальной задаче, делаем вывод, что исследуемая функция не имеет точки максимума.

3. Решим поставленную задачу с помощью средства «Поиск решения» в программе Microsoft Excel.

Структура листа в Microsoft Excel.

x1	x2	F
		=3*A2+3*B2
Ограничение 1	=A2-2*B2
Ограничение 2	=-2*A2+B2
Ограничение 3	=2*A2+B2
Ограничение 4	=A2+2*B2

Найдем минимум исследуемой функции :

x1	x2	F

Найдем максимум исследуемой функции :

x1	x2	F
107374184,4	107374184,4	644245106,4

Так как графический и симплекс-методы показали, что исследуемая целевая функция не имеет максимума, то можно сделать вывод, что полученный результат является неверным и был получен в результате достижения предельного значения представления чисел в Microsoft Excel.

Вывод.

В результате проделанной работы были приобретены навыки при решении задач линейного программирования с помощью графического метода, симплекс-метода и при помощи средства «Поиск решения» в Microsoft Excel.

ПРИМЕРНЫЕ ВОПРОСЫ НА ЗАЩИТЕ РАБОТЫ

1.Как решается задача графическим методом?

2. Как решается задача симплекс-методом?

3. Как решается задача с помощью средств «Поиск решения»?

4. Зачем перепроверяют решение задачи разными методами?