РГР по линейному программированию

РГР по линейному программированию расчетно графическая работа

 

Если у вас нету времени на ргр по линейному программированию вы всегда можете попросить меня, вам нужно написать мне, и я вам помогу онлайн или в срок 1-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. Итак,

РГР по линейному программированию

Последняя матрица определяет следующую систему уравнений:

РГР по линейному программированию