Общий вид модели линейного программирования. Шпаргалка: Шпаргалка по Математическому программированию. Оптимальное решение — задача — линейное программирование

29.05.2020

На практике ограничения в задаче линейного программирования часто задаются не уравнениями, а неравенствами.

Покажем, как можно перейти от задачи с ограничениями-неравенствами к основной задаче линейного программирования.

Пусть имеется задача линейного программирования с переменными , в которой ограничения, наложенные на переменные, имеют вид линейных неравенств. В некоторых из них знак неравенства может быть а других (второй вид сводится к первому простой переменой знака обеих частей). Поэтому зададим все ограничения-неравенства в стандартной форме:

Требуется найти такую совокупность неотрицательных значений которая удовлетворяла бы неравенствам (4.1), и, кроме того, обращала бы в минимум линейную функцию:

От поставленной таким образом задачи легко перейти к основной задаче линейного программирования. Действительно, введем обозначения:

где - некоторые новые переменные, которые мы будем называть «добавочными». Согласно условиям (4.1), эти добавочные переменные так же, как и должны быть неотрицательными.

Таким образом, перед нами возникает задача линейного программирования в следующей постановке: найти такие неотрицательные значения переменных чтобы они удовлетворяли системе уравнений (4.3) и одновременно обращали в минимум линейную функцию этих переменных:

Как видно, перед нами в чистом виде основная задача линейного программирования (ОЗЛП). Уравнения (4.3) заданы в форме, уже разрешенной относительно базисных переменных которые выражены через свободные переменные Общее количество переменных равно , из них «первоначальных» и «добавочных». Функция L выражена только через «первоначальные» переменные (коэффициенты при «добавочных» переменных в ней равны нулю).

Таким образом, задача линейного программирования с ограничениями-неравенствами сведена нами к основной задаче линейного программирования, но с большим числом переменных, чем первоначально было в задаче.

Пример 1 Имеется задача линейного программирования с ограничениями-неравенствами: иайти неотрицательные значения переменных удовлетворяющие условиям

и обращающие в минимум линейную функцию

Требуется привести эту задачу к виду ОЗЛП.

Решение. Приводим неравенства (4.4) к стандартной форме;

Вводим дополнительные переменные:

Задача сводится к тому, чтобы найти неотрицательные значения переменных

удовлетворяющие уравнениям (4.6) и обращающие в минимум линейную функцию (4.5).

Мы показали, как от задачи линейного программирования с ограничениями-неравенствами можно перейти к задаче с ограничениями-равенствами (ОЗЛП). Всегда возможен и обратный переход - от ОЗЛП к задаче с ограничениями-неравенствами. Если в первом случае мы увеличивали число переменных, то во втором случае будем его уменьшать, устраняя базисные переменные и оставляя только свободные.

Пример 2. Имеется задача линейного программирования с ограничениями-равенствами (ОЗЛП):

и минимизируемой функцией

Требуется записать ее как задачу линейного программирования с ограничениями-неравенствами.

Решение. Так как , то выберем какие-то две из переменных в качестве свободных. Заметим, что переменные в качестве свободных выбирать нельзя, так как они связаны первым из уравнений (4 7): значение одной из них полностью определяется значением другой, а свободные переменные должны быть независимыми

По такой же причине нельзя в качестве свободных выбрать переменные (их связывает второе уравнение ). Выберем в качестве свободных переменные и выразим через них все остальные:

Так как условия (4 9) могут быть заменены неравенствами:

Перейдем в выражении линейной функции L к свободным переменным Подставляя в L вместо и их выражения (4.9). получим.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ФГОУ ПО “ПСКОВСКИЙ КОЛЛЕДЖ СТРОИТЕЛЬСТВА И ЭКОНОМИКИ”

Предмет “Математические методы”

Задача линейного программирования

Курсовая работа

Студента группы 315-ПО

Андреева Дмитрия Александровича

Руководитель курсовой работы

Васильева Наталья Анатольевна

Псков 2009 г.

Введение

Глава Ι Линейное программирование

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

§ 2 Математическая модель задачи линейного программирования

§ 3 Каноническая форма задачи линейного программирования

Глава ΙΙ Решение задачи симплексным методом

§ 1 Постановка задачи

§ 2 Составление математической модели задачи

§ 3 Алгоритмы решения задачи симплексным методом

§ 4 Построение начального опорного решения методом Гаусса

§ 5 Решение задачи

Заключение

Литература

Введение

В настоящее время множество задач планирования и управления в отраслях народного хозяйства, а также большой объём частных прикладных задач решаются методами математического программирования. Наиболее развитыми в области решения оптимизационных задач являются методы линейного программирования. Эти методы позволяют описать с достаточной точностью широкого круга задач коммерческой деятельности, таких, как планирование товарооборота; размещение розничной торговой сети города; планирование товароснабжения города, района; прикрепление торговых предприятий к поставщикам; организация рациональных перевозок товаров; распределение работников торговли должностям; организация рациональных закупок продуктов питания; распределение ресурсов; планирование капиталовложений; оптимизация межотраслевых связей; замена торгового оборудования; определение оптимального ассортимента товаров в условиях ограниченной площади; установление рационального режима работы.

В задачах линейного программирования критерий эффективности и функции в системе ограничений линейны.

Если в задаче математического программирования имеется переменная времени, а критерий эффективности выражается через уравнения, описывающие течение операций во времени, то такая задача является задачей динамического программирования.

Во многих экономических моделях зависимости между постоянными и переменными факторами можно считать линейными.

Использование методов математического программирования в коммерческой деятельности связано со сбором необходимой информации коммерсантом, экономистом, финансистом, затем постановкой задачи вместе с математикой. Поскольку методы математического программирования уже реализованы на компьютере в виде пакета стандартных программ, то доступ к ним обычно прост, автоматизирован и не составляет особых трудностей.

Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.

Глава Ι Линейное программирование

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

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

Постановка задачи коммерческой деятельности может быть представлена в виде математической модели линейного программирования, если целевая функция может быть представлена в виде линейной формы, а связь с ограниченными ресурсами описать посредством линейных уравнений или неравенств. Кроме того, вводится дополнительное ограничение – значения переменных должны быть неотрицательны, поскольку они представляют такие величины, как товарооборот, время работы, затраты и другие экономические показатели.

Геометрическая интерпретация экономических задач даёт возможность наглядно представить, их структуру, выявить особенности и открывает пути исследования более сложных свойств. Задача линейного программирования с двумя переменными всегда можно решить графически. Однако уже в трёхмерном пространстве такое решение усложняется, а в пространствах, размерность которых более трёх, графическое решение, вообще говоря, невозможно. Случай двух переменных не имеет особого практического значения, однако его рассмотрение проясняет свойства задач линейного программирования, приводит к идее её решения, делает геометрически наглядными способы решения и пути их практической реализации.

§ 2 Математическая модель задачи линейного программирования

Перед решением задачи составляем её математическую модель.

Математическая модель – это совокупность соотношений состоящие из линейной целевой функции и линейных ограничений на переменную.

Принцип составления математической модели.

1. Выбирают переменные задачи.

Переменными задачи называются величины

Которые полностью характеризуют экономический процесс, описанный в задачи. Обычно записываются в виде вектора X = () Причём )

2. Составляют систему ограничения задачи.

Система ограничений – это совокупность уравнений и неравенств, которым удовлетворяют переменные задачи и которая следует из ограниченности экономических условий задачи.

В общем виде система записывается в виде

3. Задают целевую функцию.

Целевая функция – это функция Z(X) которая характеризует качество выполнения задачи, экстремум которой надо найти. В общем виде целевая функция записывается Z(X) =

т.о. математическая модель имеет вид найти переменные задачи

удовлетворяющие системе ограничений:

и условию неотрицательности

0 (j = ), которая обеспечивает экстремум целевой функции Z(Y) =

Допустимым решением задачи линейного программирования называется любой набор значений переменных удовлетворяющий системе ограничений и условной неотрицательности.

Множество допустимых решений образует область допустимых решений задачи (ОДР).

Оптимальным решением называется допустимое решение задачи, при котором целевая функция достигает экстремума.

§ 3 Каноническая форма задачи линейного программирования

Математическая модель задачи должна иметь каноническую форму.

Если система ограничения состоит только из уравнения и все переменные удовлетворяют условию неотрицательности, то задача имеет каноническую форму.

Если в системе есть хотя бы одно неравенства или какая–либо переменная неограниченна условию неотрицательности, то задача имеет стандартную форму. Чтобы привести задачу к каноническому виду надо:

