Теоретическая основа линейного программирования, Постановка задачи, Методы решения задач линейного программирования, Симплекс - метод, Геометрический метод - Использование методов линейного программирования
Постановка задачи
Постановка практической задачи ЛП включает следующие основные этапы:
- - определение показателя эффективности, переменных задачи, - задание линейной целевой функции S(x), подлежащей минимизации или максимизации, - задание ограничений.
Приведем сейчас общую математическую формулировку основной задачи линейного программирования.
Дана система линейных уравнений с n неизвестными:
A11 x1 + a11 x2 + ...... + a11 xn = b1 ,
A21 x1 + a22 x2 + ...... + a2n xn = b2 ,
Am1 x1 + am2 x2 + ...... + amn xn = bm,
И линейная функция
F = c1 x1 + c2 x2 +.........+ cn xn (1.2)
Требуется найти такое неотрицательное решение системы
X1 ?0, x2 ?0, ... ... , xn ?0 (1.3)
При котором функция f принимает наименьшее значение.
Уравнения (1.1) называют системой ограничений данной задачи; функцию f -- целевой функцией (или линейной формой).
Методы решения задач линейного программирования
Симплекс - метод
Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного итеративного процесса, необходимо улучшающего значение целевой функции на каждом шаге.
Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X1,...,Xn), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1,...,Xm), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1:
X0+ A0,m+1*XM+1 + ... + A0,n*XN = A0,0
X1+ A1,m+1*XM+1 + ... + A1,n*XN = A1,0
XI+ AI, m+1*XM+1 + ... + AI, n*XN = AI,0
XM + AM, m+1*XM+1 + ... + AM, n*XN = AM,0
Данная формальная модель задачи линейного программирования обычно задается в форме так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода:
Симплекс-таблица
1 |
X1 |
X2 |
Xm |
Xm+1 |
Xn | |
X0 |
A0,0 |
0 |
0 |
0 |
A0,m+1 |
A0,n |
X1 |
A1,0 |
1 |
0 |
0 |
A1,m+1 |
A1,n |
X2 |
A2,0 |
0 |
1 |
0 |
A2,m+1 |
A2,n |
Xm |
Am,0 |
0 |
0 |
1 |
Am, m+1 |
Am, n |
Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует определенному ограничению-равенству задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X1, ..., Xm). Сверху от таблицы приведен набор всех переменных задачи, где Xm+1, ..., Xn - свободные переменные задачи.
Преобразования таблицы надо производить до тех пор, пока не будет получена симплекс-таблица, которая одновременно является прямо и двойственно допустимой.
Данный метод получил широкое распространение и большую популярность по сравнению с другими подходами, так как крайне редко на практике встречаются задачи трудные для симплекс-метода.
Геометрический метод
Применяется дя задач с двумя переменными. Метод решения состоит в следующем:
На плоскости Ох1х2 строятся прямые, которые задают соответствующие ограничения:
A11 x1 + a11 x2 + ...... + a11 xn = b1 ,
A21 x1 + a22 x2 + ...... + a2n xn = b2 ,
Am1 x1 + am2 x2 + ...... + amn xn = bm.
Находим множество всех точек х1,х2, удовлетворяющим всем неравенствам. Такое множество называется областью допустимых решений. Строим вектор и перемещаем линию уровня, который задается уравнением: с1х1+с2х2 = const в направлении вектора до последней точки пересечения с ОДР. Эта точка и дает решение задачи Lmax = значению L в этой точки
Похожие статьи
-
Теоретическая основа линейного программирования, Симплекс метод - Линейное программирование
Симплекс метод Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного...
-
Геометрический метод, Двойственная задача - Линейное программирование
Применяется для задач с двумя переменными. Метод решения состоит в следующем: На плоскости строятся прямые, которые задают соответствующие ограничения:...
-
"РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL" Цель работы Приобретение навыков решения задач линейного программирования...
-
Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования,...
-
Методика решения задач ЛП графическим методом - Линейное программирование
I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые. II. Найти и заштриховать...
-
Это задача оптимизации, в которой переменные принимают только два значения: "единица - ноль". Пример - задача "коммивояжера". Цель работы: минимизировать...
-
Решение задач линейного программирования - Основы информатики
Имеются n пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции с i-го пункта производства в j-ый центр...
-
Формулировка задачи - Линейное программирование
Даны линейная функция Z=С1 х1 +С2 х2 +...+СN xN (1.1) И система линейных ограничений A11 x1 + a22 x2 +... + a1N ХN = b1 A21 x1 + a22 x2 +... + a2N ХN =...
-
Предложенный подход к решению задач исследования Используя в качестве основы присутствующее в наличии программное обеспечение, которое применимо к...
-
Введение - Использование методов линейного программирования
Линейное программирование -- область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся...
-
Варианты - Решение задач линейного программирования с использованием Microsoft Excel
Используя MS Excel, найти решение для модели ЛП, соответствующей заданному варианту (табл. 1.5). Таблица 1.5 Варианты задач к лабораторной работе № 1 №...
-
1. Каковы основные этапы решения задач ЛП в MS Excel? 2. Каков вид и способы задания формул для целевой ячейки и ячеек левых частей ограничений? 3. В чем...
-
Линейное программирование, Имитационное моделирование - Офисные автоматизированные технологии
Задачи нахождения значений параметров, при которых получается экстремум целевой функции с учетом ограничений, наложенных на ее аргументы, называются...
-
Вариант №1 1. Выбрать и обосновать наиболее эффективный метод решения задачи. 2. Разработать алгоритм и программу для решения задачи в общем виде. 3....
-
Транспортная задача оптимальность Поставим в соответствие поставщикам потенциалы Ui, , а потребителям - Vj, . В оптимальном плане для всех базисных...
-
Теорема. Чтобы транспортная задача была разрешима, необходимо и достаточно, чтобы выполнялось условие: (1.5) Доказательство: Необходимость. Пусть...
-
Транспортная задача - Линейное программирование
Одна из наиболее распространенных задач математического программирования -- транспортная задача. В общем виде ее можно представить так: требуется найти...
-
Информатика является основной базой для проведения научно-исследовательских и проектно-технических работ в современной промышленности. С помощью...
-
Теоретические предпосылки исследования Системы поддержки принятия решений Системы поддержки принятия решений (СППР), представляют собой приложения узкого...
-
Выведем в общем виде уравнение движения заданной динамической модели при помощи уравнений Лагранжа II рода. Полная кинетическая энергия: , Полная...
-
Введение - Линейное программирование
Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой...
-
Описание алгоритма - Решение системы линейных уравнений методом Гаусса
Согласно заданию необходимо разработать программу для решения линейных уравнений методом Гаусса. Поскольку данная программа является приложением Windows,...
-
Математическое обеспечение позволяет использовать методы автоматизированного поиска оптимальных вариантов при проектировании системы. Часто при решении...
-
Средствами решения задачи является алгоритмический язык С++. Операторы и функции, используемые для решения поставленной задачи: #Include - подключение...
-
На рисунке 1 представлен фрагмент электронной таблицы, в которой содержаться исходные данные для решения задачи. Рисунок 1 - Фрагмент электронной...
-
Метод Гаусса. Метод Гаусса решения систем линейных уравнений состоит в последовательном исключении неизвестных и описывается следующей процедурой. С...
-
Любой объект можно связать с набором процедур, исполняемых в строго определенные моменты. Процедура ( Procedure ) - это группа операторов языка....
-
Языки и системы программирования, их эволюция - Автоматизация решения задач пользователя
Язык программирования - это способ записи программ решения различных задач на ЭВМ в понятной для компьютера форме. Процессор компьютера непосредственно...
-
Понятие линейной стохастической сети Одним из важных этапов технологического проектирования электронных вычислительных средств является расчет запусков...
-
Постановка задачи Целью работы является изучение основных этапов автоматизированного структурного проектирования технологических маршрутов: -...
-
Аннотация В статье рассматриваются два способа уменьшения времени вычисления дерева решений для задач линейного параметрического программирования с...
-
Численные методы. Интерполяция Ньютона
Задание 1 Запишите порядок выполняемых вами операций, оцените погрешности их результатов, вычислите и запишите искомое значение. Определите число верных...
-
Что такое уровень языка программирования - Основы программирования
В настоящее время в мире существует несколько сотен реально используемых языков программирования. Для каждого есть своя область применения. Любой...
-
Структура оптимизационных задач - Методологические основы оптимизации
Здесь важно отметить, что оптимизационные задачи имеют весьма разнообразные области приложений. Однако, несмотря на это, в целом, их формальное описание...
-
Линейное программирование - Линейное программирование
Линейный программирование математический графический Что же такое линейное программирование? Это один из первых и наиболее подробно изученных разделов...
-
Заключение - Линейное программирование
В данной дипломной работе мною были освоены навыки решения задач линейного программирования геометрическим методом. Для этого я изучил теоретические...
-
Вычислить максимум функции F(x)=-L(x1)x2+3.1L(x2)x+5 на отрезке [a;b] с точностью е. L(x1), L(x2) - значения интерполяционного многочлена, построенного...
-
Моделирования случайных процессов - Теоретические основы информационных технологий
Моделирование случайных процессов - мощнейшее направление в современном математическом моделировании. Событие называется случайным, если оно достоверно...
-
К задачам параметрической оптимизации, относятся следующие задачи: - Определение оптимальных значений параметров. - Назначение оптимальных допусков на...
-
Результаты расчета (точки искомой функции) сохраняются в переменных-массивах: для аргумента X и функции Y, которые отображаются в виде таблицы или...
Теоретическая основа линейного программирования, Постановка задачи, Методы решения задач линейного программирования, Симплекс - метод, Геометрический метод - Использование методов линейного программирования