Решение задачи линейного программирования графическим методом
Построение множества допустимых значений. Вектор градиента заданной функции. Линия равного уровня целевой функции. Условия выполнения цели оптимизации. Первое, второе и третье ограничение целевой функции Y(x1,x2). Данные двухсторонних ограничений.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 26.11.2014 |
| Размер файла | 42,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Задание №1. Решение задачи линейного программирования графическим методом
Постановка задачи следующая: дана функция цели, представляющая собой линейную функцию (1). Функциональные ограничения на переменные представлены также линейными функциями, имеющими форму неравенств (2). Даны также непосредственные, или прямые, ограничения, которые могут иметь вид двухсторонних ограничений (3).
(1)
(2)
; j = 1,…,n (3)
Для решения задачи оптимизации графическим методом следует проделать следующие операции:
1) построить множество допустимых решений, которое на графике в осях x1, x2 будет иметь вид выпуклого многоугольника;
2) найти и построить градиент целевой функции, при этом надо помнить, что градиент линейной функции постоянен и может быть построен в любой точке координатной плоскости, например, в начале координат;
3) провести линию равного уровня целевой функции, перпендикулярную градиенту, и рассчитать соответствующее значение функции;
4) передвигать линию уровня параллельно самой себе до касания с границей множества допустимых решений в такой угловой точке, в которой выполняется цель оптимизации.
(4)
(5)
(6)
(7)
Для построения множества допустимых значений функциональные ограничения (2) представим равенствами. Для первого ограничения получим:
(8)
Чтобы построить эту линию на графике, получим две точки, принадлежащие ей: пусть x2 = 0, тогда из уравнения (8) получим: x1 = 4. Это координаты точки А. Для получения координат второй точки, В, примем x1 = 0, тогда x2 = 4. Нанесем эти точки на график (рис.1) и соединим их.
Аналогично построим линию, соответствующую равенству (9), полученному из ограничения (6).
(9)
При x2 = 0, из уравнения (9) x1 = -2, это координаты точки С. При x1 = 0, из уравнения (9) x2 = 2, это координаты точки D. Проведем вторую линию на графике (рис.1).
Чтобы учесть характер неравенств (5) и (6) на графике, нанесем штриховку на той стороне границы, на которой не удовлетворяется неравенство. В случае неравенства (5) недопустимым является пространство, расположенное выше и правее этой границы. В случае неравенства (6) штриховку нанесем выше и левее соответствующей линии, так как с увеличением x2 неравенство (6) выполняется, а с увеличением x1 - не выполняется.
Условия (7), называемые условиями неотрицательности, изображаются на графике штриховкой, нанесенной вдоль осей, со стороны отрицательных областей.
Теперь построим вектор градиента функции: Grad(F) = (-1, 3)Т. Проведем вектор из начала координат в точку с указанными в скобках координатами.
Построим линию равного уровня, проходящую через начало координат перпендикулярно вектору градиента (изображена штриховой линией). Значение функции на этой линии равно F(X) = 0. Так как требуется найти максимум функции, переносим линию равного уровня параллельно себя в направлении градиента. Крайней точкой, принадлежащей многоугольнику допустимых значений, будет точка Е, которая является точкой максимума функции. Таким образом, решением задачи оптимизации являются координаты точки Е: x1 = 1, x2 = 3. Значение функции в этой точке равно:
Fmax(X) = 2.
Заметим, что при необходимости уточнить решение можно найти угловую точку Е, решая совместно уравнения (8) и (9).
множество функция ограничение оптимизация
Рис. 1
Исходные данные к заданию №1 представлены в таблице 1.
В таблице приняты следующие обозначения: cj - коэффициенты модели (целевой функции), где j - номер переменной; aij - коэффициенты функциональных линейных ограничений; bi - свободные члены ограничений; Inf xi - нижняя граница двухсторонних ограничений для соответствующей переменной xj; Sup xj - верхняя граница двухсторонних ограничений для соответствующей переменной xj. То есть в общем виде условия задания следует читать так:
Y(x1,x2)=co + c1*x1+c2*x2 ;
при ограничениях a11*x1+a12*x2 «знак» b1; a21*x1+a22*x2 «знак» b2; a31*x1+a32*x2 «знак» b3;
Inf x1 x1 Sup x1, Inf x2 x2 Sup x2.
Таблица 1
|
Вариант |
Целевая ф-ия Y(x1,x2) |
1-e ограничение |
2 -oe ограничение |
3 -e ограничение |
2-х сторонние ограничения |
Цель опт. |
|||||||||||||||
|
сo |
c1 |
с2 |
a11 |
a12 |
знак |
b1 |
а21 |
а22 |
знак |
b2 |
a31 |
a32 |
знак |
b3 |
Infx1 |
Supx1 |
Infx2 |
Supx2 |
|||
|
1 |
10 |
5 |
10 |
6 |
5 |
2 |
-12 |
-4 |
7 |
-3 |
-6 |
5 |
0 |
5 |
-2 |
1 |
min |
||||
|
2 |
50 |
-6 |
10 |
6 |
5 |
2 |
5 |
-4 |
7 |
-3 |
0 |
5 |
0 |
5 |
-2 |
1 |
min |
||||
|
3 |
50 |
-6 |
10 |
6 |
-5 |
2 |
0 |
7 |
7 |
-3 |
5 |
3 |
0 |
5 |
-2 |
1 |
max |
||||
|
4 |
10 |
-5 |
12 |
6 |
-5 |
2 |
2 |
3 |
7 |
-3 |
-2 |
3 |
0 |
5 |
-2 |
1 |
max |
||||
|
5 |
50 |
-6 |
10 |
4 |
-5 |
2 |
2 |
-3 |
7 |
-3 |
5 |
3 |
0 |
1 |
-2 |
1 |
max |
||||
|
6 |
50 |
-6 |
10 |
-10 |
-5 |
2 |
0 |
3 |
7 |
-1 |
5 |
3 |
0 |
5 |
-2 |
1 |
max |
||||
|
7 |
20 |
-3 |
10 |
-1 |
-2 |
2 |
0 |
3 |
7 |
-1 |
3 |
3 |
0 |
5 |
-2 |
1 |
max |
||||
|
8 |
20 |
-3 |
10 |
5 |
-2 |
2 |
3 |
3 |
7 |
-1 |
3 |
3 |
-1 |
5 |
-1 |
1 |
max |
||||
|
9 |
20 |
-3 |
5 |
1 |
1 |
2 |
-3 |
-3 |
7 |
-1 |
3 |
1 |
-3 |
5 |
0 |
1 |
min |
||||
|
10 |
10 |
-3 |
5 |
1 |
1 |
2 |
-3 |
-3 |
5 |
-1 |
1 |
1 |
-3 |
2 |
0 |
1 |
min |
||||
|
11 |
15 |
2 |
5 |
1 |
1 |
2 |
-3 |
-3 |
5 |
-1 |
1 |
1 |
-3 |
2 |
0 |
1 |
min |
||||
|
12 |
12 |
2 |
5 |
-1 |
1 |
5 |
-3 |
8 |
5 |
-1 |
3 |
4 |
-1 |
1 |
0 |
1 |
min |
||||
|
13 |
8 |
2 |
5 |
5 |
1 |
5 |
-3 |
8 |
5 |
3 |
3 |
4 |
-3 |
1 |
0 |
1 |
min |
||||
|
14 |
18 |
2 |
5 |
1 |
1 |
1 |
-7 |
-2 |
3 |
5 |
3 |
2 |
-3 |
1 |
0 |
1 |
max |
||||
|
15 |
10 |
2 |
5 |
3 |
1 |
1 |
-7 |
-2 |
3 |
1 |
2 |
2 |
-1 |
1 |
-2 |
1 |
max |
||||
|
16 |
12 |
1 |
5 |
1 |
3 |
1 |
-7 |
-2 |
3 |
1 |
2 |
2 |
-1 |
1 |
0 |
1 |
max |
||||
|
17 |
12 |
1 |
5 |
3 |
3 |
3 |
-7 |
8 |
2 |
5 |
-2 |
2 |
-1 |
1 |
0 |
1 |
max |
||||
|
18 |
10 |
2 |
5 |
3 |
3 |
3 |
-7 |
8 |
2 |
2 |
-2 |
2 |
-1 |
1 |
0 |
5 |
max |
||||
|
19 |
16 |
2 |
3 |
-2 |
3 |
3 |
-7 |
5 |
2 |
1 |
-2 |
1 |
-1 |
3 |
0 |
2 |
max |
||||
|
20 |
8 |
2 |
3 |
-2 |
1 |
-3 |
3 |
-5 |
-2 |
-1 |
2 |
1 |
-1 |
3 |
0 |
2 |
max |
||||
|
21 |
5 |
2 |
3 |
-2 |
1 |
2 |
1 |
2 |
1 |
5 |
-2 |
1 |
-1 |
5 |
0 |
2 |
min |
||||
|
22 |
5 |
2 |
3 |
-2 |
4 |
-5 |
3 |
-2 |
4 |
-5 |
2 |
1 |
-2 |
5 |
0 |
2 |
min |
||||
|
23 |
10 |
2 |
3 |
-1 |
4 |
2 |
2 |
0 |
1 |
-8 |
2 |
1 |
-1 |
5 |
-1 |
2 |
min |
||||
|
24 |
50 |
-6 |
10 |
6 |
-5 |
2 |
0.5 |
7 |
7 |
-3 |
5 |
3 |
0 |
3 |
-2 |
1.5 |
max |
||||
|
26 |
30 |
-3 |
5 |
1 |
1 |
2 |
-3 |
-3 |
1 |
-1 |
3 |
1 |
-1 |
3 |
0 |
1 |
min |
||||
|
27 |
90 |
2 |
5 |
1 |
1 |
0.5 |
-10 |
-20 |
3 |
5 |
3 |
2 |
-3 |
1 |
0 |
1 |
max |
Размещено на Allbest.ru
...Подобные документы
Математическая модель задачи. Построение области допустимых планов. Построение линии уровня целевой функции. Оптимизация целевой функции. Точка контакта линии уровня с областью допустимых планов. Максимальное значение и вектор-градиент целевой функции.
презентация [534,8 K], добавлен 11.05.2013Нахождение минимума целевой функции для системы ограничений, заданной многоугольником. Графическое решение задачи линейного программирования. Решение задачи линейного программирования с использованием таблицы и методом отыскания допустимого решения.
курсовая работа [511,9 K], добавлен 20.07.2012Методы линейного программирования в математическом моделировании технологических процессов. Направление оптимизации целевой функции. Ввод функциональных зависимостей для целевой функции и ограничений осуществляется с использованием Мастера функций.
курсовая работа [994,6 K], добавлен 04.01.2014Строение системы уравнений-ограничений и ее переменных, графический способ решения задач линейного программирования на плоскости. Выражение неизвестных через две независимые переменные, являющиеся координатными осями графика. Значение целевой функции.
лабораторная работа [61,4 K], добавлен 07.01.2011Решение общей задачи линейного программирования симплексным методом, графическое построение целевой функции. Его проверка с помощью встроенной функции "Поиск решения" MS Excel. Определение плана перевозок при наименьших суммарных транспортных затрат.
контрольная работа [362,3 K], добавлен 03.11.2011Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.
контрольная работа [191,1 K], добавлен 05.04.2016Минимизация квадратической функции на всей числовой оси методами Ньютона, наискорейшего спуска и сопряженных направлений. Нахождение градиента матрицы. Решение задачи линейного программирования в каноническом виде графическим способом и симплекс-методом.
контрольная работа [473,1 K], добавлен 23.09.2010Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.
курсовая работа [232,4 K], добавлен 01.06.2009Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.
реферат [157,5 K], добавлен 21.08.2008Постановка задачи нелинейного программирования. Определение стационарных точек и их типа. Построение линий уровней, трехмерного графика целевой функции и ограничения. Графическое и аналитическое решение задачи. Руководство пользователя и схема алгоритма.
курсовая работа [2,5 M], добавлен 17.12.2012Восстановление математической модели задачи нелинейного программирования. Решение уравнений прямых. Метод линеаризации: понятие, особенности применения при решении задач. Нахождение точки максимума заданной функции. Решение задачи графическим методом.
задача [472,9 K], добавлен 01.06.2013Решение общей задачи линейного программирования, заданной математической моделью в виде целевой функции. Планирование перевозки товара с минимальными затратами. Открытая транспортная задача. Расчет показателей деятельности фирмы и себестоимости товара.
контрольная работа [2,0 M], добавлен 17.05.2012Наложение ограничений, необходимых для выполнения условия. Составление целевой функции, матрицы переменных. Разработка модели управления запасами. Раскрой и минимизация отходов. Решение системы нелинейных уравнений. Оптимальное распределение сырья.
контрольная работа [1,1 M], добавлен 09.11.2013Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Построение пространства допустимых решений. Нахождение оптимального решения с помощью определения направления убывания целевой функции. Нахождение оптимальной точки. Поиск экстремумов методом множителей Лагранжа. Условия экстремума Куна-Таккера.
контрольная работа [396,2 K], добавлен 13.09.2010Методы решения задач параметрической оптимизации. Решение однокритериальных задач с параметром в целевой функции и в ограничениях. Решение многокритериальной задачи методом свертки критериев, методом главного критерия, методом последовательных уступок.
курсовая работа [1,5 M], добавлен 14.07.2012Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.
контрольная работа [2,0 M], добавлен 02.05.2012