перейти от неравенств к уравнению следующим образом: в левую часть неравенств вводим дополнительную переменную с коэффициентом (+1) для неравенства (

) и (-1) для неравенства () дополнительные переменные не наложены целевые неотрицательности, то её заменяют разностью двух неотрицательных переменных, то есть: = – (

Общий вид канонической формы:

Глава ΙΙ Решение задачи симплексным методом

Симплексный метод – это метод последовательного улучшения плана (решения), наиболее эффективный и применяется для решения любой задачи линейного программирования.

Название метода от латинского simplecx – простой т.к. из начального область допустимых решений задачи имела простейший вид. Идеи метода предложил российский математик Контарович Л.В. в 1939 году и затем эту идею развил и разработал Дж. Данциг в 1949 году.

Симплексный метод позволяет за конечное число шагов либо найти оптимальное решение либо доказать что его нет.

§ 1 Постановка задачи

На предприятии в процессе производства используется 3 вида станков Ι, ІΙ, ІΙІ. При этом расходуется сырьё, трудовые ресурсы, и учитываются накладные расходы.

Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалента минимизации той же функции, взятой с противоположным знаком, и наоборот.

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

если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;
если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
если некоторая переменная x j не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными:
x 3 = x 3 + — x 3 — , где x 3 + , x 3 — ≥ 0 .

Пример 1 . Приведение к канонической форме задачи линейного программирования:

min L = 2x 1 + x 2 — x 3 ;
2x 2 — x 3 ≤ 5;
x 1 + x 2 — x 3 ≥ -1;
2x 1 — x 2 ≤ -3;
x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

Введем в каждое уравнение системы ограничений выравнивающие переменные x 4 , x 5 , x 6 . Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x 4 , x 6 вводятся в левую часть со знаком "+", а во второе уравнение переменная x 5 вводится со знаком "-".

2x 2 — x 3 + x 4 = 5;
x 1 + x 2 — x 3 — x 5 = -1;
2x 1 — x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:

2x 2 — x 3 + x 4 = 5;
-x 1 — x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 — x 6 = 3.

В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть отрицательными. Допустим, что x 1 = x 1 ‘ — x 7 , где x 1 ‘ ≥ 0, x 7 ≥ 0 .

Подставляя данное выражение в систему ограничений и целевую функцию и, записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме:

L min = 2x 1 ‘ + x 2 — x 3 — 2x 7 ;
2x 2 — x 3 + x 4 = 5;
-x 1 ‘ — x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 ‘ + x 2 — x 6 + 2x 7 = 3;
x 1 ‘ ≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.

Условие оптимальности базисного плана канонической задачи ЛП. Симплекс-метод и его сходимость.

Симплексный метод является универсальным, так как позволяет решать практически любую задачу линейного программирования, записанную в каноническом виде.

Идея симплексногометода последовательного улучшения плана, заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному.

Значение целевой функции при этом перемещении для задач на максимум не убывает.

Так как число опорных решений конечно, то через конечное число шагов получим оптимальное опорное решение.

Опорным решением называется базисное неотрицательное решение.

Алгоритм симплексного метода

1. Математическая модель задачи должна быть канонической. Если она неканоническая, то ее надо привести к каноническому виду.

2. Находим исходное опорное решение и проверяем его на оптимальность.
Для этого заполняем симплексную таблицу 1.
Все строки таблицы 1-го шагазаполняем по данным системы ограничений и целевой функции.

Возможны следующие случаи при решении задач на максимум:

1. Если все коэффициенты последней строки симплекс-таблицы Dj ³ 0, то найденное

решение оптимальное.

2 Если хотя бы один коэффициент Dj £ 0, но при соответствующей переменной нет ни одного положительного оценочного отношения, то решение задачи прекращаем , так как F(X) ® ¥ , т.е.целевая функция не ограничена в области допустимых решений.

Если хотя бы один коэффициент последней строки отрицателен, а при соответствующей переменной есть хотя бы одно положительное оценочное отношение, то нужно перейти к другому опорному решению.

Если отрицательных коэффициентов в последней строке несколько, то в столбец базисной переменной (БП) вводят ту переменную , которой соответствует наибольший по абсолютной величине отрицательный коэффициент.

5. Если хотя бы один коэффициент Dk < 0 ,то k — тый столбец принимаем за ведущий.

6. За ведущую строку принимаем ту, которой соответствует минимальное отношение свободных членов bi к положительным коэффициентам ведущего, k – того столбца.

7. Элемент, находящийся на пересечении ведущих строк и столбца, называется ведущим элементом.

Заполняем симплексную таблицу 2:

· заполняем базисный столбец нулями и единицей

· переписываем ведущую строку, разделив ее на ведущий элемент

· если ведущая строка имеет нули, то в следующую симплекс-таблицу можно перенести соответствующие столбцы

· остальные коэффициенты находим по правилу “прямоугольника”

Получаем новое опорное решение, которое проверяем на оптимальность:

Если все коэффициенты последней строки Dj ³ 0, то найденное решение максимальное.

Если нет, то заполняем симплексную таблицу 8-го шага и так далее.

Если целевая функция F(X) требует нахождения минимального значения , то критерием оптимальности задачи является неположительность коэффициентов Dj при всех j = 1,2,…n.

Сходимость симплекс-метода. Вырожденность в задачах ЛП. Важнейшим свойством любого вычислительного, алгоритма является сходимость, т. е. возможность получения в ходе его применения искомых результатов (с заданной точностью) за конечное число шагов (итераций).

Легко заметить, что проблемы со сходимостью симплекс-метода потенциально могут возникнуть на этапе выбора значения r (п. 2") в случае, когда одинаковые минимальные значения отношения

будут достигнуты для нескольких строк таблицы Т (q) одновременно. Тогда на следующей итерации столбец b(β(q+1)) будет содержать нулевые элементы.

⇐ Предыдущая12345Следующая ⇒

Дата публикования: 2015-11-01; Прочитано: 4190 | Нарушение авторского права страницы

Studopedia.org — Студопедия.Орг — 2014-2018 год.(0.002 с)…

Оптимальное решение — задача — линейное программирование

Cтраница 1

Оптимальное решение задачи линейного программирования достигается в одной из опорных точек, где по крайней мере k п, — т переменных равны нулю.

Используя оптимальное решение задачи линейного программирования, можно найти допустимые изменения ДС, при которых еще L остается постоянным.

Если существует оптимальное решение задачи линейного программирования, то существует базисное оптимальное решение.

Поскольку z — оптимальное решение задачи линейного программирования, имеющей т ограничений, в этом решении содержится не более чем т строго положительных переменных.

Доказано , что оптимальное решение задачи линейного программирования находится на границе области допустимых значений управляемых переменных, представляющей собой многогранник в / г-мерном пространстве, определенной системой линейных ограничений. Координаты каждой вершины определяются путем решения системы уравнений (ограничения) и при наличии п управляемых переменных и m ограничений приходится Ст п разрешать систему из т уравнений. Сочетание Спт п (т — п очень быстро растет с увеличением тип, поэтому поиск решения требует очень большого числа вычислений, недоступных даже для ЭВМ.

Итак, в случае D 1 оптимальное решение задачи линейного программирования оказывается автоматически целочисленным.

Как было показано в части 1, оптимальное решение задачи линейного программирования отнюдь не обязательно целрчислен-но, и в то же время существует много задач, природа которых требует целочисленности решения. Некоторые из этих задач на первый взгляд не являются задачами целочисленного программирования, однако они могут быть сформулированы как таковые.

Очевидно, что не всякое базисное решение является оптимальным решением задачи линейного программирования. Однако оптимальное решение невырожденной задачи всегда должно быть базисным для системы уравнений (VIII, 42), и, таким образом, задача отыскания оптимального решения заключается в переборе только базисных решений системы уравнений (VIII, 42), среди которых отыскивается оптимальное.

Очевидно, что не всякое базисное решение является оптимальным решением задачи линейного программирования. Однако оптимальное решение невырожденной задачи всегда должно быть базисным для системы уравнений (VIII42) и, таким образом, задача отыскания оптимального решения заключается в переборе только базисных решений системы уравнений (VIII42), среди которых отыскивается оптимальное.

После выполнения нескольких итераций на шаге 3 могут появиться многочисленные альтернативные оптимальные решения задачи линейного программирования.

ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Такое зацикливание иногда называют сплошной вырожденностью. К сожалению, это явление часто возникает в задачах средней PI большой размерности. Имеется также много примеров задач малой размерности (не более 10 переменных и уравнений), при решении которых для достижения сходимости потребуются тысячи итераций.

В этих случаях используется симплекс-метод, который представляет собой итеративную (пошаговую) процедуру для определения оптимального решения задачи линейного программирования. Расчеты по симплекс-методу начинают с определения допустимого решения, а затем отыскиваются другие допустимые решения и проверяются возможности их улучшения. Переход от одного решения к другому продолжается до тех пор, пока новые улучшения не будут невозможны. Широко распространены стандартные компьютерные программы, которые используют симплекс-метод для решения таких управленческих задач, которые можно представить как задачи линейного программирования.

Если система линейных ограничений обладает специальной структурой, например если она образует сетевую модель, то на шаге 2 при нахождении оптимального решения задачи линейного программирования это обстоятельство можно использовать.

Идея пропорционального распределения была реализована в виде двухэтапного алгоритма расчетов, предложенного И.И.Дикиным , в котором существенно используется свойство метода внутренних точек вырабатывать относительно внутреннюю точку множества оптимальных решений задачи линейного программирования. Это свойство означает, что граничные значения по условиям-неравенствам (2.3.2) — (2.3.4) достигаются только для тех переменных, которые имеют эти граничные значения при любом другом оптимальном решении.

Страницы: 1 2

Графический метод решения задачи линейного программирования

Рассмотрим ЗЛП в стандартной форме для случая двух переменных :

(10)

Пусть система неравенств (10) совместна (имеет хотя бы одно решение). Любое неравенство этой системы геометрически определяет полуплоскость с граничной прямой Условия не отрицательности определяют полуплоскости с соответственными граничными прямыми и .

Так как система совместна, то полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы. Совокупность всех этих точек называется многоугольником решений. Это может быть точка, отрезок, луч, прямая, замкнутый многоугольник, неограниченная многоугольная область.

Решение ЗЛП геометрически представляет собой поиск такой точки многоугольника решений, координаты которой доставляют целевой функции наибольшее (наименьшее) значение. Причем допустимым решением являются все точки многогранника.

Рассмотрим так называемую линию уровня целевой функции z , то есть линию, вдоль которой эта функция принимает одно и то же фиксированное значение : или

Алгоритм решения задачи линейного программирования графическим методом (число переменных ).

1. Строится многоугольная область допустимых решений на плоскости соответствующая ограничениям. Затем строится вектор-градиент

целевой функции z в любой точке область допустимых решений.

2. Прямая (линия уровня функции z ), перпендикулярная вектору-градиенту, передвигается параллельно самой себе в направлении вектора-градиента в случае задачи на максимум (и в противоположном направлении — в случае задачи на минимум) до тех пор, пока она не покинет область допустимых решений. Предельная точка (или точки) области являются оптимальными точками.

3. Для нахождения координат оптимальной точки, надо решить систему уравнений, которая соответствует прямым, пересечение которых образует эту точку.

Формулировка основных типов задач ЛП, построение их математических моделей

Значение целевой функции в этой точке будет оптимальным, а сами координаты точки будут являться решением задачи ЛП.

Пример. Решить геометрически задачу:

Построим многоугольник всех допустимых решений OABCD и направляющий вектор целевой функции (Рис. 1). Направление вектора-градиента указывает направление возрастания целевой функции. Так как рассматриваемая задача на отыскание максимума, то прямую, перпендикулярную вектору перемещаем в направлении этого вектора параллельно самой себе до тех пор, пока эта прямая не покинет область допустимых решений. На границе области, в нашем случае в точке С , и будет решение задачи. Точка С находится на пересечении прямых и . Следовательно, ее координаты определяются решением системы этих уравнений уравнении:

откуда т.е. точка С имеет координаты (6, 4).

Максимум (максимальное значение целевой функции) равен: Ответ: при оптимальном решении т.е. максимальна прибыль может быть достигнута при производстве 6 единиц первой и 4 единиц второй продукции.

ВВЕДЕНИЕ

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

Математические модели, используемые в экономике, можно подразделять на классы по ряду признаков, относящихся к особенностям моделируемого объекта, цели моделирования и используемого инструментария: модели микро– и макроэкономические, теоретические и равновесные, статистические и динамические.

Суть методов оптимизации заключается в том, что исходя из наличия определенных ресурсов выбирается такой способ их использования (распределения), при котором обеспечивается максимум (минимум) интересующего нас показателя.

В качестве методов оптимизации в экономике находят применение все основные разделы математического программирования (планирования).

Математическая дисциплина, занимающаяся изучением экстремальных (максимальных или минимальных) задач управления, планирования и разработкой методов их решения, получила название математического программирования.

В общем, виде математическая постановка экстремальной задачи состоит в определении наибольшего или наименьшего значения целевой функции
при условии ,

где и – заданные функции, а – некоторые действительные числа.

В зависимости от вида функции цели и ограничений математическое программирование делится на линейное и нелинейное. Наиболее

изученным разделом математического программирования является линейное программирование.

Определение.

Задача линейного программирования (стр. 1 из 3)

Линейное программирование – наука о методах использования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения.

Эта линейная функция называется целевой, а ограничения в виде уравнений или неравенств, называется системой ограничений.

Определение. Математическое выражение целевой функции и ее ограничений называется математической моделью экономической задачи.

Рассмотрим некоторые задачи линейного программирования (ЗЛП).

1. Задача об использовании ресурсов (задача планирования производства).

Для изготовления различных изделий предприятие использует три различных вида сырья. Нормы расхода сырья на производство одного изделия , а также общее количество

сырья каждого вида, которое может быть использовано предприятием, приведены в табл.

Составить план производства изделий, при котором общая стоимость всей произведенной предприятием продукции является максимальной.

Построим математическую модель данной задачи.

Обозначим через искомый выпуск изделий , через – изделий ,

через – изделий .

Так как на сырье каждого вида имеются нормы затрат, тогда мы можем найти общий объем затрат сырья каждого вида для изготовления всех изделий. Из таблицы следует, что общий объем сырья I вида составит , II –
,

III –
. А так как на фонд сырья имеются ограничения, следовательно общий объем сырья каждого вида должен быть не больше общего количества сырья, т.е.

получим следующую систему неравенств

(1)

По экономическому смыслу переменные могут принимать только неотрицательные значения:

(2)

Стоимость всех изделий вида составит – – Соответственно общая стоимость произведенной предприятием продукции составит (3)

Нам необходимо найти этой функции. Таким образом, необходимо среди всех неотрицательных решений системы (1) требуется найти такое, при котором функция (3) принимает максимальное значение.

Данную задачу можно легко обобщить на случай выпуска видов изделий с использованием видов сырья (ресурсов).

Обозначим через – число единиц продукции запланированной к производству, – запас ресурсов – го вида, – удельный расход – го ресурса для изготовления – ой продукции. – прибыль от реализации единицы изделия – го вида.

Тогда экономико – математическая модель задачи об использовании ресурсов в общей постановке примет вид: найти такой план
выпуска продукции, удовлетворяющий основной системе ограничений

дополнительной системе ограничений

при котором целевая функция –

принимает максимальное значение.

Замечание. Чтобы составить математическую модель ЗЛП необходимо:

– ввести обозначения переменных;

– исходя из цели экономических исследований, составить целевую функцию;

– учитывая ограничения в использовании экономических показателей задачи и их количественные закономерности, записать систему ограничений.

Решение задач линейного программирования основываются на понятиях аналитической геометрии в – мерном векторном пространстве.

Приведение общей ЗЛП к каноническому виду.

Общий вид ЗЛП следующий:

(1)

(2)

(3)

где соотношение (1) – целевая функция, (2) – система основных ограничений, (3) – система дополнительных ограничений.

Соотношения (2) и (3) образуют полную систему ограничений.

Приведение системы основных ограничений к каноническому виду осуществляется введением в левые части неравенств дополнительных неотрицательных переменных с коэффициентами «+1», если неравенства вида и «-1», если неравенства вида . В целевую функцию дополнительные переменные входят с нулевыми коэффициентами.

Определение . ЗЛП называется заданной в каноническом виде, если ее система основных ограничений представлена уравнениями.

Определение. ЗЛП называется заданной в стандартной форме канонического вида, если выполняются следующие условия:

1) система основных ограничений представлена уравнениями и все они линейно независимы;

2) число уравнений меньше числа переменных;

3) решается задача минимизации целевой функции;

4) правые части системы основных ограничений неотрицательны;

5) все переменные также неотрицательны.

В большинстве методов решения задач линейного программирования предполагается, что система ограничений состоит из уравнений и естественных условий неотрицательности переменных.

Однако при составлении моделей многих задач ограничения в основном формируются в виде системы неравенств, поэтому необходимо уметь переходить от системы неравенств к системе уравнений.

Это может быть сделано следующим образом:

Возьмем линейное неравенство

и прибавим к его левой части некоторую величину , такую, что неравенство превратилось в равенство

При этом данная величина является неотрицательной.

Пример

Привести к каноническому виду задачу линейного программирования:

Решение:

Перейдем к задаче на отыскивание максимума целевой функции.

Для этого изменим знаки коэффициентов целевой функции.

Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x 4 x 5 (на математической модели эта операция отмечена буквой Д).

Переменная х 4 вводится в левую часть второго неравенства со знаком "+", так как неравенство имеет вид "≤".

Переменная x 5 вводится в левую часть третьего неравенства со знаком "-", так как неравенство имеет вид "≥".

В целевую функцию переменные x 4 x 5 вводятся с коэффициентом. равным нулю.

Записываем задачу в каноническом виде:

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Данный метод является методом целенаправленного перебора опорных решений задачи линейного программирования. Он позволяет за конечное число шагов либо найти оптимальное решение, либо установить, что оптимальное решение отсутствует.

Алгоритм симплексного метода решения задач линейного программирования

Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее:

1. Привести задачу к каноническому виду

Тема 8. Линейное программирование

Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)

3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается

5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

Пример решения задачи симплексным методом

Пример 1

Решить симплексным методом задачу:

Минимизировать значение функции

F = 10×1 — 4×3 max

При наличии ограничений в виде неравенств

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x 5 с коэффициентом +1. В целевую функцию переменная x 5 входит с коэффицентом ноль (т.е. не входит).

Получаем:

F = 10×1 — 4×3+0∙x5 max

При наличии ограничений в виде неравенств

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,5,9/15,6) с единичным базисом Б1 = (А4, А5, А6).

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:

Δ k = C б X k - c k

· C б = (с 1 , с 2 , … , с m) - вектор коэффициентов целевой функции при базисных переменных

· X k = (x 1k , x 2k , … , x mk) - вектор разложения соответствующего вектора А к по базису опорного решения

· С к - коэффициент целевой функции при переменной х к.

Оценки векторов входящих в базис всегда равны нулю.

Опорное решение, коэффиценты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу:

Сверху над таблицей для удобства вычислений оценок записываются коэффициенты целевой функции. В первом столбце "Б" записываются векторы, входящие в базис опорного решения. Порядок записи этих векторов соответствует номерам разрешенных неизвестных в уравнениях ограничениях. Во втором столбце таблицы "С б " записываются коэффициенты целевой функции при базисных переменных в том же порядке. При правильном расположении коэффициентов целевой функции в столбце "С б " оценки единичных векторов, входящих в базис, всегда равных нулю.

В последней строке таблицы с оценками Δ k в столбце "А 0 " записываются значения целевой функции на опорном решении Z(X 1).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ 1 = -2, Δ 3 = -9 для векторов А 1 и А 3 отрицательные.

По теореме об улучшении опорного решения, если в задаче на максимум хотя бы один вектор имеет отрицательную оценку, то можно найти новое опорное решение, на котором значение целевой функции будет больше.

Определим, введение какого из двух векторов приведет к большему приращению целевой функции.

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

Вычисляем значения параметра θ 01 для первого и третьего столбцов по формуле:

Получаем θ 01 = 6 при l = 1, θ 03 = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции при введении в базис первого вектора

ΔZ 1 = - 6*(- 2) = 12,

и третьего вектора ΔZ 3 = - 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ 03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение

Х2 = (0,0,3,21,42,0)

с базисом Б2 = (А3, А4, А5).

