Линейное программирование
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Линейное программирование
Вариант №6
Задание №1. Решение симплексным методом:
(1.1)
(1.2)
(1.3)
Задача (1.1)-(1.3) является общей задачей линейного программирования (ЛП), так как система (1.1) состоит из неравенств, вводя дополнительные неизвестные х3>0, х4>0 и прибавляя их к левым частям первого и второго неравенства и отнимая неизвестную х5>0 от левой части третьего неравенства, домножим третье неравенство на -1, получим основную задачу ЛП вида:
(1.4)
(1.5)
(1.6)
Не выполняя дополнительных преобразований, определяем, что основная форма (1.4)-(1.6) одновременно является и канонической формой задачи ЛП.
Задача (1.4)-(1.6) каноническая, применим для их решения стандартный симплекс метод. Запишем систему ограничений и начальное значение целевой функции в исходную симплекс таблицу.
Таблица №1
Базисыx0x1x2x3x4x5Ключевое отношениех345-2100-2х44-120102х5-4-1-10014f0-1-2000
Так как задача максимизации, то в индексной строке отыщем наименьший элемент - это -2, этот элемент лежит в основании ключевого столбца, который указывает на элемент, вводимый в базис. Подсчитав ключевые отношения, находим наименьшие, которое указывает на неизвестное, вводимое в базис, но положительное - это 2. Следовательно, строим новую таблицу и вписываем новые базисные неизвестные, вместо x4 войдет x2.
Таблица №2
Базисыx0x1x2x3x4x5Ключевое отношениех38401102х22-1/2101/204х5-2-1 1/2001/211 1/3f4-20010
В новой таблице (Таблица №2) рассчитываем и записываем ключевую строку, она получается делением всех элементов соответствующей строки исходной таблицы на ключевой элемент, то есть на 2. Остальные строки подсчитываются по правилу двух перпендикуляров. То есть каждый элемент новой таблице равен разности между соответствующими элементами исходной таблицы и произведением элементов, оказывающимися в основании перпендикуляров опущенных из старого элемента на ключевой столбец и ключевую строку.
Так продолжаем до тех пор, пока, все элементы индексной строки не отрицательны (положительные и нули).
Таблица №3
Базисыx0x1x2x3x4x5Ключевое отношениех32 2/30012 1/32 2/31х22 2/30101/3-1/3-8х11 1/3100-1/3-2/3-2f6 2/30001/3-1 1/3
В новой таблице (Таблица №3) рассчитываем и записываем ключевую строку, Остальные строки подсчитываются по правилу двух перпендикуляров. Мы видим, что х5 войдет в базисы, заменив собой х3. Получаем новую таблицу (Таблица №4):
Таблица №4
Базисыx0x1x2x3x4x5х51003/87/81х23011/85/80х12101/41/40f8001/21 1/20
В Таблице №4 все элементы индексной строки не отрицательные (положительные и нули), значит задача решена. Так оно и есть, значит, план является оптимальным, а значение, стоящее в индексной строке столбца х0 есть максимальное значение целевой функции. Вычисления прекращаем и получаем: , .
Так же было проведена проверка с помощью MS Excel, встроенной функции Поиск решения. На Рисунке 1 - Заполнение требуемых параметров, мы видим заданную систему; изменяемые ячейки, которые являются базисами; целевую ячейку, которая отображает максимальное значение целевой функции; сохраняемые модели, которые необходимы для хранения временных данных.
линейное программирование функция
Рисунок 1 - Заполнение требуемых параметров
На Рисунке 1 изображено не все, так же имеются формулы, которые написаны для расчета целевой функции и сохраняемых моделей. Формула для расчета целевой ячейки: произведение сумм коэффициентов перед неизвестными в целевой функции на изменяемые ячейки соответственно. Для сохраняемых моделей: сумма произведений коэффициентов перед неизвестными соответствующего уравнения на изменяемые ячейки.
Рисунок 2 - Выполняемая программа
После выполнения программы, изображенной на Рисунке 2, появиться правильный ответ, то есть максимальное значение целевой функции, изображенной на Рисунке 1.
Задание №1. Построить графическое решение:
(1.1)
(1.2)
(1.3)
Система линейных ограничений (1.1) - (1.3), представлена в виде прямых, определим точки для построения прямых на плоскости:
) ;
) ;
) ;
Постоим получившиеся прямые на плоскости. Каждая прямая делит декартову плоскость на две полуплоскости:
Рисунок 3 - График
Так как изначально нам были даны неравенства то, следовательно, решение неравенства является множество точек, а решение системы является область, включающая точки, удовлетворяющие всем неравенствам.
Для определения интервала точек для каждого неравенства достаточно взять любую точку из первой полуплоскости и подставить в неравенство, отвечающее за данную прямую, и проверить условия. Если точка удовлетворяет условию тогда эта полуплоскость является решением неравенства.
Теперь построим вектор нормали из коэффициентов целевой функции (;,), находим точку направления вектора, соединяем начало координат с этой точкой, указываем направление вектора. Вектор нормали указывает направление передвижения функции по многоугольнику.
Теперь построим целевую функцию. Целевую функцию можно изобразить в виде сетки параллельных прямых, достаточно для построения приравнять целевую функцию к любому значению и построить прямую (; (4;0); (0;2)). Та точка, через которую пройдет целевая функция при перемещении вдоль вектора нормали окажется последней в многоугольнике будет ответом. Эта тоска с координатами (2;3). Получаем отве?/p>