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

Содержание Введение 3 Линейное программирование 5 Алгоритм симплекс-метода 19 Метод полного исключения Жордана 28 Экономическая постановка задачи 30 Автоматизация задачи с помощью Excel 33 Заключение 36 Список используемой литературы 38 Введение В настоящее время линейное программирование является одним из наиболее употребительных аппаратов

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

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

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

Первым исследованием по линейному программированию является работа Л. В. Кантфовича “Математические методы организации и планирования производства”, опубликованная в 1939 г. В нем дана постановка задач линейного программирования, разработан метод разрешающих множителей решения задач линейного программирования и дано его теоретическое обоснование. Прямая задача линейного программирования является математической формулировкой проблемы составления

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

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

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

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

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

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

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

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

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

; б) область G определяется системой линейных равенств или неравенств Стандартная и каноническая формы задачи линейного программирования Обратите внимание на то, что в указанных выше двух примерах задачи имели достаточно разный вид: в задаче о диете требовалось найти минимум целевой функции, а в задаче о плане производства  максимум. В задаче о диете ограничения имели вид , а в задаче о плане производства  вид .

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

Обозначение будет означать, что Соответственно, запись означает, что Первая стандартная форма задачи линейного программирования имеет вид (1.7) Введем вектора ; ; , a также вектора , и матрицу . Заметим, что комбинация есть не что иное, как скалярное произведение векторов и . Поэтому в векторной форме задача (1.7) примет вид (1.8)

Можно использовать и матричные обозначения. Тогда комбинация есть произведение и задача (1.7) примет вид (1.9) Вторая стандартная форма задачи линейного программирования имеет вид (1.10) В векторной форме эта задача имеет вид (1.11) и в матричной форме - вид (1.12) Канонической формой задачи линейного программирования называется задача вида (1.13) В векторной форме эта задача имеет вид (1.14) и в матричной форме - вид (1.15)

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

планом или просто решением задачи линейного программирования. Правила приведения задач линейного программирования к стандартной и канонической формам Рассмотрим теперь те приёмы, которые позволяют произвольные формы задач линейного программирования приводить к указанным выше стандартным формам. 1. Превращение max в min и наоборот. Если целевая функция в задаче линейного программирования задана в виде , то, умножая её на (-

1), приведем её к виду , так как смена знака приводит к смене на . Аналогично можно заменить на . 2. Смена знака неравенства. Если ограничение задано в виде , то, умножая на (- 1), получим: . Аналогично, неравенство вида больше либо равно можно превратить в неравенство вида меньше либо равно. 3. Превращение равенства в систему неравенств.

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

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

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

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

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

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

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

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

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

разности . Если все эти разности , то план является оптимальным Этап 2 Если есть столбцы, где , то выбирается столбец с максимальным значением этой разности. Индекс j определит вектор, вводимый в базис. Пусть , то есть в базис надо вводить вектор . Назовем столбец, соответствующий этому вектору, направляющим столбцом. В дальнейшем мы будем направляющий столбец помечать символом .

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

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

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

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

его нулями, оставив 1 на месте бывшего элемента . Далее итерации продолжаются. Пример Решить задачу линейного программирования В данном случае вектор равен (0,1 3,0,2,0), а в векторной форме ограничения могут быть записаны в виде . Заполним исходную симплекс-таблицу, взяв в качестве исходного базиса вектора ,что удобно из-за их вида. Исходная симплекс-таблица Ба- План 0 1 -3 0 2 0 зис 0 7 1 3 -1 0 2 0 0 12 0 -2 4 1 0 0 0 10 0 -4 3 0 8 1 0 0 -1 3 0 -2 0

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

и будет направляющим столбцом. В этом направляющем столбце есть два положительных числа  4 и 3. Поэтому нужно рассмотреть два частных и выбрать из них наименьшее. Так как и он достигается на векторе , то этот вектор подлежит выводу из базиса и соответствующая ему строка и будет направляющей строкой. Ба- План 0 1 -3 0 2 0 зис 0 10 1 0 2 0 -3 3 0 1 0 0 0 1 0 0 8 1 -9 0 0 -2 0 Заполним теперь новую симплекс-таблицу, следуя сформулированным выше правилам.