(таблица 26.2)

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = - 6.

Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ 02 для второго столбца, он равен 7 при l = 2.

Следовательно, из базиса выводим второй вектор базиса А4.

Производим преобразование Жордана с элементом х 22 = 3, получаем третье опорное решение

Х3 = (0,7,10,0,63,0)

Б2 = (А3, А2, А5) (таблица 26.3).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Ответ : max Z(X) = 201 при Х = (0,7,10,0,63).

⇐ Предыдущая123456789Следующая ⇒

2. направления использования мат. моделей в экономике.

Математические модели позволяют определять оптимальные значения неизвестных параметров экономических систем, что является важным в процессе принятия решений. Математическое программирование как раз и дает аппарат, позволяющий оптимизировать процесс отбора лучших вариантов планов в процессе управления в экономических системах.

Используется в матстастике, оптимизационные методы, методы экономич. кибернетики, экспериментальные задачи.

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

2. математическое програмирование как наука, его структура. Задачи оптимизации. Трудности применения классических методов оптимизации при решении экономических задач.

Математическое программирование – это раздел прикладной математики, который разрабатывает теоретические основы и методы решения экстремальных задач.

К математическому программированию относятся ряд разделов, основные из которых следующие:

1. Линейное программирование. К данному разделу относятся задачи, в которых неизвестные переменные входят в математические соотношения в первой степени.

2. Нелинейное программирование. К данному разделу относятся задачи, в которых целевая функция и (или) ограничения могут быть нелинейными.

3. Динамическое программирование. К данному разделу относятся задачи, в которых процесс решения можно разбить на отдельные этапы.

4. Целочисленное программирование. К данному разделу относятся задачи, в которых неизвестные переменные могут принимать только целочисленные значения.

5. Стохастическое программирование. К данному разделу относятся задачи, в которых содержатся случайные величины в целевой функции или ограничениях.

6. Параметрическое программирование. К данному разделу относятся задачи, в которых коэффициенты при неизвестных переменных в целевой функции или ограничениях зависят от некоторых параметров.

Для решения задач математического программирования сложно использовать классические методы нахождения экстремума т. к. в задачах математического программирования целевая функция достигает своего экстремального значения на границе области допустимых значений неизвестных переменных, а производные в граничных точках не существуют. Полный перебор допустимых точек невозможен из-за значительного их количества.

3. Понятие математической модели, виды мат. моделей

Математическая модель – это записанная в математических символах и выражениях абстракция реального явления или процесса. Математические модели экономических процессов и явлений называются экономико-математическими моделями

Модели делятся на:

1. линейные , в которых все зависимости описываются линейными соотношениями,

2. нелинейные , в которых имеются нелинейные соотношения;

3. стохастические , в которых учитывается случайный характер изучаемых процессов,

4. детерминированные , в которых учитываются усредненные значения всех параметров.

5. динамические модели, в которых исследуемые системы рассматриваются в развитии в течение нескольких периодов,

6. статические , в которых фактор времени не учитывается.

7. оптимизационные модели, в которых выбор осуществляется в зависимости от экстремизации некоторого критерия,

8. неоптимизационные , в которых критерия оптимальности нет.

9. макромодели (всего хозяйства в целом)

10. микромодели (отдельных звеньев или процессов экономики).

Виды математических моделей: линейные, нелинейные, квадратические, целочисленные, дискретные, параметрические, дробно-линейные, динамические, стохастические

4. Общая постановка задач математического програмирования.

Рассмотрим общую постановку задачи математического программирования.

Общая задача математического программирования состоит в определении оптимального значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений. Математически определение оптимального решения выражается в нахождении экстремума (max или min) функции многих переменных

Z = f (x1, x2, …, xn)

в заданной области изменения этих переменных

gi (x1, x2,…, xn)Ribi (i = 1, 2,…, m),

где Ri - один из знаков ≥, =, ≤.

5. Задача об оптимизации плана выпуска продукции. Экономическая постановка и построение математической модели задач.

Экономическая постановка:

Предприятие производит n видов продукции с использованием m видов сырья. Для производства единицы продукции используется строго определённое количество сырья того или иного вида. Сырьё каждого вида на предприятии ограничено. Предприятие получает определённую прибыль от реализации единицы продукции. Необходимо найти такой план производства продукции, при котором предприятие получит максимальную общую прибыль.

Математическая постановка:

Пусть j – индекс вида продукции j = 1, n

i– индекс вида ресурсов i = 1, m

а ij – затраты сырья i -го вида на производство единицы продукции j -го вида;

Аi – заданное ограничение на имеющийся объём ресурсов i-го вида;

Рj – прибыль, получаемая от реализации единицы продукции j-го вида;

xj – объём выпускаемой продукции j-го вида.

z = Р1x 1 + Р2x 2 + … +Pnx n → max

а11x 1 + а12x 2 +…+ а1nx n ≤ A1

а21x 1 + а22x 2 +…+ а2nx n ≤ A2

…………………………….

a m1x1 + а m2x2 +…+ а m n x n ≤ Am

xj ≥ 0, j = 1, n

6. Задача о рационе. Экономическая постановка и построение математической модели задачи.

Экономическая постановка

В некотором фермерском хозяйстве производится откорм животных. Для откорма используется n видов кормов. Известно содержание питательных веществ (кальций, фосфор и др.) в единице корма каждого вида. Для полноценного питания животных необходимо потребление питательных веществ не меньше заданных количеств. Известна стоимость единицы каждого корма. Необходимо определить рацион кормления животных, при котором общие затраты на откорм будут минимальными.

Математическая постановка:

j – индекс вида кормов, j = 1, n

i – индекс вида питательных веществ, i = 1, m

Аi – необходимое суточное потребление питательного вещества i –го вида;

Сj – стоимость единицы кормов j-го вида.

Введём неизвестные переменные:

хj – суточный объём кормления животных j-м видом корма.

В терминах введённых обозначений данная задача запишется следующим

а11x1 + а12x2 +…+ а1nxn ≥ A1

а21x1 + а22x2 +…+ а2nxn ≥ A2

…………………………….

am1x1 + аm2x2 +…+ а mnxn ≥Am

xj ≥ 0, j = 1, n

7. Транспортная задача . Экономическая постановка и построение математической модели задачи.

Экономическая постановка :

Имеется m поставщиков однородной продукции и n потребителей этой продукции. Известны удельные затраты на доставку единицы продукции от каждого поставщика каждому потребителю. Запасы продукции у поставщиков ограничены. Известны так же потребности в продукции каждого потребителя.

Необходимо определить такой план перевозки продукции от поставщиков к потребителям, при котором общие затраты на перевозку будут минимальными.

Математическая постановка :

Введём обозначения заданных параметров:

j – индекс потребителей, j = 1, n

i – индекс поставщиков, i = 1, m

Аi – объём имеющейся продукции у i-го поставщика;

Вj – объём потребность в продукции j-го потребителя;

Cij – удельные затраты на перевозку единицы продукции от i-го поставщика j-му потребителю.

Введём неизвестные переменные:

хij – объём перевозки продукции от i-го поставщика j-му потребителю.

z = С11x11 + С12x12 +…+С1nx1n + С21x21 +…+ Сm(n -1)xm (n-1) + Сmnxmn → min

Ограничения задачи.

I. От каждого поставщика можно вывести продукцию не более имеющегося количества:

x11 + x12 +…+ x1n ≤ A1

x21 + x22 +…+ x2n ≤ A2 (2)

…………………….

xm1 + xm2 +…+ xmn ≤ Am

II. Потребность каждого потребителя в продукции должна быть удовле-

x11 + x21 +…+ xm1 ≥B1

x12 + x22 +…+ xm2 ≥B2

……………………. (3)

x1n + x2n +…+ xmn ≥Bn

III. Условие неотрицательности: xij ≥0, i = 1, m ; j = 1, n

Часто удобно записывать математическую постановку в свёрнутом виде:

, i = 1, m , j = 1, n

8. Задача о выборе назначениях или о назначениях. Экономическая постановка и построение математической модели задачи.

Экономическая постановка :

Имеются n видов работ и n исполнителей. Каждый из исполнителей может выполнить любую, но только одну работу. Задана себестоимость выполнения каждой работы, каждым исполнителем. Необходимо закрепить исполнителей за работой таким образом, чтобы общая стоимость выполнения работ была минимальной.

Математическая постановка .

Введём обозначения заданных параметров.

i – индекс работ, i = 1, m

j – индекс исполнителей, j = 1, n

Cij – себестоимость выполнения i-той работы j-тым исполнителем.

Введём неизвестные переменные. В данной задаче неизвестные переменные могут принимать только два значения 0 или 1. Такие переменные называются нулевыми.

1 - если за i-той работой закреплён j-тый исполнитель;

0 - в противном случае.

В терминах введённых обозначений данная задача запишется следующим образом:

z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n -1)x(n-1)(n-1) + Сnnxnn → min

I группа ограничений.

За каждой работой должен быть закреплён только один исполнитель:

x11 + x12 +…+ x1n = 1

x21 + x22 +…+ x2n = 1

……………………..

xn1 + xn2 +…+ xnn = 1

II. группа ограничений.

Каждый исполнитель может выполнить только одну работу:

x11 + x21 +…+ xn1 = 1

x12 + x22 +…+ xn2 = 1

……………………..

x1n + x2n +…+ xnn = 1

x ij = { 0,1} i = 1, n ; j = 1, n

9. Задача о раскрое материалов. Экономическая постановка и построение математической модели задачи.

Экономическая постановка .

На раскрой поступает исходный материал одинакового размера. Его требуется раскроить на заготовки заданного размера в заданном количестве, таким образом, чтобы общие отходы были минимальными.

Математическая постановка .

Введём обозначения:

i – индекс заготовок,

Аi – необходимое количество заготовок i-того типа;

j – индекс вариантов раскроя,

Сj –размер отходов при раскрое единицы исходного материала по варианту j;

а ij – количество заготовок i-того вида при раскрое единицы исходного материала по варианту j.

Введём обозначения неизвестных переменных.

хj- количество исходного материала раскроенного по варианту j.

В терминах введённых обозначений данная задача запишется следующим образом:

z = С1x1 + С2x2 + … +Сnxn → min

а11x1 + а12x2 +…+ а1nxn = A1

а21x1 + а22x2 +…+ а2nxn = A2

…………………………….

am1x1 + аm2x2 +…+ аmnxn =Am

xj ≥ 0, j = 1, n

Применение математических моделей позволяет экономить исходные материалы до 20 %.

Математическая модель раскроя строится в два этапа.

На первом этапе производится построение вариантов раскроя, в результате которого определяются значения количества вариантов n, количества заготовок каждого вида, получаемых при различных вариантах раскроя (аij), а так же значения отходов (Сj).

Построение вариантов раскроя единицы исходного материала осуществляется в виде следующей таблицы:

№ варианта

Заготовка i1

Заготовка i2

Заготовка im

Заготовки располагаются в порядке невозрастания их размеров. Построение вариантов осуществляется методом полного перебора.

10. Общая форма модели задач ЛП и ее особенности

Общая форма ЗЛП имеет вид:

z = С1x1 + … + Сnxn max (min)

а11 X1 + a12 X2 + … + а1n Xn R1 a1

а21 X1 + a22 X2 + … + а2n Xn R2 a2

………………………………………………….

am1 X1 + аm2 X2 +…+ аmnxn Rm am

хj ≥ 0, j = 1, k, k ≤ n

В общей форме каждый символ R1 , R2 ,…, Rm означает один из знаков: ≥, = или ≤ .

Общая форма модели задачи ЛП обладает следующими особенностями.

1. Система ограничений представлена в виде уравнений (жестких условий) и неравенств (нежестких условий).

2. Условия неотрицательности накладываются не на все переменные

3. Целевая функция стремится либо к максимуму, либо к минимуму.

11. Стандартная форма модели задач ЛП и ее особенности

Стандартная форма имеет следующий вид.

Найти максимум или минимум целевой функции z:

z = С1x1 + … + Сnxn → max (min) (1)

При выполнении следующих ограничений:

а11 Х1 + а12 Х2 + … + а1n Хn ≤ а1

а21 Х1 + а22 Х2 + … + а2n Хn ≤ а2

…………………………………………..

am1 Х1 + аm2 Х2 +… + аmn Хn ≥ аm

хj ≥ 0, j = 1, k, k ≤ n

Особенности стандартной формы модели задачи ЛП следующие:

1. система ограничений представлена в виде неравенств (нежестких условий)

2. условия неотрицательности накладываются на все переменные

3. целевая функция стремится либо к max, либо к min

12. Каноническая форма модели задач ЛП и ее особенности

Каноническая форма имеет вид:

Найти минимум целевой функции z:

z = С1x1 + … + Сnxn → min

При выполнении следующих ограничений:

а11 Х1 + а12 Х2 + … + а1n Хn = а1

а21 Х1 + а22 Х2 + … + а2nxn = а2

…………………………

am1x1 + аm2 X2 +… + аmn Xn = am

Xj ≥0, j = 1, n

Особенности канонической формы следующие:

1. Система ограничений представлена в виде уравнений (жестких условий).

2. Условия неотрицательности накладываются на все переменные

3. Целевая функция стремится к

В некоторых источниках целевая функция задачи ЛП, представленной в канонической форме, стремится к максимуму. Это делается для удобства решения задачи по алгоритму, разработанному на максимум целевой функции.

13. Возможный, допустимый, оптимальный опорный план задачи, ОДЗ задачи ЛП

Определение 1. Значения неизвестных переменных, удовлетворяющие всем ограничениям задачи линейного программирования, называются допустимыми значениями переменных или планами .

Определение 2. Множество всех планов задачи линейного программирования называется областью допустимых значений переменных (ОДЗ ).

Определение 3. План задачи линейного программирования, при котором целевая функция принимает минимальное (или максимальное) значение на ОДЗ называется оптимальным .

14. Виды записей задач ЛП: развернутая, свернутая, матричная, векторная.

Модели задач ЛП могут быть записаны в различных видах.

1. Развернутый вид записи модели

Z = c1 X1 + c2 X2 + … + cn Xn → min

a11 X1 + a12 X2 + … + a1n Xn = a1,

a21 X1 + a22 X2 + … + a2n Xn = a2,

……………………………………………

a m1 X1 + am2 X2 + … + amn Xn = am,

Xj ≥ 0, j = 1, n.

2. Свернутый вид:

Xj ≥ 0, j = 1, n.

3. Модель задачи ЛП в матричном виде:

