Общая задача линейного программирования реферат

Выбранная небазисная переменная будет включаться в новый базис, поэтому называется включаемой переменной. Базисная переменная, которая будет выведена из базиса, называется исключаемой переменной. Исключаемой переменой будет та базисная переменная, которая первой обратится в «0» при переходе в смежную вершину после ввода включаемой переменной. Переменные R определяют начальный допустимый базис с точки зрения возможного дальнейшего перехода в одну из вершин ОДР. За использование искусственных переменных в целевой функции вводится штраф М. В задаче максимизации М отрицательное (М>0). Преобразуем базисное решение: xb i Ü xb i — q * , i ¹ r, xb r Ü q и переходим к этапу 2. 3.2. Мультипликативная форма обратной матрицы Назовем элементарной матрицей матрицу, отличающуюся от единичной только одной строкой или столбцом. При мультипликативном представлении матрица не дается явно, а представляется в виде произведения накапливаемых элементарных матриц. Это относится к точности, скорости и требованиям к памяти.

Реферат на тему общая задача линейного программирования

Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных и называется математическим программированием. В классическом математическом анализе рассматривается задача отыскания условного экстремума функции. Основным инструментом при решении этих задач стало математическое моделирование — формальное описание изучаемого явления и исследование с помощью математического аппарата. Искусство математического моделирования состоит в том, чтобы учесть как можно больше факторов по возможности простыми средствами. Именно в силу этого процесс моделирования часто носит итеративный характер. На первой стадии строится относительно простая модель и проводится ее исследование, позволяющее понять, какие из существенных свойств изучаемого объекта не улавливаются данной формальной схемой. Затем происходит уточнение, усложнение модели. В большинстве случаев первой степенью приближения к реальности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, предполагаются линейными. Здесь имеется полная аналогия с тем, как весьма важна и зачастую исчерпывающая информация о поведении произвольной функции получается на основе изучения ее производной — происходит замена этой функции в окрестности каждой точки линейной зависимостью. Значительное количество экономических, технических и других процессов достаточно хорошо и полно описывается линейными моделями. Основные формы задачи ЛП. Различают три основные формы задач линейного программирование в зависимости от наличия ограничений разного типа. Вектор называется вектором коэффициентов линейной формы, — вектором ограничений. Стандартная задача важна ввиду наличия большого числа прикладных моделей, сводящихся наиболее естественным образом к этому классу задач ЛП. Каноническая задача ЛП. или, в матричной записи, Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.

Для этого выбирают небазисную переменную, имеющую максимально отрицательный (положительный) коэффициент в – строке. Большая часть этих преимуществ определяется тем фактором, что, как правило, матрицы больших линейных задач (то есть с n>m>100) являются слабозаполненными, содержат малый процент ненулевых элементов.