Начинается заполнение, естественно, со второй строки (так как она была направляющей), а затем пересчитываются все остальные строки. Вторая итерация Просматривая дополнительную строку мы вновь видим в ней всего один положительный элемент это 1/2, стоящая в столбце вектора . Следовательно, этот вектор надо ввести в базис и этот столбец будет направляющим. В столбце, соответствующем вектору , всего один положительный элемент это 5/2, которая стоит в первой

строке. Поэтому первая строка будет направляющей и вектор должен быть выведен из базиса. Ба- План 0 1 -3 0 2 0 зис 1 4 1 0 0 -3 5 0 1 0 0 1 0 0 10 1 -11 0 0 0 Запишем новую симплекс-таблицу, следуя сформулированным выше правилам. В получившейся таблице в дополнительной строке стоят лишь отрицательные числа и нули. Поэтому получившийся план является оптимальным. Итак, оптимальный план имеет вид то есть , а все остальные

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

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

Аналогично исключают xs в остальных строках. Получают эквивалентную запись системы алгебраических уравнений. В ней г-я строка имеет прежний вид, но все коэффициенты у нее поделены на ais; 5-й столбец состоит из нулевых элементов (кроме единичного, стоящего в /-й строке). Остальные элементы матрицы системы и столбец свободных переменных пересчитывают по правилу прямоугольника. Например, новое значе¬ние элемента а новое значение элемента столбца свободных членов

Из правила прямоугольника следует, что когда в разрешающей строке (столбце) есть нулевые элементы, то элементы столбцов (строк), пересекающих эти нулевые элементы, остаются без изменения. Экономическая постановка задачи В продаже двух изделий А и В участвуют 3 отдела магазина на продажу одного изделия А: первый отдел затрачивает 7 часов; Второй отдел 7 часов; третий отдел 8 часов.

На продажу изделия В: первый отдел затратил 13 часов; второй отдел 8 часов; третий отдел 2 часа.На продажу обоих изделий: первый отдел затратил 363 часов; второй отдел 327 часов; третий отдел 429 часов. От реализации одного изделия А магазин получил доход 6уе, а от реализации изделия В получил 4уе. Сколько будет максимальный доход от реализации двух изделий Составим математическую модель задачи Тогда задача

ЛП формируется следующим образом: найти максимум целевой функции F(х)=6х1+фх2&#61614;max при ограничениях 7x1+13x2<363 7x1+8x2<327 13x1+2x2<429 Приведем задачу к каноническому виду, для чего добавим в правые части ограничений дополнительные неизвестные х3, х4, х5 (балансовые переменные) при ограничениях 7x+13x2+x3<363 7x1+8x2+ +x4<327 13x1+2x2+ +x5<429 Теперь составим симплексную таблицу 1-ого шага:

Б.П С/Ч, bi -х1 -х2 -х3 -х4 -х5 К, ci х3 363 7 13 1 0 0 384 х4 327 7 8 0 1 0 343 х5 429 8 2 0 0 1 440 f(x) 0 -6 -4 0 0 0 10 b1=363*7-327*7/7=252/7 b2=327/7=327/7 b3=327*8-429*7/7=387/7 a12=7*8-7*13/7=5 a22= 8/7=8/7 a32=7*2-8*8/7=-50/7 a14=7*1-7*0/7=-1 a24=1/7=1/7 a34=7*0-8*1/7=-8/7 c1=7*343-7*384/7=287/7 c2=343/7=343/7 c3=7*440-8*343/7=336/7 БП С/Ч -х1 -х2 -х3 -х4 -х5 К х3 252/7 0 5 1 -1 0 287/7 х4 327/7 1 8/7 0 1/7 0 343/7 х5 387/7 0 -501/7 0 -817 1 336/7 f(x) 1962/7 0 20/7 0 6/7 0 1988/7