X ≥ 0

Где

а11 а12 … а1n X1 a1

A= a21 a22 … a2n , X= X2 , A0 = a2

… … … … … …

am1 am2 … amn X3 am

4. Модель задачи ЛП в векторном виде:

Где

Х1 a11 a12 a1n a1

Х2 , a21 , a22 , a2n , a2

… … … … …

Хn am1 am2 am2 am

15. Переход от стандартной и общей формы задач ЛП к канонической. Теорема связи

Для перехода от общей или стандартной формы к канонической используют следующие приёмы.

1. Преобразование переменных . Если какая-то переменная Xk неположительна (Xk ≤ 0), то вводят новую переменную Xk ", так что Xk " = –Xk . Очевидно, что Xk " ≥ 0. После этого в каждом ограничении и целевой функции переменную Xk заменяют на [ – Xk "].

Если какая-то переменная Хt может принимать любые значения, то её заменяют разностью двух неотрицательных переменных Хt’ и Хt’’, т. е. полагают, что хt = Хt’ – Хt’’, где Хt’ 0 ≥ и Хt’’ ≥ 0.

2. Преобразование ограничений. Если какое–либо из ограничений в модели имеет вид неравенства, то оно преобразуется в равенство прибавлением (если неравенство имеет тип ≤) или вычитанием (если неравенство имеет тип ≥) из его левой части. Эти переменные называют балансовыми. Балансовые переменные входят в целевую функцию с коэффициентами нуль. Балансовая переменная принимает значение индекса последовательно после уже имеющихся. Если, например, система ограничений имеет 5 переменных, то первая балансовая переменная будет Х6, а вторая – Х7 и т.д.

16. Переход от канонической формы модели ЗЛП к стандартной

Для перехода от канонической формы к стандартной можно каждое из

уравнений заменить системой неравенств:

Другой способ состоит в приведении системы уравнений к специальному виду и дальнейшему исключению некоторых переменных.

С помощью метода Жордана-Гаусса выделяем в каждом уравнении базисную переменную. Такое выделение осуществляется с помощью эквивалентных (элементарных) гаусовских преобразований. К ним относятся:

а) умножение любого уравнения на константу отличную от нуля;

б) прибавление к любому уравнению любого другого уравнения, умноженного на любую константу.

Исходную систему линейных уравнений перед преобразованием удобно записывать в виде матрицы или таблицы:

Записываем задачу в стандартной форме.

17. Понятие гиперплоскости полуплоскости, опорная гиперплоскость.

18. Геометрич. интерпретация системы ограничений и целевой функции в задачи ЛП

19. Выпуклое множество: крайние (угловые) точки множества. Выпуклый многогранник

Определение Множество М называется выпуклым, если вместе с любыми двумя точками, принадлежащими данному множеству, оно содержит и отрезок их соединяющий.

Выпуклое множество

Определение Точка х множества М называется угловой или крайней, если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.

Теорема 1. Любую точку отрезка можно представить в виде выпуклой комбинации его угловых точек.

х = λ 1 А + λ 2 В

λ 1 , λ 2 ≥ 0 выпуклая комбинация точек угловых точек А и В

λ 1 + λ 2 = 1

Теорема 2. Любую точку выпуклого замкнутого множества можно представить в виде выпуклой комбинации его угловых точек.

20. алгоритм графического метода решения задач ЛП

1. Проверяется, находится ли исходная ЗЛП в стандартной форме, если нет, то задачу необходимо преобразовать к стандартной форме.

2. Проверяется количество неизвестных переменных. Если это количество больше трёх, то задача не может быть решена графическим методом (существуют другие эффективные методы решения таких задач).

3. Строится область допустимых значений переменных для ЗЛП.

4. Строится направляющий вектор c .

5. Через ОДЗ проводится исходная изоцель (перпендикулярно направляющему вектору).

6. Проводится мысленное перемещение исходной изоцели в направлении вектора c , если определяется максимальное значение целевой функции, или в противоположном направлении, если определяется её минимальное значение, до тех пор, пока изоцель не станет опорной к ОДЗ. Точки пересечения опорной изоцели и ОДЗ и будут оптимальными точками задачи.

7. Для того, чтобы определить координаты оптимальной точки, необходимо решить систему соответствующих линейных уравнений.

8. Для нахождения оптимального значения целевой функции необходимо оптимальные значения переменных подставить в целевую функцию и вычислить её значение.

20. алгоритм графич. метода решения задач ЛП

Алгоритм графического метода.

1. Последовательным построением каждого из условий системы ограничений задачи осуществляется построение ОДЗ.

2. Строится направляющий вектор С по коэффициентам при переменных целевой функции.

3. Перпендикулярно направляющему вектору через начало координат проводится исходная изоцель.

4. Проводится мысленное перемещение исходной изоцели в направлении возрастания значений вектора С, если определяется максимальное значение целевой функции или в противоположном направлении, если определяется ее минимальное значение, до тех пор, пока изоцель не станет опорной к ОДЗ. Точки пересечения опорной изоцели и ОДЗ будут оптимальными точками задачи.

5. Для определения координат оптимальной точки необходимо решить систему соответствующих линейных уравнений тех условий, на пересечении которых находится оптимальная точка.

6. Для нахождения оптимального значения целевой функции, необходимо координаты оптимальной точки подставить в целевую функцию и вычислиь ее значение.

23. теоремы об области допустимых значений задачи ЛП и о целевой ф-ции

Теорема об ОДЗ. Область допустимых решений задачи ЛП выпуклое множество (замкнутое и ограниченное в n-мерном пространстве)

Теорема 2. О целевой функции задачи линейного программирования.

Целевая функция ЗЛП принимает своё оптимальное значение в одной из угловых точек области допустимых значений переменных. Если целевая функция принимает своё оптимальное значение в нескольких угловых точках, то такое же значение она принимает и в любой точке, являющейся выпуклой комбинацией данных угловых точек.

24. Теорема об угловой точке. Достаточное и необходимое условие

25. Следствия из теоремы о свойствах решений задач ЛП и выводы. Понятие опорного плана.

Следствия из теорем.

Определение. План = (х1,х2,…,хn), положительным координатам которого соответствуют линейно независимые векторы, называется опорным планом ЗЛП .

Следствие1. Опорный план имеет не более m положительных координат.

Если он имеет ровно m положительных координат, то такой опорный план называется невырожденным, в противном случае вырожденным.

Следствие 2. Каждая угловая точка ОДЗ является опорным планом.

27. Алгоритм симплексного метода.

При решении задач ЛП симплексным методом необходимо выполнить следующую последовательность действий.

1. Проверяется, находится ли задача ЛП в канонической форме. Если нет, то необходимо исходную модель преобразовать в каноническую форму.

2. Выделяется начальный опорный план и значение целевой функции при этом опорном плане.

3. Проводится построение исходной симплексной таблицы.

4. Проверяются значения оценок оптимальности в индексной строке. Если нет положительных оценок, то выписывается оптимальное решение и алгоритм заканчивает свою работу. В противном случае выполняется пункт 5.

5. В базисе вводится вектор, которому соответствует наибольшая положительная оценка. Данный столбец называется разрешающим.

6. Из базиса выводится вектор, которому соответствует симплексное отношение, рассчитанное по формуле 0 < Ө ≤ . Данная строка называется разрешающей строкой.

7. Строится новая симплексная таблица. Соответствующим образом изменяются столбцы Б и С Б. остальная часть таблицы заполняется из предыдущей с помощью гауссовских преобразований, причем индексная строка считается m+1 строкой и также преобразуется с помощью гауссовских преобразований. Переходим к выполнению пункта 4 данного алгоритма.

После построения каждой таблицы можно проверить правильность вычислений с использованием формул вычисления оценок, приведенных в предыдущем параграфе.

28. выбор базиса и построение начального опорного плана при решении задач симплекс методом.

29. Симплекс-таблицы, их заполнение. Формулы расчета коэффициентов индексной строки.

30 . Теорема оптимальности плана задачи линейного программирования следствие из теоремы оценки оптимальности при решении задач симплекс методом.

Теорема 1: Если для некоторого вектора Ā j в системе

Х 1 + а 1 m +1 X m +1 + а 1 m +2 X m +2 + … + а 1 n X n = a 1

Х 2 + а 2 m +1 X m +1 + а 2 m +2 X m +2 + … + а 2 n X n = a 2

…………………………………………………..

X m + а mn +1 X m +1 + а mn +2 X m +2 + … + а mn X n = a m

Выполняется соотношение Z j – c j > 0, то план Х Б0 не является оптимальным и можно перейти к плану Х Б1 такому, что Z (Х Б1) ≤ Z (Х Б0).

Здесь Z j = (С, Ā j) – скалярное произведение векторов.

С – вектор, состоящий из коэффициентов при базисных переменных целевой функции Z

Ā j – вектор, состоящий из коэффициентов разложения соответствующего вектора по векторам базиса.

c j – коэффициент целевой функции Z при переменной Х j

Следствие из теоремы : Если для всех векторов Ā 1 , Ā 2 , …, Ā n некоторого опорного плана Х выполняется соотношение Z j – c j < 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.

Таким образом теорема и следствие позволяют установить, является ли очередной опорный план оптимальным и, если не является, то необходимо перейти к другому опорному плану, при котором значение целевой функции будет меньше.

Замечание . В теореме и следствии предполагается, что задача находится в канонической форме с целевой функцией на минимум. Однако симплекс-методом моно решать и задачи с целевой функцией на максимум. В этом случае при анализе значений оценок используется их противоположный смысл, то есть план будет оптимальным, если все оценки оптимальности будут не отрицательными (положительным или отрицательным).

31. Выбор вектора, вводящегося в базис и выводящегося из базиса. Симплексное отношение.

Для перехода к новому опорному плану необходимо один из свободных векторов ввести в базис, а какой-то из базисных векторов вывести. Для введения в базис выберем вектор, имеющий хотя бы одну положительную координату. Пусть таким вектором будет вектор А m+1 .

Разложению –

Соотв. вектор, кот. будет являться опорным планом, если его координаты будут неотрицательными, а кол-во положительных координат будет равняться m.

Координаты вектора Х1 должны быть неотрицательными, т.е. .

Если , то эта координата будет неотрицательной.

Пусть минимум в соотношении (5) был получен при i =1, тогда если взять

то первая координата вектора 1 х станет равной нулю.

Соотношение (6) называется симплексным отношением . Таким образом, мы перешли от исходного опорного плана 0 х (базисные векторы А1,А2,…Аm) к опорному плану 1 х (базисные векторы А2,А3,…,Аm,Am+1).

32. разрешающий элемент таблицы, его выбор. Правило полных жордановых исключений для перерасчета симплекс таблицы.

33. Правило «четырехугольника» для перерасчета симплекс-таблицы

34. Признак единственности оптимального плана, множества оптимальных планов и отсутствия оптимального плана при решении задача ЛП симплекс-методом.

При решении задач симплекс-методом возможны следующие виды оптимальных решений:

1. Единственность . Если оценки всех свободных векторов строго отрицательные, то полученный опорный план является оптимальным и единственным. (см. пример в предыдущем параграфе).

2. Альтернативный оптимум (множество оптимальных решений).

Если среди неположительных оценок свободных векторов имеется хотя бы одна нулевая, то полученный опорный план будет оптимальным, но не единственным. В этом случае можно перейти к другим опорным планам (вводятся в базис векторы, которым соответствуют нулевые оценки) и, затем, общее оптимальное решение записать в виде выпуклой комбинации полученных оптимальных опорных планов.

3. ЗЛП не имеет оптимального решения, так как целевая функция не ограничена снизу . Если в симплекс таблице имеется положительная оценка, а все элементы данного столбца отрицательны и нулевые, то данный вектор можно ввести в базис. Однако никакой из базисных векторов нельзя вывести из базиса. Из этого следует, что дальнейшее уменьшение целевой функции возможно при переходе к неопорному плану.

4. ЗЛП не имеет оптимального решения, так как система ограничений противоречива. Поскольку при решении ЗЛП обычным симплекс-методом должен быть исходный опорный план, то система линейных уравнений заведомо не противоречива. Следовательно, такой случай не может встретиться при решении обычным симплекс методом.

5. Если ОДЗ состоит из одной точки, то решение такой задачи является тривиальным, и может быть получено без использования симплекс-метода.

35. В каких случая применяется метод искусственного базиса

искусственной.

36. Построение М-задачи в методе искусственного базиса

Если задача линейного программирования находится в канонической форме, однако, не во всех уравнениях присутствуют базисные переменные, т. е. исходный опорный план отсутствует. В этом случае в те уравнения, в которых нет базисных переменных, необходимо добавить с коэффициентом +1 некоторую неотрицательную переменную. Такая переменная называется искусственной.

Искусственную переменную необходимо добавить в целевую функцию с очень большим положительным числом (так как целевая функция на нахождения минимума). Это число обозначается латинской буквой M. Его можно считать равным +∞. В связи с этим иногда метод искусственного базиса называют М- методом. Такое преобразование исходной задачи называется построением расширенной задачи. Если решается задача с целевой функцией на нахождение искусственную переменную необходимо добавить в целевую функцию с очень большим положительным числом (так как целевая функция на нахождения минимума). Это число обозначается латинской буквой M. Его можно считать равным +∞. В связи с этим иногда метод искусственного базиса называют М- методом. Такое преобразование исходной задачи называется построением расширенной задачи. Если решается задача с целевой функцией на нахождение максимума, то искусственные переменные входят в целевую функцию с коэффициентом –М.

Таким образом, в расширенной задаче мы имеем опорный план (хотя некоторые из базисных переменных и являются искусственными).

Строится исходная симплекс таблица.

37. построение индексной строки в методе искусственного базиса

Строится исходная симплекс таблица, в которой индексная строка разбивается на две строки, поскольку оценки состоят из двух слагаемых. В верхней строке записывается слагаемое оценки без M, в нижней строке – коэффициенты при М. Знак оценки определяется знаком коэффициента при M, независимо от величины и знака слагаемого без M, так как M очень большое положительное число.

Таким образом, для определения вектора, который вводится в базис необходимо провести анализ нижней индексной строки. Если выводится из базиса искусственный вектор, то соответствующий столбец в последующих симплексных таблицах можно не вычислять, если нет необходимости в получении решения двойственной задачи (см. следующую тему).

