Теоретические вопросы

1. Какая задача называется общей задачей линейного программирования?

2. Какая задача называется стандартной?

3. Какая задача называется канонической?

4. Какое решение называется базисным?

5. Что на плоскости задает каждое неравенство системы ограничений?

6. Как построить полуплоскость в заданной системе координат?

7. Какими из перечисленных точек (0,0); (1,-1); (1,1) может задаваться контрольная точка для определения полуплоскости неравенства x₁+x₂≥0?

8. Что на плоскости может представлять собой область допустимых решений? Какие варианты области допустимых решений возможны?

9. Что на плоскости графически представляет собой целевая функция?

10. Как на плоскости построить вектор ?

11. Что показывает вектор при решении задачи линейного программирования геометрическим методом при целевой функцииf(x)=c₁x₁+c₂x₂max?

12. Как на плоскости построить линии уровня целевой функции?

13. Через какие две точки проходит линия уровня, если ее рассматривать как вектор нормали к вектору ?

14. В чем заключается геометрическая интерпретация нахождения оптимального плана?

15. Что графически представляет собой оптимальный план, если область допустимых решений – выпуклый многоугольник?

16. Какие варианты оптимальных планов возможны?

17. Что означает запись относительно допустимых и оптимальных решений?

18. Что означает запись относительно допустимых и оптимальных решений?

Лабораторная работа №1. Геометрическое решение задачи лп при помощи математического пакета MathCad

Задание. Реализуйте все нижеприведенные шаги в математическом пакете MathCad, необходимые для решения задачи ЛП графическим методом.

Поясним последовательность действий при решения задачи на примере.

Рассмотрим задачу в стандартной форме с двумя переменными.

Задача. Найти значения переменных x₁ и x₂, при которых

при ограничениях

Поскольку в задаче только две переменные, можно рассмотреть геометрическую интерпретацию данной задачи на плоскости и найти ее решение геометрическим методом.

Порядок выполнения работы:

I. Оформление исходных данных.

1. Откройте математический пакет MathCad и введите заголовок Геометрический метод решения задач линейного программирования, выбрав команду Insert–Text Region.

2. Наберите целевую функцию, систему ограничений и условие неотрицательности переменных в текстовом процессоре (Word), используя редактор формул, а затем скопируйте «текст» задания на рабочий лист в пакете MathCad.

II. Определение области допустимых решений

1. Введите заголовок Определение области допустимых решений, выбрав команду Insert – Text Region.

2. Введите заголовок Построение прямых, выбрав команду Insert–Text Region.

3. Возьмите первое ограничение из системы и запишите его в виде равенства.

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

Выразите x2.

Для этого:

- выделите x2;

- выберите команду Symbolics-Variable – Solve;

- получите выражение

.

4. Для построения этой прямой в MathCad присвойте данному выражению имя функции y1(x), которая будет задавать эту прямую, то есть .

5. Аналогичным образом поступите с остальными 3 ограничениями системы, опираясь на шаги 3-4.

6. Постройте графики функций y1(x), y2(x), y3(x), y4(x) на одном чертеже.

Для этого:

- на панели инструментов выберите иконку для построения графиков в декартовой системе координат;

- введите все функции y1(x), y2(x), y3(x), y4(x) через запятую в окне построения графика функций;

- щелкните дважды ЛКМ на окне построения графиков функций, и в появившемся окне выберите тип Crossed;

- задайте по осям Ox и Oy только положительные значения с клавиатуры, учитывая, что по условию определяют первую координатную четверть.

- увеличьте окно, отображающее графики функций (рис. 1).

Рис. 1. Прямые, ограничивающие искомые полуплоскости.

7. Определите полуплоскость для каждого ограничения системы, используя панель инструментов Programming.

Введите функцию, которая поможет определить какую полуплоскость, верхнюю или нижнюю, задает первое ограничение. Для этого запрограммируйте проверку принадлежности точки искомой полуплоскости. Если точка принадлежит полуплоскости, то в итоге должна получиться «истина»-«1», иначе – «0».

- введите u1(x):=

- выберите панель программирования и на ней Add line;

- поставьте курсор в появившийся маркер первой строки и наберите 1(верно);

- выберите на панели программирования if;

- наберите в появившемся маркере первое неравенство, как оно задано в системе ограничений;

- поставьте курсор в появившийся маркер второй строки и наберите 0;

- выберите на панели программирования if;

- наберите в появившемся маркере первое неравенство системы ограничений, но с противоположным знаком;

Таким образом, для первого ограничения функция имеет вид:

.

Точка с координатами первой прямой, то есть ее можно взять в качестве контрольной для определения полуплоскости.

- введите u1(0,0)=, т.е. подставьте в функцию u1(x1,x2) точку с координатами (0, 0)

- получите , т.е. точка (0,0) принадлежит полуплоскости, разделяемой прямойy1(x), в противном случае не принадлежит

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

Для последних двух ограничений системы точка с координатами не принадлежит искомым полуплоскостям.

9. Мысленно выделите область допустимых решений, задаваемых данной системой ограничений. В итоге получился выпуклый пятиугольник.