Навигация
Общая характеристика задачи линейного
62893
знака
11
таблиц
17
изображений
1.1 Общая характеристика задачи линейного
программирования
При рассмотрении задач линейного программирования, следует помнить что, с одной стороны, они являются специальным случаем общей задачи оптимизации. Тем самым для задач линейного программирования оказываются справедливыми соответствующие результаты относительно общих свойств и способов их решения, разработанные в теории решения экстремальных задач. С другой стороны, специальная форма задания целевой функции и ограничений в форме линейных функций приводит к появлению у данного класса задач целого ряда специальных свойств, которые послужили основой разработки специализированных методов и алгоритмов их решения. Для детального анализа этих специальных свойств следует рассмотреть общую математическую постановку задачи линейного программирования.
1.2 Математическая постановка задачи линейного
программирования
В общем случае математическая постановка задачи линейного программирования, может быть сформулирована в следующем виде:
f(x1,x2…,,x n)®
где (1.1)
x1,x2…,,x n
(1.2)
(k
{1,2,…,m}).
при этом следует принимать во внимание следующие принципиальные предположения о характере целевой функции и левых частей ограничений:
1. Целевая функция f(x1,x2…,,x n ) предполагается линейной относительно всех своих переменных, т.е. может быть представлена в форме всех своих представлена в форме: f(x1,x…,,x n)=с1х1+с2х2+…+с n x n.
2. Левые части ограничений g k(x1,x2…,,x n) (
{1,2,…,m}) также является линейными функциями относительно своих переменных x1,x2…,,x n, т.е. могут быть представлены в форме: g k(x1,x2…,,x n)=ак1х+ак2х2+…+а к n x n.
3. Переменные x1,x2…,,x n могут принимать свои значения только из множество неотрицательных действительных чисел R1+ ,т.е. хi 
R1+ (
{1,2,…,n}).
С учетом сделанных предположений общая задача линейного программирования может быть сформулирована следующим образом.
Необходимо найти максимум линейной целевой функции n переменных x1,x2…,,x n R1+ следующего вида:
с1х1+с2х2+…+с n x n ® (1.3)
где множество допустимых альтернатив 
формируется следующей системой ограничений типа равенств и неравенств:
аi1х+аi2х2+…+а in x n=bi ({1,2,…,q}). (1.4)
ак1х+ак2х2+…+а к n x n.
bk ({q+1,2,…,m}). (1.5)
В математической постановке общей задачи линейного программирования через сi, aki , bk ({1,2,…,n}),({1,2,…,m}) обозначены постоянные величины, которые могут принимать произвольные, не обязательно целочисленные значения, определяемые спецификой конкретной задачи линейного программирования.
В случае отсутствия ограничений типа равенств (1.4), т.е. при q=0, задача линейного программирования называется стандартной задачей линейного программирования, которая, с учетом сделанных предположений, может быть записана в следующем виде:
с1х1+с2х2+…+с n x n ® (1.6)
где множество допустимых альтернатив 
формируется следующей системой ограничений типа неравенств:
(1.7)
и x1,x2…,,x n
0
С другой стороны, при отсутствии ограничений типа неравенств (1.5), т.е. при q=m, задача линейного программирования называется канонической или основной задачей линейного программирования, которая с учетом сделанных предположений, может быть записана в следующем виде:
с1х1+с2х2+…+с n x n ® (1.8)
где множество допустимых альтернатив формируется следующей системой ограничений типа неравенств:
(1.9)
и x1,x2…,,x n 0.
При рассмотрении общих особенностей задачи линейного программирования удобной оказывается стандартная форма математической постановки задачи линейного программирования (1.6) и (1.7). Анализ множества допустимых альтернатив стандартной задачи линейного программирования (1.6) и (1.7) позволяет прийти к выводу о справедливости только одной из трех возможных ситуаций:
1. Система ограничений (1.7) противоречива или несовместна, т.е. не существует ни одного выбора значений x1,x2…,,x которые удовлетворяют ограничениям (1.7). В этом случае задача линейного программирования не имеет решения.
2. Система ограничений (1.7) не является противоречивой, однако соответствующая ей область пространства Rn является неограниченной. В этом случае задача линейного программирования не имеет решения, в случае, если линейная функция (1.6) не ограничена в неограниченной области, соответствующей множеству допустимых альтернатив .
3. Система ограничений (1.7) не является противоречивой, и при этом соответствующая ей область пространства Rn является ограниченной. В этом случае задача линейного программирования имеет решения.
В последней ситуации задача линейного программирования может иметь либо единственное решение, либо континуум решений. Континуум решений имеет место в том случае, когда линейная целевая функция оказывается параллельной функции левой части одного из ограничений.
ГЛАВА II Основные методы решения задач линейного программирования
В общем случае существует два подхода к решению задач оптимизации. С одной стороны, для решения задачи линейного программирования теоретически может быть использован некоторый аналитический способ решения, применимый для решения задач оптимизации в общей постановке.
Однако использование для решения задач линейного программирования аналитического способа решения, основанного, например, на методе множителей Лагранжа, с учетом дифференцируемости целевой функции и ограничений, связано с преодолением серьезных трудностей вычислительного характера. В этом случае, даже для небольшого числа переменных и ограничений, решения задачи линейного программирования сводится к нахождению частных производных функции Лагранжа с последующим решением системы уравнений с большим числом переменных. Именно по этой причине аналитический способ решения задач линейного программирования не используется на практике.
С другой стороны для решения задачи линейного программирования могут быть использованы алгоритмические методы решения, применимые для решения задач оптимизации в общей постановке. Эти методы основываются на идее градиентного поиска для задач оптимизации с ограничениями.
Однако наибольшее применение для задач линейного программирования получили алгоритмические способы решения соответствующих задач, которые учитывают специфические особенности целевой функции и множества допустимых решений. Из алгоритмических способов следует отметить получивший широкую известность симплекс- метод для решения задач линейного программирования и метод потенциалов для решения транспортной задачи.
Для решения задач линейного программирования в программе MS EXCEL реализованы приближенные методы их решения с достаточно высокой степенью точности. Оценить получаемых решений можно посредством сравнения аналитических и алгоритмических решений отдельных практических задач.
Похожие работы
... задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов. 3. Решение задач 3.1. Решение задачи линейного программирования 3.1.1.Постановка задачи Сформулируем задачу: Определить значения переменных, обеспечивающие минимизацию целевой функции. Составим целевую функцию и зададим ограничения. ...
... ячеек свидетельствует о том, что возможно лучшее решение и наоборот, если отрицательных ячеек нет, то было найдено оптимальное решение. 2. Содержательная постановка задачи Частным случаем задачи линейного программирования является транспортная задача. Проблема транспортировки включает поиск низко затратных схем распределения товарных запасов от многих источников до многих мест назначения ...
... F = 27*100 + 30*30 + 24*70 + 18*190 + 21*60 + 23*120 + 31*80 = 15110 Результат: Затраты на распределение товаров между магазинами найденные методом наименьшей стоимости составят 15110 рублей. 2.6 Применение возможностей электронных таблиц при решении транспортной задачи Для решения транспортной задачи также можно применять электронные таблицы (Microsoft Office Excel ). Для решения ...
... ). Требуется распределить все работы между всеми рабочими так, чтобы время выполнения работ было минимальным, а каждую работу выполнял только один рабочий. §4. Решение транспортной задачи в Excel В качестве примера я рассмотрел транспортную задачу для 2 складов и 5 магазинов. · В ячейки C4:C5 записал объемы продукции, имеющиеся на 2 складах. · В ячейки E5:I5 - заявки на продукцию, ...
0 комментариев