После того, как все искусственные векторы будут выведены из базиса, нижняя строка будет иметь все нулевые элементы, за исключением оценок, соответствующих искусственным векторам. Они будут равны –1. Такую строку можно удалить из рассмотрения и дальнейшее решение проводить обычным симплекс-методом, если нет необходимости в получении решения двойственной задачи (см. следующую тему).

38. Критерий оптимальности в методе искусственного базиса. Признак построение начального опорного плана исходной задачи.

39. Алгоритм двойственного симплекс-метода

Алгоритм двойственного симплекс-метода:

1. обычным способом заполняют первую симплекс-таблицу не обращая внимания на знаки свободных членов. Считается, что такая задача должна иметь исходный единичный базис.

2. Выбирают направляющую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов А0

3. Выбирают направляющий столбец по наименьшему по абсолютной величине отношению элементов индексной строки к отрицательным элементам направляющей строки.

4. Пересчитывают симплексную таблицу по правилу полных жордановых исключений

5. проверяют полученный план на допустимость. Признаком получения допустимого опорного плана является отсутствие в столбце А0 отрицательных элементов. Если в столбце А0 имеются отрицательные элементы то переходят ко второму пункту. Если же их нет, то переходят к решению полученной задачи обычным способом.

6. признаком получения оптимального решения двойственным симплекс-методом является критерий оптимальности обычного симплекс-метода.

41. Открытые и закрытые транспортные модели. Переход от открытой транспортной модели к закрытой.

Типы транспортных задач.

Имеются m поставщиков однородной продукции с известными запасами продукции и n потребителей этой продукции с заданными объёмами потребностей. Известны так же удельные затраты на перевозку.

Если сумма объёмов запасов продукции равна объёму потребностей всех потребителей, то такая задача называется закрытой транспортной задачей

(т. е. если ∑ Ai = ∑ Bj), в противном случае транспортная задача называется открытой . Для решения транспортной задачи необходимо, чтобы она была закрытой.

Открытую транспортную задачу можно преобразовать к закрытой следующим образом.

Пусть ∑Ai > ∑Bj. В этом случае необходимо ввести фиктивного n+1 потребителя с объёмом потребностей ∑Ai – ∑Bj Удельные затраты на перевозку от поставщиков к фиктивному потребителю полагаются равными 0, так как на самом деле такие перевозки осуществляться не будут и некоторая часть продукции останется у поставщиков.

Если ∑Bj > ∑Ai . В этом случае необходимо ввести фиктивного m+1 поставщика с объёмом запасов∑Bj – ∑Ai . Удельные затраты на перевозку от фиктивного поставщика к потребителям полагаются равными 0, так как на самом деле такие перевозки осуществляться не будут и некоторую часть продукции потребители недополучат.

42. Способы построения первоначального распределения в транспортной задаче: метод северо-западного угла и метод наименьшего элемента в матрице.

Северо-западный прием построения опорного плана. Согласно этому приему формирование величин перевозок начинается с с.-з. уголка таблицы, т.е. с клетки x11. По этому приему прежде всего распределяется товар первого поставщика. Причем первый поставщик сначала предельно возможно удовлетворяет первого потребителя. Затем, если у поставщика товар еще остался,

Метод наименьшего элемента в матрице.

Сущность метода заключается в том, что максимально возможная поставка всегда проставляется в клетку, которой соответствует наименьший тариф матрицы.

Сначала делаем пометки (например, знаком ▼) в тех клетках строк, в которых наблюдается самая меньшая цена по строке. Затем обходим таблицу по столбикам и делаем такие же пометки в клетках, в которых самая маленькая цена по столбикам.

Дальнейшее распределение делается сначала предельно возможно по клеткам с двумя отметками, потом - с одной, а затем делается добалансировка задачи до (m + n – 1) заполнений. Заполнения организуем при прохождении таблицы слева направо и сверху вниз.

43. Свойства транспортных задач

Транспортная задача обладает некоторыми свойствами, которые можно отразить следующими теоремами.

Теорема 1. Закрытая транспортная задача всегда имеет решение.

Теорема 2. Если объёмы запасов продукции и объёмы потребностей является целыми числами, то и решение транспортной задачи также будет целочисленным.

Теорема 3. система ограничений закрытой транспортной задачи всегда линейно-зависима.

Из этой теоремы следует, что распределение закрытой транспортной задачи всегда имеет m + n – 1 базисную переменную и (m – 1) (n – 1) свободные временные.

44. Вырожденное распределение в транспортных задачах, избавление от вырожденности. Вычеркиваемая комбинация.

Распределение называется вырожденным, если количество клеток меньше чем m + n – 1.

45. Теорем оптимальности транспортной задачи.

Теорема. Если для некоторого распределения транспортной задачи вы-

полняются условия:

а). ui+vj = сij для занятых клеток

б) ui+vj ≤ сij, для свободных клеток,

то данное распределение является оптимальным.

Величины ui называют потенциалами строк, а величины vj называют потенциалами столбцов.

46. Потенциалы и способы их расчета.

Для нахождения потенциалов строк и столбцов пользуются следующими рассуждениями, исходя из условия а) теоремы оптимальности.

Количество уравнений исходя из этого условия равняется m + n – 1, а количество неизвестных ui и vj равняется m + n. Т.о. количество переменных больше количества уравнений, причем все уравнения линейно независимы. Решение такой системы линейных уравнений является неопределенным, поэтому одному из потенциалов нужно присвоить любое значение. На практике ui = 0. получается система из m + n – 1 уравнений с m + n – 1 неизвестными переменными. Эту систему можно решить любым методом. На практике для расчета потенциалов рассматриваются занятые клетки, для которых один их потенциалов известен, и исходя из условия а) теоремы вычисляются значения остальных неизвестных потенциалов.

47. расчет оценок оптимальности распределения транспортных задач и критерий оптимальности.

Исходя из соотношения б) теоремы можно записать следующую формулу для вычисления оценок: δ ij = ui +vj – сij. Для того, чтобы оценки не перепутать с объёмами перевозок, они (оценки) заключаются в круги.

Оценки оптимальности в свободных клетках ТЗ представляют собой критерий оптимальности, с помощью которого осуществляется проверка распределения на оптимальность. Если оценки всех свободных клеток меньше или равны нулю, то данное распределение является оптимальным.

48. перераспределение поставок в транспортной задаче

Если распределение не является оптимальным, то необходимо осуществить перераспределение поставок.

Для перераспределения осуществляют построение цикла пересчета. В качестве клетки выбирается клетка с наибольшей положительной оценкой. Эта клетка помечается знаком «+», то есть в неё необходимо записать некоторый объём поставки. Но тогда нарушится баланс по данному столбцу, следовательно, одну из занятых клеток данного столбца необходимо пометить знаком «-», то есть уменьшить объём поставки на такую же величину. Но тогда изменится баланс по данной строке, следовательно, какую-то занятую клетку данной строки необходимо пометить знаком «+». Данный процесс продолжается до тех пор, пока не поставлен знак «-» в строке, где находилась исходная клетка.

Для любой свободной клетки существует цикл пересчета и притом единственный.

49. цепочки перераспределения, их виды.

Пусть рассматриваемый план перевозок не оптимальный, т.е. имеются положительные относительные оценки. Тогда берется неблагоприятная клетка (одна из неблагоприятных) и для нее строится цикл пересчета, согласно которому потом делается перераспределение намеченных перевозок. Цикл строится в виде ломаной замкнутой линии, отрезки которой идут либо вдоль столбика, либо вдоль строки. В одном из углов ломаной претендующая на товар неблагоприятная клетка, а в остальных углах клетки заполненные, т.е. при построении цикла мы исходим из претендующей клетки и возвращаемся в нее по ломаной, но повороты мы можем делать только в клетках заполненных (соответствующих базисным переменным). Пусть неблагоприятная клетка претендует на товар Q. Чтобы не произошел разбаланс в таблице, надо в переходах по циклу по очереди

прибавлять и отнимать Q к имеющимся перевозкам. Так как углов чётное количество, в половине клеток Q прибавится, а в другой половине - отнимется. Обход цикла начинают по часовой стрелке или против с претендующей клетки, помещая туда товар Q, затем из соседней клетки вычитают Q, затем прибавляют и т.д. Сама величина Q выбирается так, чтобы одна из клеток опустошалась, но ни одна из поставок не стала бы отрицательной.

Для этого Q надо выбрать равным наименьшему уменьшаемому из клеток, в которых Q вычитается. На следующих рис. 7.1 и 7.2 покажем примеры циклов и правило вычисления.

При этом опустошаются две клетки. Но надо, чтобы взаимно пустой стала лишь одна клетка. Поступают так: одну из опустошающихся клеток делают пустой в новой таблице, а в другой опустошающейся клетке ставят нуль. Эта клетка считается в новой таблице базисной (заполненной).

50. Выбор объема перераспределения.

Определение объёма перемещаемой продукции. При определении объёма продукции, перемещаемого по циклу пересчёта, мы должны исходить из следующих двух соображений:

а) после преобразования в клетках таблицы не должны получиться отрицательные числа;

б) одна из занятых клеток должна стать свободной.

Для того, чтобы эти условия выполнялись, необходимо объём перемещаемой продукции выбрать следующим: θ=min {хij} -, где {хij} – объёмы перевозок из клеток цикла пересчёта, помеченных знаком «-».

θ = min{20;30}=20

К значениям клеток, помеченных знаком «+»прибавляется θ. От значений клеток, помеченных знаком «-», вычитается θ. Значение поставок остальных клеток переписывается без изменений. В результате получим следующую таблицу.

53. Алгоритм метода потенциалов.

Алгоритм:

1. Проверить, выполняется ли для задачи рав-во если нет, то в задачу вводится фиктивный поставщик или потребитель

2. Условие задачи записывается в форме транспорт.таблицы

3. Строится начальный опорный план

4. Определяются потенциалы пост-ков и потреб-лей

5. Вычисляются оценки свободных клеток. Если все они не отрицательные – план оптимальный и нужно выписать ответ. Матрицу перевозок Х и определить величину затрат на транспортировку. Если план не явл-ся оптимальным, т.е.среди оценок есть отриц-ые, то выбир-т перспективную клетку с наибольшей по величине отриц. оценкой и переходят по величине к след.

6. Загруж-т перспективную клетку. Оформл-т нов.опорн.план в виде трансп.таблицы. Переходят к пункту 4.

54. Учет затрат на производство и транспортировку продукции. Транспортная задача с запретами на поставки.

При решении некоторых задач необходимо учитывать затраты не только на перевозку груза, но и на производство перевозимой продукции. Для этого в матрице трансп. задачи

Где Cij ‘ – приведенные затрат на производство одной единицы продукции.

Cij “– затраты на транспортировку одной единицы продукции.

Задачи с запретами на поставки.

В некоторых ситуациях нельзя перевозить продукцию по какому-либо маршруту.

Для этого в матрице транспортной задачи перевозка через которую является запретной проставляется запрещающий тариф М. дальше задача решается обычным способом., однако этой клетке всегда будет соответствовать отрицательная оценка клетки.

55. учет ограничений по пропускной способности маршрутов, учет обязательности некоторых поставок в транспортной задаче.

учет ограничений по пропускной способности маршрутов.

В некоторых транспортных задачах по некоторым маршрутам устанавливают меньшую пропускную способность чем необходимо для удовлетворения спроса пункта потребления.

учет обязательности некоторых поставок в транспортной задаче.

В некоторых случаях в задаче требуется, что например по маршруту Ak Bs должно обязательно осуществиться поставка в объема А ед. В этом случае из объема производства пункта А и объем S Bs вчитается обязательная поставка и задача решается относительно необязательности поставок. После получения оптимального решения обязательно поставка добавляется к объему стоящему в клетке Ak Bs.

56. Возможные выводы при экономич. интерпретации оптимального распределения для открытых транспортных задач.

При получении оптимального распределения необходимо вернуться к исходной задаче и сделать соответствующие экономич. выводы. Они следующие:

1. если введен пункт потребления, то это означает, что в анализируемоой системе излишни объемы производства, и можно без ущерба для рассматриваемой системы уменьшить мощности тех пунктов производства на величину привязки, которые привязались к фиктивному пункту потребления.

2. если же введен фиктивный пункт производства, то это означает, что мощностей реальных пунктов производства не хватает и их необходимо увеличить. Увеличиваются мощности тех пунктов производства, которые ближе всего расположены к пунктам потребления, привязанным к фиктивному пункту производства. Производится увеличение мощности производителя на величину привязки. Для этого рассматривают столбец пункта потребления, который привязан к фиктивному пункту производства, и находят в нем наименьший тариф. Мощность соответствующего этому тарифу пункта производства наиболее эффективно увеличить на величину привязки.

57.Понятие двойственности. Экономическая постановка двойственных задач на примере задачи об оптимизации плана выпуска продукции.

Двойственная задача - это вспомогательная задача линейного программирования, формулируемая с помощью определенных правил непосредственно из условий исходной, или прямой задачи.

Пусть имеется зада об оптимизации плана выпуска продукции. Она имеет следующий вид:

Исходная задача:

а 11 х 1 +а 12 х 2 +…+ а 1п х п ≤в 1 | у 1

а 21 х 1 +а 22 х 2 +…+ а 2п х п ≤в 2 | у 2

……………….. |.. (1)

а т 1 х 1 +а т 2 х 2 +…+ а т п х п ≤в 1 | у т

x j ≥0, j = 1,n(2)

z = c 1 x 1 +c 2 x 2 +…+c n x n ->max(3)

X = (x 1, x 2 ,…, x n)

a ij – кол-во сырья i- го вида, затраченного для выпуска j-го вида продукции

Двойственная задача

Пусть предприятие по какой-либо причине не может выпускать продукцию. Для того, чтобы уменьшить затраты простоя, предприятие может реализовать сырье, которое у него имеется. По каким ценам нужно реализовать сырье?

у i - цена i- го вида сырья имеющегося на предприятии.

а 11 у 1 +а 21 у 2 +…+ а т 1 у т ≥с 1

а 12 х 1 +а 22 у 2 +…+ а т 2 х п ≥с 2

……………….. (1’)

а 1п у 1 +а 2п у 2 +…+ а тп у т ≥с п

у i ≥0, j = 1,m(2’)

F = b 1 y 1 +b 2 y 2 +…+b m y m ->min(3’)

58. Соответствие между структурными элементами прямой и двойственной задачи

Каждой задаче линейного программирования можно сопоставить

двойственную задачу по следующим правилам:

1. Во всех ограничениях исходной задачи свободные члены должны

находиться справа, а члены с неизвестными - слева.

2. Ограничения-неравенства исходной задачи должны иметь знаки,