F(х)=327/7*6=1962/7 Автоматизация задачи с помощью Excel Теперь можно приступить к решению задачи на компьютере: 1. откроем новый рабочий лист (Вставка &#9658; Лист). 2. в ячейки А2, А3 и А4 занесем общее время данное продажу 3х изделии-7,7,8 3. в ячейки С1, D1, E1 и F1 занесем начальные значения неизвестных х1, х2, х3, х4,х5 (нули) – в дальнейшем значения

этих ячеек будут подобраны автоматически. 4. в ячейки С2:F4 разместим таблицу расхода времени на продажу 3х изделий. 5. в ячейках В2:В4 укажем формулы для расчета дохода от продаже 3х изделии. В ячейке В2 формула будет иметь вид =$C$1*C2+$D$1*D2+$E$1*E2+$F$1*F2, а остальные формулы можно получить методом автозаполнения (копирования). 6. в ячейке G1 занесем формулу целевой функции =C1+2*D1+3*E1.

результат ввода данных в рабочую таблицу представлен на рис.1. 46 0 276 363 322 7 13 327 322 7 8 429 368 8 2 7. дадим команду Сервис &#9658; Поиск решения – откроется диалоговое окно Поиск решения. 8. в поле Установить целевую ячейку мышью укажем ячейку, содержащую оптимизируемое значение (F1) (рис.2). установим переключатель Равной в положение максимальному значению. 9. в поле Изменяя ячейки мышью зададим диапазон подбираемых параметров (неизвестных xi) –

C1:F1. 10. чтобы определить набор ограничений, щелкнем на кнопке Добавить. В диалоговом окне Добавление ограничения в поле Ссылка на ячейку мышью укажем диапазон В2:В4. в качестве условия зададим <=. В поле Ограничение мышью зададим диапазон А2:А4(рис. 3). Это условие указывает, что доход от реализации 3х изделий недолжно превосходить общего дохода.

Щелкнем на кнопке OK. 11. снова щелкнем на кнопе Добавить. В поле Ссылка на ячейку укажем диапазон C1:F1. в качестве условия зададим >=. В поле Ограничение зададим число 0. это условие указывает, что число приготавливаемых изделий неотрицательно. Щелкнем на кнопке ОК. 12. снова щелкнем на кнопке Добавить. В поле Ссылка на ячейку укажем диапазон C1:F1. в качестве условия выберем пункт цел.

Это условие не позволяет производить доли изделий. Щелкнем на кнопке ОК. 13. щелкнем на кнопке Выполнить. По завершение оптимизации откроется диалоговое окно Результаты поиска решения. 14. установим переключатель Значения параметров в положение Сохранить найденное решение, после чего щелкнем на кнопке

ОК. 46 0 276 363 322 7 13 327 322 7 8 429 368 8 2 Оптимальное решение задачи найдено. Заключение Методы и модели линейного программирования широко применяются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределении ее по исполнителям, при размещении заказов между исполнителями и по временным интервалам, при определении наилучшего ассортимента выпускаемой продукции, в задачах перспективного, текущего и оперативного планирования

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

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

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

Акулич И.Л. Математическое программирование в примерах и задачах.[Текст]/И.Л. Акулич Минск : Высшая школа, 2004 год. 2. Гельман В.Я. Решение математических задач средствами Excel: Практикум. [Текст]/ В.Я. Гельман. – СПб.: Питер, 2003. – 237 с. 3. Зайченко Ю.П. Исследование математических операций 1979 г.

4. Иванов Ю.П Лотов А.В. Математические модели в экономике.[Текст]/ Ю.П. Иванов. – М Наука, 1978 год. 5. Карасев А.Н Кремер Н.Ш. , Савельева Т.Н “Математические методы в экономике”, М.2000 6. Красс М.С Чупрынов Б.П. Основы математики и ее приложения в экономическом анализе. Учебник-3-е изд исп М. Дело, 2002 688с. 7. Кузнецов,

А.Г Новикова,Г.И Холод.И.И. Высшая математика. Математическое программирование.[Текст]/А.Г.Кузнецов,Г. И. Новикова, И.И. Холод Минск: Высшая школа, 2001 год 8. Моисеев, Н.Н Иванов, Ю.П Столяров, Е.М. Методы оптимизации. [Текст]/ Н.Н. Моисеев, Ю.П. Иванов, Е.М. Столяров. – М Наука, 9. Павлова Т.Н Ракова О.

А Решение задач линейного программирования средствами EXCEL. Учебное пособие. Димитровград, 2002 г. 10. Шапкин А.С. , Мазаев Н.П. “Математические методы и методы исследования операций.