Контрольная работа на тему КОНТРОЛЬНАЯ РАБОТА 160217-07

Содержание


Решить следующие задачи линейного программирования графическим методом 2
Решить задачи линейного программирования графическим методом и провести анализ на чувствительность 8
Решить задачи линейного программирования с n переменными графическим методом 15
Решить задачи линейного программирования симплекс-методом 21
Решить задачи линейного программирования табличным симплексным методом 25
Решить задачи линейного программирования табличным симплекс-методом и провести анализ на чувствительность 32
Решить задачи, используя алгоритм двойственного симплекс-метода 39
Сформулировать двойственную задачу к исходной задаче и найти решение симметричной пары задач 49
Для исходной задачи составить двойственную. Решить обе задачи симплексным методом или двойственным симплексным методом и по решению каждой из них найти решение другой. Одну из задач решить графическим методом 59
Решить следующие задачи распределительным методом и методом потенциалов 68

Решить следующие задачи линейного программирования графическим методом



Решение:
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Построим уравнение x1?0. Эта прямая проходит через точку x1 = 0 параллельно оси OX2. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1 • 0 – 0 = 0, т.е. x1 – 0? 0 в полуплоскости на прямой.
Построим уравнение x1?1. Эта прямая проходит через точку x1 = 1 параллельно оси OX2. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1 • 0 – 1 ? 0, т.е. x1 – 1? 0 в полуплоскости левее прямой.
Построим уравнение x2?0. Эта прямая проходит через точку x2 = 0 параллельно оси OX1. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1 • 0 – 0 = 0, т.е. x2 – 0? 0 в полуплоскости на прямой.
Построим уравнение x2?2. Эта прямая проходит через точку x2 = 2 параллельно оси OX1. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1 • 0 – 2 ? 0, т.е. x2 – 2? 0 в полуплоскости ниже прямой.
Построим уравнение x1+x2?0 по двум точкам. Для нахождения первой точки приравниваем x1 = 1. Находим x2 = -1. Для нахождения второй точки приравниваем x2 = 1. Находим x1 = -1. Соединяем точку (1;-1) с (-1;1) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1 • 0 + 1 • 0 – 0 = 0, т.е. x1+x2 – 0? 0 в полуплоскости на прямой.
Построим уравнение x1+x2?3 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 3. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 3. Соединяем точку (0;3) с (3;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1 • 0 + 1 • 0 – 3 ? 0, т.е. x1+x2 – 3? 0 в полуплоскости нижепрямой.
Построим уравнение x1-x2?-1 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 1. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = -1. Соединяем точку (0;1) с (-1;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1 • 0 – 1 • 0 + 1 ? 0, т.е. x1-x2 + 1? 0 в полуплоскости нижепрямой.
Построим уравнение x1-x2?0 по двум точкам. Для нахождения первой точки приравниваем x1 = 1. Находим x2 = 1. Для нахождения второй точки приравниваем x2 = 1. Находим x1 = 1. Соединяем точку (1;1) с (1;1) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1 • 0 – 1 • 0 – 0 = 0, т.е. x1-x2 – 0? 0 в полуплоскости на прямой.


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


Рассмотрим целевую функцию задачи F = x1+x2 > max.
Построим прямую, отвечающую значению функции F = 0: F = x1+x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (1; 1). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.


Прямая F(x) = const пересекает область в точке V. Так как точка V получена в результате пересечения прямых (6) и (7), то ее координаты удовлетворяют уравнениям этих прямых:
x1+x2=3
x1-x2=-1
Решив систему уравнений, получим: x1 = 1, x2 = 2
Откуда найдем максимальное значение целевой функции:
F(X) = 1*1 + 1*2 = 3
Поскольку функция цели F(x) параллельна прямой (6), то на отрезке VU функция F(x) будет принимает одно и тоже максимальное значение.
Для определения координат точки U решим систему двух линейных уравнений:
x2=2
x1-x2=-1
Решив систему уравнений, получим: x1 = 1, x2 = 2
Откуда найдем максимальное значение целевой функции:
F(X) = 1*1 + 1*2 = 3


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




Решение:
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Построим уравнение x1+x2?1 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 1. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 1. Соединяем точку (0;1) с (1;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1 • 0 + 1 • 0 – 1 ? 0, т.е. x1+x2 – 1? 0 в полуплоскостивыше прямой.
Построим уравнение -x1+x2?1 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 1. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = -1. Соединяем точку (0;1) с (-1;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:-1 • 0 + 1 • 0 – 1 ? 0, т.е. -x1+x2 – 1? 0 в полуплоскостиниже прямой.


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


Рассмотрим целевую функцию задачи F = 2x1+2x2 > min.
Построим прямую, отвечающую значению функции F = 0: F = 2x1+2x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора – точка (0; 0), конец – точка (2; 2). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.


Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
x1+x2=1
-x1+x2=1
Решив систему уравнений, получим: x1 = 0, x2 = 1
Откуда найдем минимальное значение целевой функции:
F(X) = 2*0 + 2*1 = 2
Поскольку функция цели F(x) параллельна прямой (1), то на отрезке AD функция F(x) будет принимает одно и тоже минимальное значение.
Для определения координат точки D решим систему двух линейных уравнений:
x2=0
x1+x2=1
Решив систему уравнений, получим: x1 = 1, x2 = 0
Откуда найдем минимальное значение целевой функции:
F(X) = 2*1 + 2*0 = 2
Изменение коэффициентов целевой функции.
Изменение значений коэффициентов c1 и c2 приводит к изменению угла наклона прямой z. Существует интервалы изменения коэффициентов c1 и c2, когда текущее оптимальное решение сохраняется. Задача анализа чувствительности и состоит в получении такой информации. Необходимо определить интервал оптимальности для отношения c1/c2 (или c2 и c1). Если значение отношения c1/c2 не выходит за пределы этого интервала, то оптимальное решение в данной модели сохраняется неизменным.
Таким образом, в рамках анализа на чувствительность к изменениям коэффициентов целевой функции могут исследоваться вопросы:
1. Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходит изменения оптимального решения.
2. На сколько следует изменить тот или иной коэффициент целевой функции, чтобы изменить статус некоторого ресурса.
На предыдущем рисунке видно, что функция достигает своего оптимума в точке, которая является пересечением прямых (x1+x2=1) и (-x1+x2=1). При изменении коэффициентов целевой функции эта точка останется точкой оптимального решения до тех пор, пока угол наклона линии z будет лежать между углами наклона этих прямых. Алгебраически это можно записать следующим образом:


при условии c1 ? 0
или


при условии c2 ? 0
Таким образом, мы получили две системы неравенств, определяющих интервал оптимальности.
При c2 = 2


или
-2 ? c1 ? 2
При c1 = 2