направленные в одну строну.

3. Если целевая функция в исходной задаче минимизируется, ограничения-неравенства следует записать со знаком «≤» , тогда в двойственной задаче целевая функция будет минимизироваться и знаки ограничений-неравенств будут «≥».

4. Каждому ограничению исходной задачи соответствует переменная в

двойственной задаче. Если переменная соответствует неравенству, она неотрицательна, если равенству – то переменная без ограничений на знак («произвольная»).

5. Коэффициенты при переменных в ограничениях двойственной задачи получаются транспонированием матрицы, составленной из

коэффициентов при переменных исходной задачи.

6. Свободные члены исходной задачи являются коэффициентами при

переменных в функции цели двойственной задачи, а свободными

членами в двойственной задаче – коэффициенты при переменных в

функции исходной задачи.Отметим также, что соотношение двойственности взаимное, т.е. задача, двойственная по отношению к двойственной, совпадает с исходной.Двойственные пары задач подразделяются на симметричные и несимметричные. В симметричной паре ограничения прямой и двойственной задач являются нестрогими неравенствами и, следовательно, переменные обеих задач могут принимать только неотрицательные значения.

59. Построение двойственных задач к исходным задачам, записанным в стандартной, канонической и общей форме модели(построение симметричных и несимметричных двойств. задач)

Стандартная форма (исходная)

Σ a ij x j ≤ b i , i=1,n(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->max(3)

Двойственная стандартная

Σ a ij y i ≤ c j , j=1,n(1)

y i ≥0, j=1,m(2)

F = Σ b i y i ->min(3)

Исходная задача в канонической форме:

Σ a ij x j = b i , i=1,m(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->min(3)

Двойственная каноническая

Σ a ij y i ≤ c j , j=1,n(1)

y i - любые (2)

F = Σ b i y i ->max(3)

Дадим экономическую интерпретацию пары двойственных задач. Рассмотрим задачу рационального использования ресурсов. Пусть предприятие располагает ресурсами b1,b2,…bm, которые могут использ-ся для выпуска n-видов продукции. Пусть также известны стоимость единицы j-вида продукции cj (j=1,n) и норма потребления i-го ресурса (i=1,m) на производство единицы j-й продукции – aij.Требуется определить объем производства продукции каждого вида xj (j=1,n), максимизирующий суммарную стоимость

f= c1x1+…+cnxn (1)

При этом расход ресурсов не должен превышать их наличия:

a11x1+…+a1nxn<=b1 }

…………………….. } (2)

am1x1+…+amnxn<=bm }

Все известные по своему экономическому смыслу неотрицательны:

Xj>=0 (j=1,n). (3)

Заметим, что это задача образуют симитричную двойственную задачу.

Несимметричные двойственные задачи.

Возьмем ЗЛП на максимум в канонической форме:

Max Z=(n;j=1)Σcj*xj

(n;j=1)Σaij*xj=bi (i=1,m)

Xj>=0 (j=1,n).

60.Основная и вторая теорема двойственности (сформулировать теоремы и разъяснить)

Первая теорема двойственности.

Теорема: если одна из двойственных задач имеет оптимальный план, то и другая решима, т.е. имеет опт.план. При этом экстремальные значен.целевых функций совпадают (j=от 1 до n) Σcjxj*= (i=от 1 до m)Σbiyi* если в исходн. задаче целевая функция неограниченна на множестве планов, то в двойственной задаче система ограничений несовместна.

Вторая теорема двойственности и ее эконом.интерпритация.

Для того, чтобы допустимые решения пары двойственных задач были оптимальными, необходимо и достаточно выполнение условия: xj*(∑aij yi*-cj)=0, j от 1 до n, yi*(∑aij xj*-bi)=0, I от 1 до m. Это условия дополняющей нежесткости. Из них следует: если какое-либо ограничение двойств.задачи обращ-ся оптималь.планом в строгое равенство, то соответствующая компонента опт. плана двойственной задачи должно равняться нулю.Если же какая-то компонента опт. плана равна нулю, то соответствующее ограничение двойств.задачи обращается опт.планом в строгое равенство хj*>0 следовательно (i= от 1 до m)Σaij yi*=cj (затраты на пр-во продукции=цене) – Если продукция вошла в опт.план, то если затраты>цены, объем пр-ва=0 Σaij yi* >cj следовательно xj*=0

yi*>0 следовательно (j=от 1 до n) Σaij xj*=bi (рас-ды рес-ов =запас рес-ов).

(j=от 1 до n) Σaij xj*

Смысл теоремы сводится к следующему:

Если стоимост.оценка рес-ов расход-х на пр-во ед.прод-ии=цене, то этот вид прод-ии входит в оптим.план;

Если затраты превышают цену, то прод-ию производить не следует;

Еслирасход рес-ов=запасу, то стоимост.оценка этого рес-са положительна. Такой рес-с наз-ся дефицитным. Наибелее дефицит.рес-с обладает наибольшей оценкой;

Если рес-с израсходован неполностью, то его стоимост.оценка = 0.

61. Построение оптимального опорного плана двойственной задачи по симплексной таблице исходной задачи

Информация из столбцов обратной матрицы линейных преобразований, приведших к оптимальному результату. Из столбцов матрицы D-1 можно почерпнуть весьма полезную информацию.

Столбец A3: «теневая» цена ресурса S2 равна y01=0, столбец остался

единичным и по первой строке можно прочесть, что x3=9, т.е. при реализации найденного оптимального плана 1-й ресурс окажется в избытке, причем этот избыток (недоиспользование) как раз составит 9 условных единиц.

Столбец A4: «теневая» цена ресурса S2 равна y02=1, ресурс будет полностью использован и его возможное увеличение будет вести к увеличению целевой функции (т.е. дохода). И т.к. y02=1, то увеличение ресурса S2 на 1 у.е. будет давать добавку по доходу на.Z = y02· .в2 = = 1.1 = 1 (тыс. грн.) (здесь.в2 -приращение ресурса S2 и.Z - соответствующее приращение дохода). При таком приращении ресурса S2 максимальный доход уже составит Zmax=58 тыс. грн. + 1 тыс. грн = 59 тыс. грн. На рис. 6.2 проиллюстрирована эта ситуация, комментарий по отношению к которой будет приведен ниже. Из столбца A4 еще следует, что при увеличении ресурса S2 на 1 у.е. для новой оптимальной точки выпуск товара T1 сократится на ½ тонны (на пересечении строки базисной переменной x1 и столбца A4 стоит «-1/2»), а выпуск товара T2 увеличится на 3/2 тонны (т.к. в строке с базисной переменной x2 в столбце A4 имеем «3/2»).Сказанное по столбцу A4 будет ниже прокомментировано с помощьюграфических построений (рис. 6.2).Столбец A5: «теневая» цена ресурса S3 равна y03=2. Это означает, чтоувеличение ресурса S3 на 1 у.е. принесет добавку по Z на.Z = y03· .в3 = 2.1 =2(тыс. грн.) и составит Zmax=58 тыс. грн. + 2 тыс. грн = 60 тыс. грн. При этом, как следует из столбика A5 табл. 3, выпуск T1 увеличится на ½ тонны, а T2 уменьшится на ½ тонны. Запас по сырью S1 (см. 1-ю строку) увеличится на 3/2 у.е.

62. Идея метода динамического програмирования и его геометрическая интерпретация. Принцип оптимальности Беллмана.

Оптимальное решение задачи методом динамического программирования находится на основе функционального уравнения

Чтобы определить его, необходимо:

1.записать функциональное уравнение для последнего состояния процесса (ему соответствует l=n-1)

fn-1(Sl-1)=optimum(Rn(Sn-1,Un)+f0(Sn))

