РГР по линейному программированию
Ответы на вопросы по заказу заданий по линейному программированию:
Сколько стоит помощь?
- Цена зависит от объёма, сложности и срочности. Присылайте любые задания по любым предметам - я изучу и оценю.
Какой срок выполнения?
- Мне и моей команде под силу выполнить как срочный заказ, так и сложный заказ. Стандартный срок выполнения – от 1 до 3 дней. Мы всегда стараемся выполнять любые работы и задания раньше срока.
Если требуется доработка, это бесплатно?
- Доработка бесплатна. Срок выполнения от 1 до 2 дней.
Могу ли я не платить, если меня не устроит стоимость?
- Оценка стоимости бесплатна.
Каким способом можно оплатить?
- Можно оплатить любым способом: картой Visa / MasterCard, с баланса мобильного, google pay, apple pay, qiwi и т.д.
Какие у вас гарантии?
- Если работу не зачли, и мы не смогли её исправить – верну полную стоимость заказа.
В какое время я вам могу написать и прислать задание на выполнение?
- Присылайте в любое время! Я стараюсь быть всегда онлайн.
Содержание:
- Ответы на вопросы по заказу заданий по линейному программированию:
- Линейное программирование
- РГР 1.
- РГР 2.
- РГР 3.
Линейное программирование
Линейное программирование - это раздел математики, изучающий методы нахождения максимальных или минимальных значений линейной однородной формы - линейной функции
в некоторой области мерного пространства где - постоянные числа, не все равные нулю.
Ясно, что если то линейная функция (1) не имеет наибольшего и наименьшего значений:
Однако если мы будем рассматривать ограниченную замкнутую область то линейная функция (непрерывная на а следовательно, и на достигает своих максимальных и минимальных значений на Так как
и одновременно не равны нулю, то линейная функция не имеет стационарных точек. Поэтому наибольшее и наименьшее значения эта функция достигает только на границе
Так как то в дальнейшем мы будем говорить только о минимуме линейной функции
Транспортная задача. Характерной задачей, приводящей к указанной выше проблеме (нахождения минимума или максимума линейной функции), является транспортная задача. Требуется наиболее экономно, в смысле транспортных затрат, перевезти потребителям заказанную ими на данных предприятиях продукцию. Характер продукции в данном случае не имеет значения. Важно, что речь идет об однотипной продукции.
Возможно, вас также заинтересует эта ссылка:
Итак, пусть имеются предприятия (производители) выпустившие продукцию в количестве соответственно тонн. Эту продукцию надо доставить потребителям в количествах тонн соответственно, т. е. - количество продукции, заказанное потребителем
Возможно, вас также заинтересует эта ссылка:
Решение задач по линейному программированию с примерами онлайн |
Таким образом, надо считать, что
т. е. вся произведенная продукция распределена между предприятиями. Стоимость перевозки тонны продукции от обозначим через . Пусть количество продукции, доставленной из будет Тогда стоимость перевозки продукции будет
Требуется так составить план перевозок, чтобы сумма транспортных расходов была минимальной.
Таким образом, мы пришли к следующей математической задаче.
Дана линейная функция
Требуется найти ее минимум при ограничениях т. е. сумма продукции, полученной потребителями от производителя равна продукции выработанной этим предприятием, а сумма продукции, полученной потребителем от всех производителей равна потребности этого потребителя.
По характеру задачи также ясно, что
Таким образом, среди неотрицательных решений системы (3) необходимо выбрать такое, при котором достигает наименьшего значения (минимизируется).
Возможно, вас также заинтересует эта ссылка:
Контрольная работа по линейному программированию заказать |
РГР 1.
Общая задача линейного программирования. В общем случае задачу линейного программирования можно сформулировать следующим образом: даны система линейных уравнений
(где можно считать, что изменяя, если нужно, знак в соответствующем уравнении (4)) и линейная функция
Требуется среди неотрицательных решений системы (4) найти такое решение, для которого линейная функция принимает наименьшее значение.
- Решение:
Уравнения (4) обычно называют ограничениями данной задачи. Конечно, требование, чтобы тоже является ограничением, но оно присутствует во всех задачах подобного типа и его не принято называть ограничением. Любое неотрицательное решение системы (4) будем называть допустимым, а решение, реализующее минимум, - оптимальным.
Отметим, что уравнения системы (4) с геометрической точки зрения представляют плоскости в Чтобы задача о минимуме была содержательной, необходимо, чтобы число ограничений типа равенств было меньше
Например, при наличие двух ограничений означает, что неотрицательное решение системы должно быть точкой пересечения прямых, представляющих уравнения системы. Тогда задача о нахождении сводится к вычислению в этой точке. Если прямые параллельны, то задача теряет смысл. Если ограничений больше двух, то система или несовместна, или же все прямые принадлежат одному пучку:
В этом случае минимум также равен
В ряде практических задач (например, в задаче о диете) ограничения носят вид неравенств
Однако от одного типа ограничений легко перейти к другому. В самом деле, если ограничения носят характер неравенств (5), то вводим новые добавочные неизвестные с помощью уравнений
Тогда неравенства (5) равносильны условию
и мы пришли к ограничениям типа равенств (4), хотя и с большим числом переменных.
Обратно, пусть имеют место ограничения типа равенств (4). Тогда, решая эту систему (например, методом исключения неизвестных), мы после некоторого числа шагов или убедимся, что система несовместна, или же разрешим систему (4) относительно некоторых неизвестных:
Здесь - ранг матрицы коэффициентов системы (4).
Подставляя эти выражения в функцию получаем
После этого исходная задача может быть сформулирована следующим образом. Даны система
линейных неравенств с неизвестными и линейная функция
Требуется среди всех неотрицательных решений системы (7) найти такое, которое минимизирует
Эта задача эквивалентна исходной. В самом деле, если
мы нашли решение задачи (7), (8) то, находя
по формулам (6) неотрицательные значения мы получим систему чисел
которая служит решением задачи (1), (4).
Таким образом, задачу линейного программирования можно ставить с ограничениями типа неравенств. Из такой постановки видно, что область в которой мы ищем минимум представляет собой «многогранник» в неотрицательном угле (т. е. когда а ее
граница состоит из «плоских граней», находящихся в плоскостях пространства
Множество называется выпуклым, если
Из системы неравенств (7) ясно, что «многогранник» выпуклый и находится по одну сторону от любой из своих граней.
Слово «многогранник» мы пишем в кавычках, так как могут быть случаи, когда этот «многогранник» будет неограниченной частью неотрицательного угла
Например, при и при тех ограничениях типа неравенств «многоугольник» может быть неограниченным в первой четверти На рис. 54 - заштрихованная часть. В дальнейшем кавычки у слова «многогранник» мы будем опускать.
При нахождении минимума линейной функции на замкнутой области мы последовательно будем переходить на плоские грани меньшей размерности. Отметим, что граница мерного многогранника состоит из нескольких мерных многогранников.
- Если - ограниченный замкнутый многогранник, то линейная функция достигает минимума в некоторой точке границы При рассмотрении линейной функции на этом новом многограннике меньшего числа измерений она снова будет линейной функцией, но от меньшего числа переменных и, следовательно, будет достигать минимума на границе которая состоит из мерных многогранников. Продолжая этот процесс, мы придем к случаю, когда линейная функция рассматривается на одномерной грани (ребре границей которой являются точки (вершины многогранника
Таким образом ясно, что если - ограниченный за-мкнутый многогранник, то линейная функция достигает минимума в некоторой вершине
Если минимальное значение достигается в двух вершинах, конусах ребра, соединяющего эти точки, то в этой ситуации существует бесконечное множество точек, в которых линейная функция достигает минимума.
Возможно, вас также заинтересует эта ссылка:
Помощь по линейному программированию онлайн |
РГР 2.
Найти минимум функции при ограничениях (рис. 55)
- Решение:
Ясно, что область есть треугольник с вершинами в точках Прямая уровня функции
при возрастании от опускается относительно оси (коэффициент при отрицателен); ее первая точка встречи с есть вершина Значение функции в этой точке равно нулю Итак, решение задачи есть
В данном случае можно было бы просто вычислить значение в точках и взять наименьшее:
Векторно-матричная форма задачи линейного программирования. Задачу линейного программирования можно сформулировать также в векторно-матричной форме. Пусть векторы пространства вектор из пространства
- матрица размера составленная из коэффициентов системы ограничений (4). Линейная функция
есть скалярное произведение векторов
Поэтому общую задачу линейного программирования можно записать в следующем виде: требуется минимизировать скалярное произведение при условии и
Примем столбцы матрицы за векторы из
Тогда легко получаем, что
Поэтому систему ограничений можно записать в виде
Если ранг то среди векторов имеется линейно независимых, которые можно принять за базис в пространстве (см. § 16). Следовательно, любой вектор может быть разложен по элементам этого базиса. Нам необходимо выбрать такой базис, чтобы вектор разлагался по векторам этого базиса с неотрицательными коэффициентами
Возможно, вас также заинтересует эта ссылка:
Курсовая работа по линейному программированию заказать готовую онлайн |
Различных мерных базисов из векторов конечное число. Среди них могут быть базисы, по элементам которых вектор разлагается с неотрицательными коэффициентами. Тогда минимум скалярного произведения (линейной функции) достигается на конечном множестве точек - коэффициенты разложения вектора по элементам некоторых базисов.
Если базисов указанного типа нет (вектор не разлагается по элементам базисов с неотрицательными коэффициентами), то задача линейного программирования не имеет решения (неразрешима).
Таким образом, задача состоит в том, как найти базис
так, чтобы
И
Симплекс - метод. Реальные задачи линейного программирования содержат, как правило, большое число ограничений и неизвестных. Поэтому естественно, что решение таких задач связано с большим объемом вычислений. Это затруднение преодолевается с помощью быстродействующих электронно-вычислительных машин (ЭВМ). Для каждой задачи разрабатываются алгоритм и программа, и затем ЭВМ в короткий срок дает решение поставленной задачи.
Существуют и другие общие методы, позволяющие найти решение любой задачи линейного программирования в обозримое число шагов.
Таким является симплекс-метод. Опишем идею этого метода.
Пусть надо найти минимум линейной функции
среди значений удовлетворяющих равенствам
Неотрицательные решения системы (4) мы условимся называть допустимыми, а точку - допустимой точкой. Покажем, как эту задачу можно решить, применяя симплекс-метод.
Пусть ранг матрицы равен - ранг Будем считать, что система (4) разрешима относительно
и числа неотрицательны
В этом случае говорят, что переменные образуют базис - базис Остальные переменные называются свободными или небазисными. Следует обратить внимание, что здесь понятие базиса не совпадает с понятием базиса из § 16.
Вопрос о возможности перехода от системы (4) к системе (12) будет рассмотрен ниже в п. 28.8.
Системы (4) и (12) равносильны, поэтому допустимая точка системы (4) есть допустимая точка системы (12), и обратно.
Очевидно, точка допустимая, ее называют базисным решением, отвечающим базису Будем писать В силу равенств (12) функцию можно записать в виде линейной функции от переменных
Очевидно, что Первый этап симплекс-метода связан с рассмотрением функции определяемой равенством (13), и системы ограничений в виде равенств (12).
Возможно, вас также заинтересует эта ссылка:
Задачи по линейному программированию с решением |
РГР 3.
Найти базисные переменные в системе ограничений
где - некоторое число.
- Решение:
Если то система ограничений несовместна в области Поэтому будем считать Выясним, при каком элементы будут базисом. Имеем Далее,
Отсюда
Таким образом, при все отношения базис.
Для того чтобы написать систему (12), нет необходимости вычислять все нужные определители. Надо просто преобразовывать матрицу как мы это делали в § 4.7.
Пусть Получим базис из элементов Для этой цели будем матрицу преобразовывать так,
чтобы в первых трех столбцах по главной диагонали стояли 1, а на остальных местах - 0. Итак,
Последняя матрица определяет следующую систему уравнений:
Возможно, вас также заинтересует эта ссылка:
Заказать работу по линейному программированию помощь в учёбе |