2.найти Rn(Sn-1,Un) из дискретного набора его значений при некоторых фиксированных Sn-1 и Un из соответствующих допустимых областей (так как f0(Sn)=0, то f1(Sn-1)= optimum(Rn(Sn-1,Un)

В результате после первого шага известно решение Un и соответствующее значение функции f1(Sn-1)

3.Уменьшить значение l на единицу и записать соответствующее функциональное уравнение. При l=n-k (k= 2,n) оно имеет вид

fk(Sn-k)=optimum(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2)

4.найти условно-оптимальное решение на основе выражения (2)

5.проверить, чему равно значение l.Если l=0, расчет условно-оптимальных решений закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если l не равно 0, перейти к выполнению п.3.

6.Вычислить оптимальное решение задачи для каждого последующего шага процесса, двигаясь от конца расчетов к началу.

Метод динам программ позволяет одну задачу со многими переменными заменить рядом последовательно решаемых задач с меньшим числом переменных. Решение осуществляется по шагам. Основной принцип, на котором базируется оптимизация многошагового процесса, а также особенности вычислительного метода-принцип оптимальности Беллмана.

Оптимальное поведение обладает тем свойством, что каковы бы ни были начальное состояние и начальное решение, последующие решения должны быть оптимальными относительно состояния, полученного в результате первоначального решения.

Математически он записывается выражением вида:

fn-1(Sl)=optimum(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1)

(l=0,n-1)Optimum в выражении означает максимум или минимум в зависимости от условия задачи.

63. Требования, предъявляемые к задачам, решаемым методом ДП

Динамическое программирование-математический метод для нахождения оптимальных решений многошаговых задач. Многошаговым является процесс, развивающийся во времени и распадающийся на ряд шагов, или этапов.

Одна из особенностей метода динамического программирования состоит в том, что принятые решения по отношению к многошаговым процессам рассматривается не как единичный акт, а как целый комплекс взаимосвязанных решений. Эту последовательность взаимосвязанных решений называют стратегией.Цель оптимального планирования-выбрать стратегию, обеспечивающую получение наилучшего результата с точки зрения заранее выбранного критерия. Такую стратегию называют оптимальной.

Другой важной особенностью метода является независимость оптимального решения, принимаемого на очередном шаге, от предистории, т.е. от того, каким образом оптимизируемый процесс достиг теперешнего состояния. Оптимальное решение выбирается лишь с учетом факторов, характеризующих процесс в данный момент.

Метод динам программ характеризуется также тем, что выбор оптимального решения на каждом шаге должен производиться с учетом его последствий в будущем. Это означает, что, оптимизируя процесс на каждом отдельном шаге, ни в коем случае нельзя забыть обо всех последующих шагах.

64.Экономическая постановка и построение математической модели задачи, решаемой методом ДП(на примере задачи о распределении капиталовложений). Рекуррентное соотношение Беллмана.

Предварительно поясним, что метод динамического программирования применяется прежде всего к тем задачам, в которых оптимизируемый процесс (или ситуация) разворачивается в пространстве или во времени, или в том и другом.

Пусть сам процесс (ситуация) настолько сложен, что нет возможности его оптимизировать известными методами. Тогда по методу динамического программирования СЛОЖНЫЙ процесс (операция, ситуация) разбивается (членится) на ряд этапов (шагов). Эта разбивка во многих случаях является естественной, но в общем случае привносится искусственно. Например, при рассмотрении какой-либо партии игры в шахматы любой ход каждого из игроков как раз и служит

разбивке всей партии на отдельные шаги (этапы). А в военной операции по преследованию одной ракеты другой весь непрерывный процесс приходится искусственно разбивать на этапы, например, через каждую секунду наблюдения. Метод динамического программирования позволяет оптимизацию всего сложного процесса заменить условной оптимизацией по каждому из этапов

(шагов) с последующим синтезом оптимального управления всем процессом. При этом метод предусматривает, что условная оптимизация на отдельном шаге (этапе) делается в интересах, прежде всего, всей операции.

Все вычисления, дающие возможность найти оптимальное значение эффекта, достигаемого за n шагов, fn(S0), проводятся по формуле (1), которая носит название основного функционального уравнения Беллмана или рекуррентное соотношение. При вычислении очередного значения функции fn-1 используется значение функции fn-(l+1), полученное на предыдущем шаге, и непосредственное значение эффекта Rl+1(Sl,Ul+1), достигаемого в результате выбора решения Ul+1 при заданном состоянии системы Sl. Процесс вычисления значения функции fn-1(l=0,n-1)

Осуществляется при естественном начальном условии f0(Sn)=0, которое означает, что за пределами конечного состояния системы эффект равен нулю.

65. Задача о распределении капитальных вложений (пример).

Для решения задачи об оптимальном распределении капиталовложений мы будем пользоваться функциональным уравнением Беллмана. Сначала с помощью простейшей ситуации проиллюстрируем вывод функционального уравнения Беллмана, а потом на примере докажем, как использовать это уравнение для решения интересующей нас задачи.

Начнем с оптимального распределения выделенных капиталовложений в сумме К между двумя предприятиями. Плановые отделы предприятий на основе своих расчетов сформировали функции дохода q(x) для предприятия П1 и h(x) - для предприятия П2. Функции эти означают, что если первое или второе предприятие получит капиталовложение и размере х, то первым предприятием

будет получен доход q(x), а вторым h(x), причем величина x может принимать непрерывные или известные дискретные значения от 0 до К.

Итак, пусть предприятию П1 выделены капиталовложения в сумме х, тогда предприятию П2 выделяется сумма К - х. В этом случае от первого предприятия будет получен доход q(x), а от второго - h(К - x). Если капиталовложения К были выделены на один плановый период, то общий доход от двух предприятий составит R(K, x) = q(x) + h(K - x). Очевидно, что x и соответственно К - x надо выбирать такими, чтобы R(K, x) приняло свое максимальное значение, которое мы обозначим через F(K):

Эта запись является как бы остовом для более полных записей

функционального уравнения Беллмана. УСЛОЖНИМ нашу задачу, распределив капиталовложения на два плановых периода (два этапа). Пусть изначально решено первому предприятию П1 выделить сумму х, а второму К – х. В целом доход получался бы равным R(K, x) = q(x) +

h(K - x). Если мы будем иметь в виду, что капиталовложения распределяются на 2 периода (2 этапа), то на первом предприятии остаток капиталовложений составит.x, где , а на втором - .(К - х), где Соответственно доходы за второй период составят q(.x) -по первому предприятию и h[.(K - x)] - по второму. Оптимизацию по методу динамического программирования, как правило, начинают с концевого этапа. Поэтому начнем со второго этапа, обозначив F1 максимально возможный доход от двух предприятий на втором

этапе. Получим

Затем к рассмотренному последнему (в нашем случае второму) этапу как бы пристраиваем предшествующий (у нас первый) этап и находим максимальный доход от двух этапов вместе:

Аналогичным образом для n этапов получаем

где Fn-1 - целевая функция, дающая наилучший результат за последние (n - 1) этапы. Полученное функциональное уравнение Беллмана носит рекуррентный характер, т.е. связывает значение Fn со значением Fn-1.

В более общем начертании уравнение Беллмана имеет вид

где , Fn-1 - максимальный доход за (n - 1) последних этапов, Fn -

максимальный доход за все n этапов.

66. Понятие о решении задач нелинейного программирования

Пусть задача нелинейного программирования ставится в следующем общем виде: найти такие значения переменных х1, х2,…, хn, которые отвечают условиям:

и приносят требуемый экстремум (максимум или минимум) целевой функции

f = f(х1, х2,…, хn), (13.2)

где f(х1, …, хn) и qi(х1, …, хn) (m , 1 i =) - действительные нелинейные,

регулярные функции n действительных переменных.

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

существенно отличаться от линейных. Например, область допустимых решений может уже быть невыпуклой, а экстремум целевой функции может наблюдаться в любой точке допустимой области. Существенно отличаются и методы решения нелинейных задач. Рассмотрим лишь некоторые подходы к решению этих задач.

Прежде всего также справедлив графический подход при решении простейших задач нелинейного программирования. Так, если аргументами задачи являются переменные х1 и х2, то сначала на плоскости этих переменных строится область допустимых решений, а затем с помощью уровней целевой функции f(х1,х2) определяется оптимальная точка в области.

В нелинейном программировании для решения многих задач используется градиентный подход. Имеется целый ряд градиентных методов, сущность которых состоит в поиске оптимального результата с помощью градиента целевой функции - вектора, указывающего направление максимального возрастания цели для рассматриваемой точки. В общем случае процедура поиска совершается в итеративном режиме от первоначально выбранной точки к точкам с лучшим показателем. Пусть, например, . - о6ласть допустимых решений

рассматриваемой задачи, а итеративный процесс расчетов начинается с точки

Далее, сначала делается переход по градиенту целевой функции, а затем возврат в область. по градиенту к нарушенной границе О2 О3 области.. На рис. 13.3 показано так, что Ai с нечетными индексами принадлежат области., а точки Аi с четными индексами не принадлежат.. По мере приближения к оптимальной точке Q направления рабочих градиентов сближаются. Поэтому идеальным критерием остановки процесса будет коллинеарность градиента цели и градиента нарушенной границы.

67. Понятие о параметрическом и целочисленном программировании .

Постановка и математич модель ЗЦЛП.

В задачах с неделимыми объектами на переменные накладываются условия целочисленности. Иногда эти условия распространяются на все переменные, иногда-на часть переменных.Рассматривают полностью целочисленную задачу

f=(n,j=1)∑CjXi max

(n,j=1)∑AijXj=bi, i=1,m

xi-целое,j=1,n

Теперь в отличие от общей задачи линейного программирования, оптимальный план не обязательно будет в вершине многогранника планов.Существуют следующие методы решения целочисленных задач:

1.Методы отсечения

2.Комбинаторные

3.Приближенные методы..

Параметрическое программирование – раздел математического программирования, посвящённый исследованию задач оптимизации, в которых условия допустимости и целевая функция зависят от некоторых детерминированных параметров.

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

Линейное программирование – это наиболее разработанный раздел математического программирования, с помощью которого выполняются анализ и решение экстремальных задач с линейными связями и ограничениями.

Линейное программирование включает в себя целый ряд эвристических (приближенных) методов решения, позволяющих при заданных условиях из всех возможных вариантов решений производственных задач выбрать наилучший, оптимальный. К этим методам относятся следующие – графический, симплексный, метод потенциалов (модифицированный распределительный метод – МОДИ), Хичкова, Креко, метод аппроксимации Фогеля и другие.

Часть этих методов объединяют общим названием - распределительный, или транспортный, метод.

Родиной линейного программирования является Россия. Первые работы по линейному программированию будущим академиком Л.В. Канторовичем были опубликованы в 1939 г. В 1975 г. за разработку методов линейного программирования им была получена Нобелевская премия по экономике. Поскольку большинство работ академика Л.В. Канторовича посвящено решению транспортных задач, можно считать, что указанная Нобелевская премия отмечает и заслуги российской транспортной науки.

На автомобильном транспорте методы линейного программирования используются с 1960-х годов для решения большого числа важнейших производственных задач, а именно: сокращение дальности перевозок грузов; составление оптимальной схемы перевозок; выбор кратчайших маршрутов движения; задачи перевозки разных, но взаимозаменяемых грузов; сменно-суточное планирование; планирование перевозок мелкопартионных грузов; распределение автобусов по маршрутам и другие.

Особенности модели линейного программирования заключаются в следующем:

Целевая функция и ограничения выражены линейными зависимостями (равенствами или неравенствами);

Число зависимостей всегда меньше числа неизвестных (условие неопределенности);

Неотрицательность искомых переменных. Общая форма записи модели линейного программирования в сокращенном виде выглядит следующим образом:

Найти х ij ≥ 0 (j = 1, 2…n) при ограничениях следующего типа:

Эти ограничения минимизируют (или максимизируют) целевую функцию

Стандартной формой записи модели линейного программирования является система линейных уравнений, записанная в канонической форме, т. е. в форме линейных равенств, в неотрицательных числах:

а 11 х 1 + а 12 х 2 + …+ а 1 n х n = b 1 ;

а 21 х 1 + а 22 х 2 + … + а 2 n х n = b 2 ; (3.1)

……………………………..

a m х 1 + а m 2 х 2 + …+ а mn х n = b m ..

Если модель записана в форме неравенств в неотрицательных числах, т. е. имеет вид

а 11 х 1 + а 12 х 2 + …+ а 1 n х n ≤ b 1 ;

а 21 х 1 + а 22 х 2 + … + а 2 n х n ≤ b 2 ; (3.2)

……………………………..

a m х 1 + а m 2 х 2 + …+ а mn х n ≤ b m ,..

то эта запись приводится к канонической форме (3.1) путем введения дополнительных переменных х n +1 > 0 (i =1,2…m ) в левую часть неравенства (или сокращения числа переменных, если знак неравенства направлен в другую сторону). Дополнительные переменные составляют базис.

Стандартной формой решения задачи линейного программирования является нахождение решений системы линейных уравнений в неотрицательных числах, которые минимизируют целевую функцию. Целевая функция при этом имеет вид

L = с 1 х 1 + с 2 х 2 …с n х n → min, (3.3)

где с 1 , с 2 … с n – коэффициенты целевой функции L при переменных х j .

В целевую функцию дополнительные переменные входят с нулевыми коэффициентами.

В случае максимизации целевой функции L следует знаки при переменных целевой функции изменить на противоположные, и мы вновь придем к задаче минимизации, т.е. одна задача сводится к другой заменой L на –L или max L = min (–L ).

Базисным решением системы линейных уравнений (3.1) называется решение, в котором небазисным переменным даны нулевые значения.

Допустимым называется такое базисное решение, в котором вошедшие в базис переменные являются неотрицательными.

Оптимальным называется допустимое решение, максимизирующее (или минимизирующее) целевую функцию (3.3).

Каждой задаче линейного программирования соответствует другая, называемая двойственной задачей линейного программирования. Исходная задача по отношению к двойственной называется прямой. Прямая и двойственная задачи образуют пару, называемую в линейном программировании двойственной парой. Прямая и двойственная пара образуют несимметричную пару, когда прямая задача записана в канонической форме, и симметричную пару, когда условия задач записаны неравенствами.

Правила составления математической модели двойственной задачи базируются на правилах матричного исчисления.

Понятие двойственности широко используется в анализе задач линейного программирования. Свойство двойственности детально рассматривается в каждом конкретном случае.

3.2. Графоаналитический метод

Графоаналитический метод – это один из простейших методов линейного программирования. Он наглядно раскрывает сущность линейного программирования, его геометрическую интерпретацию. Его недостаток в том, что он позволяет решать задачи с 2 или 3 неизвестными, т. е. применим для узкого круга задач. Метод основан на правилах аналитической геометрии.

Решение задачи с двумя переменными х 1 и х 2 , которые по смыслу задачи не должны быть отрицательными, выполняется в системе декартовых координат. Уравнения х 1 =0 и х 2 = 0 являются осями системы координат первого квадранта

Метод решения рассмотрим на конкретном примере.

Пример 3.1. На складе имеются 300 т изделий из пенобетона и 200 т из стали. Автопредприятию необходимо доставить эти изделия на строящийся объект. На автопредприятии имеются грузовые автомобили КамАЗ - 5320 и

ЗИЛ-4314. За одну поездку КамАЗ-5320 может доставить 6 т пенобетона и 2 т стали, а прибыль от ездки составит 4 тыс. руб. ЗИЛ-4314 за одну поездку доставляет 2 т пенобетона и 4 т стали, прибыль от ездки составляет 6 тыс. руб. Необходимо организовать перевозку так, чтобы обеспечить автопредприятию наибольшую прибыль.

Построим математическую модель задачи. Обозначим через х 1 искомое количество ездок КамАЗ-5320 и через х 2 искомое количество ездок ЗИЛ-4314.

Общая перевозка в т изделий из пенобетона составляет 6х 1 + 2х 2 , а из стали 2х 1 + 4х 2 . Ограничения по перевозке, исходя из имеющегося количества изделий, составляют 6х 1 + 2х 2 ≤ 300т по пенобетону и 2х 1 + 4 х 2 ≤ 200т по стали.

Суммарная прибыль в тыс. руб. выражается величиной 4х 1 + 6х 2 , которую нужно максимизировать и которая является критерием оптимальности в рассматриваемой задаче. Математическая модель задачи, таким образом, выглядит следующей. Необходимо максимизировать целевую функцию

L = 4х 1 + 6х 2 → mах при условиях: 6х 1 + 2х 2 ≤ 300; 2х 1 + 4х 2 ≤ 200; х 1 ≥ 0; х 2 ≥ 0.

Рассмотрим уравнение 6х 1 + 2х 2 = 300. Чтобы построить прямую, описываемую этим уравнением, найдем две точки, лежащие на этой прямой. При х 1 = 0 из уравнения прямой найдем 2х 2 = 300, откуда х 2 = 150. Следовательно, точка А с координатами (0,150) лежит на искомой прямой. При х 2 = 0 имеем 6х 1 = 300, откуда х 1 = 50, а точка D с координатами (50,0) также находится на искомой прямой. Через эти две точки проводим прямую AD (рис. 3.1).

Линейное неравенство 6х 1 + 2х 2 ≤ 300 представляет собой полуплоскость, расположенную с одной из сторон от построенной прямой 6х 1 + 2х 2 = 300. Чтобы выяснить, с какой стороны от этой прямой расположены точки искомой полуплоскости, подставим в неравенство 6х 1 + 2х 2 ≤ 300 координаты какой-либо точки, не лежащей на граничной прямой. Например, начало координат 0-(0,0). Для него справедливо неравенство 6∙0 + 2∙0 = 0 < 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой AD и на рис. 3.1 заштрихована.

Уравнение 2х 1 + 4х 2 = 200 построим по двум точкам. При х 1 = 0 4х 2 = 200, откуда х 2 = 50. Тогда точка Е имеет координаты (0,50) и принадлежит искомой прямой. При х 2 = 0, 2х 2 = 200, точка с находится на данной прямой с координатами (100,0). Подставив в неравенство координаты точки с (0,0), получим 2∙0 + 4∙0 = 0 < 200. Значит, начало координат находится в области допустимых значений от прямой 2х 1 + 4х 2 = 200.

Система ограничений задачи требует, чтобы планы (х 1 ; х 2 ) удовлетворяли всем четырем неравенствам, т. е. допустимые планы – точки (х 1 ; х 2 ) должны одновременно находиться во всех четырех полуплоскостях. Этому требованию отвечают только точки, расположенные внутри и на границе многоугольника OEKD , который и является многоугольником допустимых решений.

Вершинами многоугольника допустимых решений являются точки O, E, K, D, отрезки прямых OE, EK, KD, OD – его ребра. Любая точка многоугольника OEKD является планом задачи, удовлетворяя все ее условия. Вершины многоугольника образованы пересечением двух прямых и соответствуют опорным планам задачи, среди которых находится и наилучший (оптимальный) план. Таким образом, опорных планов будет столько, сколько вершин у многоугольника допустимых решений.

Наглядное геометрическое представление можно получить и для целевой функции L = 4х 1 + 6х 2 . Зафиксируем какое-либо значение целевой функции, например L = 120. уравнение 4х 1 + 6х 2 = 120 определяет прямую, проходящую через точку В с координатами (х 1 = 0; х 2 = 20) и точку L с координатами ((х 1 = 30; х 2 = 0). Отрезок ВL лежит внутри многоугольника OEKD . Следовательно, для всех планов (точек) этого отрезка значение целевой функции одинаково и равно 120. Придавая другие значения целевой функции, получим параллельные прямые, которые называют линиями уровня целевой функции.

Перемещая прямую L параллельно самой себе в одном направлении, получим возрастание целевой функции, а в противоположном направлении – ее убывание. В рассматриваемом примере передвижение прямой ВL вправо определяет возрастание целевой функции, которую мы максимизируем. Так поступаем до тех пор, пока прямая ВL будет иметь хотя бы одну общую точку с многоугольником допустимых решений OEKD . Из рис. 3.1 следует, что последней точкой, которую пересечет прямая уровня целевой функции, будет точка К . Это значит, что точка К определяет оптимальный план задачи.

Направление возрастания, перпендикулярное к линии уровня, называется направлением наибольшего возрастания целевой функции и определяет ее максимальный прирост. Это направление можно установить без построения линий уровня. Для этого необходимо на осях х 1 и х 2 отложить отрезки, равные коэффициентам целевой функции, и по ним, как по координатам, построить вектор наибольшего возрастания целевой функции. В математике его называют градиентом и обозначают знаком grad. Градиентом для функции L = 4х 1 + 6х 2 будет вектор n | 4; 6 | . Для удобства его построения увеличим координаты, например, в 10 раз, т.е. n | 40; 60 | . Построим градиент целевой функции L , для чего соединим точку с координатами (40; 60) с началом координат. Линии уровня целевой функции строят перпендикулярно к направлению градиента.

Итак, тем или другим способом установлено, что точка К определяет оптимальный план задачи, значения переменных которого соответствуют координатам данной точки. Для установления координат необходимо решить систему уравнений прямых, образующих эту вершину:

6х 1 + 2х 2 = 300;

2х 1 + 4х 2 = 200.

Уравняем коэффициенты при х 1 , умножив второе уравнение на 3, и вычтем из второго уравнения первое. Получим 10х 2 = 300, х 2 = 30. Подставив значение х 2 = 30 в любое из уравнений, например в первое, определим значение х 1:

6х 1 + 2х · 30 = 300,

откуда 6х 1 = 300 – 60 = 240, следовательно, х 1 = 40.

Таким образом, чтобы получить наибольшую прибыль автопредприятию, необходимо выполнить 40 ездок на КамАЗ-5320 и 30 ездок на ЗИЛ-4314. Максимальная прибыль при этом составит

L = 4х 1 + 6х 2 = 4 · 40 + 6 · 30 = 340 тыс. руб.

На основе рассмотренного примера и геометрической интерпретации задачи оптимизации с двумя переменными можно сделать следующие выводы:

1) в двухмерном пространстве область допустимых решений представляет собой многоугольник;

2) каждой стороне многоугольника соответствует значение одной переменной, равной нулю;

3) каждой вершине многоугольника допустимых решений соответствуют значения двух переменных, равных нулю;

4) каждому значению целевой функции соответствует прямая;

5) оптимальному решению задачи соответствует вершина многоугольника, в которой целевая функция приобретает оптимальное значение, при этом оптимальными переменными являются координаты этой вершины.

В общем случае задачи оптимизации имеют аналогичную геометрическую интерпретацию. Множество планов задачи будет представлять собой многогранник, вершины которого соответствуют опорным планам. При решении задачи осуществляется переход от одной вершины многогранника к другой с большим значением целевой функции до получения оптимального ее значения. Отметим, что эффективность методов оптимизации как раз и заключается в том, что перебор вершин (итерация) ведется только в направлении наибольшего возрастания целевой функции. Поэтому рассматриваются не все вершины, которых огромное количество, а только те, которые ближе к экстремальной.

При определении класса задач оптимизации и выборе метода ее решения необходимо знать, выпукло или невыпукло множество допустимых решений, линейная или нелинейная целевая функция.

По определению множество называется выпуклым , если для любых двух точек весь отрезок, соединяющий эти точки, принадлежит этому множеству. Примерами выпуклых множеств могут служить, например, отрезок (рис. 3.2,а), плоскость в виде круга, куб, параллелепипед, а также многоугольники, которые целиком расположены по одну сторону от каждой из его сторон, и др.

На рис. 3.2,б изображены невыпуклые множества. В невыпуклых множествах можно указать хотя бы две точки отрезка АВ, не принадлежащие рассматриваемому множеству.

3.3. Симплексный метод

Симплексный метод – это распространенный метод решения задач линейного программирования. Свое название метод получил от слова «симплекс», обозначающего простейший выпуклый многоугольник, число вершин которого всегда на единицу больше, чем размерность пространства. Симплексный метод разработан в США математиком Дж. Данцигом в конце 1940-х годов.

Симплексный метод включает получение неотрицательного базисного решения системы канонических линейных уравнений типа (3.1), последующую минимизацию (максимизацию) целевой функции (3.3) и нахождение таким способом оптимальных значений искомых переменных х 1 , х 2… х n .

Идея симплексного метода заключается в том, что в процессе вычисления последовательно переходят от первого базисного решения ко второму, третьему и т.д. с помощью так называемых симплексных преобразований. Преобразования производятся в форме симплексных таблиц, что значительно упрощает и ускоряет расчеты.

Чтобы получить неотрицательные базисные решения системы линейных уравнений, надо процесс исключения неизвестных вести так, чтобы свободные члены уравнений на всех этапах процесса оставались неотрицательными. При этом следует руководствоваться следующим правилом: в качестве новой базисной переменной принимается любая свободная переменная, при которой есть хотя бы один положительный коэффициент; выводится из базиса переменная, которая соответствует наименьшему отношению свободных членов уравнений к соответствующим положительным коэффициентам уравнений при вводимой в базис переменной. Такие преобразования называются симплексными преобразователями .

Это очень важно, поскольку для нахождения частного неотрицательного решения, отвечающего наибольшему возможному значению какой-то одной свободной переменной при нулевых значениях других свободных переменных, вместо определения области изменения указанной переменной и подстановки ее наибольшего возможного значения в общее решение достаточно принять эту переменную за базисную и подвергнуть систему симплексному преобразованию, перейдя к новому базису, что значительно упрощает расчеты.

Вычисления удобно производить с помощью симплексных таблиц. Переход от одной таблицы к другой соответствует одной итерации, т. е. переходу от одного базиса к другому, при этом значение целевой функции уменьшается. За определенное число итераций переходят к базису, для которого получают оптимальное (минимальное или максимальное) значение целевой функции. Рассмотрим симплексный метод в общем виде.

Общая задача линейного программирования заключается в минимизации (максимизации) целевой функции, переменные которой связаны между собой системой линейных уравнений, подчинены условию неотрицательности.

Пусть необходимо минимизировать линейную форму

L = с 1 х 1 + с 2 х 2 + … с n х n .

При условиях (для наглядности нулевые и единичные коэффициенты в уравнениях сохранены):

1х 1 + 0х 2 + … 0х m + a 1m+ 1x m+1 …+a 1n x n = b 1 ;

0х 1 + 1х 2 + … 0х m + a 2m+ 1x m+1 …+a 2n x n = b 2 ;

……………………………………………

0х 1 + 0х 2 + … 1х m + a mm + 1x m +1 …+a mn x n = b m .

В данной системе уравнений уже имеется готовый базис, поскольку каждое уравнение ограничений содержит неизвестную с коэффициентом, равным единице, которой нет в других уравнениях, т. е. из коэффициентов при переменных х 1 , х 2 …, х m можно составить единичную матрицу.

Решим уравнения относительно базисных переменных:

х 1 = b 1 – (a 1m+1 ·х m+1 …+ a 1n x n);

х 2 = b 2 – (a 2m+1 ·х m+1 …+ a 2n x n);

………………………………

х m = b m – (a mm+ 1x m+1 …+ a mn x n),

а целевую функцию выразим через свободные переменные, подставив в нее на место базисных переменных их выражения через свободные переменные:

L=c 1 b 1 +c 2 b 2 +c m b m –(c 1 a 1m +c 2 a 2m+1 +…+c m a mn+1)x m+1 -…-(c 1 a 1n +c 2 a 2n +…+c m a mn)x n …+c n x n..

Переменные х 1 , х 2 …, х m , с помощью которых найден первый базисный план, являются базисными, а остальные x m +1 , x m +2 ,…x n – свободными. Базисных переменных должно быть всегда столько, сколько уравнений в системе. Исходя из условия неотрицательности, наименьшее значение свободных переменных равно нулю. Полученное базисное решение системы уравнений и является ее первоначальным допустимым решением, т.е. x 1 = b 1 , x 2 =b 2 , … x m =b m , x m +1 = 0,…, x n = 0.

Этому решению соответствует значение целевой функции

L = с 1 b 1 + с 2 b 2 + … с m b m .

Первоначальное решение проверяется на оптимальность. Если оно неоптимально, то путем введения в базис свободных переменных находят следующие допустимые решения с меньшим значением целевой функции. Для этого определяют свободную переменную, которую необходимо ввести в базис, а также переменную, которую необходимо вывести из базиса. Затем переходят от предыдущей системы к последующей эквивалентной системе. Осуществляется это с помощью симплекс-таблиц. Решение задачи продолжается до получения оптимального значения целевой функции.

Симплексные таблицы составляют следующим образом (см. табл. 3.1). Вверху таблицы помещают все переменные х 1 , х 2 …, х n и коэффициенты c j , с которыми соответствующие переменные входят в целевую функцию. Первый столбец c i состоит из коэффициента целевой функции при переменных, вошедших в базис. Затем следует столбец базисных переменных и свободных членов уравнений. Элементы остальных столбцов таблицы представляют собой коэффициенты при переменных, с которыми последние входят в систему уравнений. Таким образом, каждой строке таблицы соответствует уравнение системы, решенное относительно базисной переменной. В таблице показан и вариант плана, который соответствует целевой функции при данном базисе.

Нижняя строка таблицы называется индексной . Каждый ее элемент (оценка) ∆ j определяют

∆ j = z j – c j ,

где c j – коэффициенты при соответствующих переменных в целевой функции; z j – сумма произведений коэффициентов целевой функции при базисных переменных на соответствующие переменные – элементы j –го столбца таблицы.

Таблица 3.1

Симплексная таблица с первоначальным допустимым

МОДЕЛЬ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1 Математическое описание модели линейного программирования

2 Методы реализации моделей линейного программирования

3 Двойственная задача линейного программирования

Модель линейного программирования (ЛП) имеет место, если в исследуемой системе (объекте) ограничения на переменные и целевая функция линейны .

Модели ЛП используются для решения двух основных типов прикладных задач:

1) оптимального планирования в любых сферах человеческой деятельности – социальной, экономической, научно-технической и военной. Например, при оптимальном планировании производства: распределении финансовых, трудовых и других ресурсов, снабжении сырьем, управлении запасами и т. д.

2) транспортной задачи (нахождение оптимального плана различного рода перевозок, оптимального плана распределения разных средств по объектам различного назначения и т. п.)

МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Требуется найти неотрицательные значения переменных

удовлетворяющих линейным ограничениям в виде равенств и неравенств

где – заданные числа,

и обеспечивающих экстремум линейной целевой функции

где – заданные числа, что записывается в виде

Допустимым решением называется любая совокупность , удовлетворяющих условиям.

Область допустимых решений – множество всех допустимых решений.

Оптимальное решение
, для которого .

Замечания

1. Приведенная модель ЛП является общей . Различают также стандартные и канонические формы моделей ЛП.

2. Условия существования реализации модели ЛП:

– множество допустимых решений – не пустое;

– целевая функция ограничена на (хотя бы сверху при поиске максимума и снизу при поиске минимума).

3.ЛП основывается на двух теоремах

Теорема 1. Множество G , определяемое системой ограничений вида, есть выпуклое замкнутое множество (выпуклый многогранник в с угловыми точками - вершинами .)

Теорема 2. Линейная форма , определенная на выпуклом многограннике

j =1,2,…,s

i=s +1,s+2,…,m ,

достигает экстремума в одной из вершин этого многогранника.

Данная теорема получила название теоремы об экстремуме линейной формы.

В соответствии с теоремой Вейерштрасса оптимальное решение единственно и является глобальным экстремумом.

Существует общий аналитический подход к реализации модели ЛП – симплекс-метод. При решении задач линейного программирования достаточно часто решения нет. Это происходит по следующим причинам.

Первую причину проиллюстрируем примером

Про такую причину говорят, что ограничения несовместны. Область допустимых решений – пустое множество.

Вторая причина комментируется следующим примером:

В данном случае, область допустимых решений не ограничена сверху. Область допустимых решений не ограничена.

Следуя традициям линейного программирования, дадим задаче ЛП экономическую интерпретацию. Пусть в нашем распоряжении имеется m типов ресурсов. Количество ресурса типа j равно . Эти ресурсы необходимы для производства n типов товаров. Обозначим количество этих товаров символами соответственно. Единица товара типа i стоит . Производство товаров типа i должно быть ограничено величинами соответственно. На производство единицы товара типа i расходуется ресурса типа j . Необходимо определить такой план производства товаров (), чтобы их суммарная стоимость была минимальной.

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

Общность основных теоретических положений приводит к тому, что алгебраические методы решения задач линейного программирования во многом сходны между собой. В частности, практически любой из них требует предварительного приведения задачи линейного программирования к стандартной (канонической) форме.

Алгебраические методы решения задачи ЛП начинаются с приведения ее к стандартной (канонической) форме :

i =1,..,n ; j =1,..,m .

Любая задача линейного программирования может быть приведена к стандартной форме. Сравнение общей модели с канонической моделью позволяет сделать вывод о том, что для приведения задачи ЛП к стандартной форме необходимо, во-первых, от системы неравенств перейти к равенствам, а во-вторых, преобразовать все переменные так, чтобы они были неотрицательными.

Переход к равенствам осуществляется прибавлением к левой части ограничений неотрицательной остаточной переменной для неравенств типа , и вычитанием из левой части неотрицательной избыточной переменной для неравенств типа . Например, неравенство при переходе к стандартной форме преобразуется в равенство , a неравенство - в равенство . При этом, как остаточная переменная , так и избыточная переменная являются неотрицательными.

Предполагается, что правая часть неравенств неотрицательна. В противном случае, этого можно добиться умножением обеих частей неравенства на «-1» и сменой его знака на противоположный.

Если в исходной задаче линейного программирования переменная не ограничена в знаке, ее можно представить в виде разности двух неотрицательных переменных , где .

Важной особенностью переменных является то, что при любом допустимом решении только одна из них может принимать положительное значение. Это означает, что если , то и наоборот. Следовательно, может рассматриваться как остаточная, а - как избыточная переменные.

Пример Пусть дана задача линейного программирования:

Необходимо привести ее к стандартной форме. Заметим, что первое неравенство исходной задачи имеет знак , следовательно, в него необходимо ввести остаточную переменную . В результате получим .

Второе неравенство имеет знак и для преобразования к стандартной форме требует введения избыточной переменной , выполнив эту операцию, получим .

Кроме того, переменная не ограничена в знаке. Следовательно, как в целевой функции, так и в обоих ограничениях она должна быть заменена на разность . Выполнив подстановку, получим задачу линейного программирования в стандартной форме, эквивалентную исходной задаче:

Задача линейного программирования, записанная в стандартной форме, представляет собой задачу поиска экстремума целевой функции на множестве векторов, являющихся решениями системы линейных уравнений с учетом условий неотрицательности. Как известно, система линейных уравнений может не иметь решений, иметь единственное решение или иметь бесконечное множество решений. Оптимизация целевой функции возможна только в том случае, если система имеет бесконечное множество решений. Система линейных уравнений имеет бесконечное множество решений, если она совместна (ранг основной матрицы равен рангу расширенной) и, если ранг основной матрицы меньше числа неизвестных.

Пусть ранг матрицы системы ограничений равен m . Это значит, что матрица имеет хоть один минор m -го порядка не равный нулю. Не нарушая общности, можно предположить, что минор расположен в левом верхнем углу матрицы. Этого всегда можно добиться, изменив нумерацию переменных. Этот не равный нулю минор ранга m принято называть базисным. Составим систему из первых m уравнений системы, записав ее следующим образом:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .