Реферат Методы математического программирования
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Содержание:
Введение. 3
1. Методы линейного программирования. 5
1.1. История проблемы поиска экстремума. 7
1.2. Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП 10
1.3. Алгоритм симплекс-метода. 12
1.4. Метод полного исключения Жордана. 16
2. Задачи линейного программирования. 19
2.1. Геометрическое решение ЗЛП.. 23
2.2. Основные теоремы линейного программирования. 26
Заключение. 28
Список используемой литературы.. 29
Введение
В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решений, в том числе и в финансовой математике. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов. В развитие и совершенствование этих систем вложен труд и талант многих математиков, аккумулирован опыт решения тысяч задач. Владение аппаратом линейного программирования необходимо каждому специалисту в области прикладной математики.
Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:
· рационального использования сырья и материалов; задачи оптимального раскроя;
· оптимизации производственной программы предприятий;
· оптимального размещения и концентрации производства;
· составления оптимального плана перевозок, работы транспорта;
· управления производственными запасами;
· и многие другие, принадлежащие сфере оптимального планирования.
Для большого количества практически интересных задач целевая функция выражается линейно – через характеристики плана, причем допустимые значения параметров подчинены линейным равенствам или неравенствам. Нахождение при данных условиях абсолютного экстремума целевой функции носит название линейного программирования.
Первым исследованием по линейному программированию является работа Л. В. Кантфовича “Математические методы организации и планирования производства”, опубликованная в
Прямая задача линейного программирования является математической формулировкой проблемы составления такого плана использования различных способов производства, который позволяет получить максимальное количество однородного продукта при имеющихся в наличии ресурсах.
Математическое программирование – это прикладная отрасль математики, которая является теоретической основой решения задач оптимального планирования.
Существуют следующие разделы математического программирования: линейное, параметрическое, нелинейное и динамическое программирование. Наиболее разработанным и широко применяемым разделом математического программирования является линейное программирование, целью которого служит отыскивание оптимума (max, min)заданной линейной функции при наличии ограничений в виде линейных уравнений или неравенств.
Цель данной курсовой работы – изучить методы математического программирования, общую задачу линейного программирования.
Задачами курсовой работы:
1. Изучить понятие методов математического программирования.
2. Составить общую задачу линейного программирования.
3.Рассмотреть на примерах решения задач линейного программирования.
1. Методы линейного программирования
Различают детерминированные и одноцелевые задачи, исследованием которых занимается математическое программирование. Слово программирование в данном случае означает "планирование".
К математическому программированию относится:
Линейное программирование: состоит в нахождении экстремального значения линейной функции многих переменных при наличии линейных ограничений, связывающих эти переменные;
Нелинейное программирование: целевая функция и ограничения могут быть нелинейными функциями;
Особым случаем в задачах линейного и нелинейного программирования является случай, когда на оптимальные решения накладывается условие целочисленности. Такие задачи относятся к целочисленному программированию;
Динамическое программирование: для отыскания оптимального решения планируемая операция разбивается на ряд шагов (этапов) и планирование осуществляется последовательно от этапа к этапу. Однако выбор метода решения на каждом этапе производится с учетом интересов операции в целом;
Теория графов: с помощью теории графов решаются многие сетевые задачи, связанные с минимальным протяжением сети, построение кольцевого маршрута и т.д [7].
Стохастическое линейное программирование
Бывает много практических ситуаций, когда коэффициенты ci целевой функции, коэффициенты aij в матрице коэффициентов, коэффициенты ограничений bi - являются случайными величинами. В этом случае сама целевая функция становится случайной величиной, и ограничения типа неравенств могут выполняться лишь с некоторой вероятностью. Приходится менять постановку самих задач с учётом этих эффектов и разрабатывать совершенно новые методы их решения. Соответствующий раздел получил название стохастического программирования [4].
Геометрическое программирование
Под задачами геометрического программирования понимают задачи наиболее плотного расположения некоторых объектов в заданной двумерной или трехмерной области. Такие задачи встречаются в задачах раскроя материала для производства каких-то изделий и т.п. Это - еще недостаточно разработанная область математического программирования и имеющиеся здесь алгоритмы в основном ориентированы на сокращение перебора вариантов с поиском локальных минимумов.
Задачами теории массового обслуживания является анализ и исследование явлений, возникающих в системах обслуживания. Одна из основных задач теории заключается в определении таких характеристик системы, которые обеспечивают заданное качество функционирования, например, минимум времени ожидания, минимум средней длины очереди.
Теория игр пытается математически объяснить явления возникающие в конфликтных ситуациях, в условиях столкновения сторон. Такие ситуации изучаются психологией, политологией, социологией, экономикой [8].
Главное в математическом программировании заключается в том, чтобы определить максимальное и минимальное значения целевой функции.
При этом, необходимо, чтобы значения переменных принадлежали некоторой области допустимых значений. В общем виде эту задачу можно представить так:
здесь
Различия между перечисленными дисциплинами заключаются в виде целевой функции
Специфика определения наиболее приемлемого решения стала исследоваться еще в древности, ее истоки проистекают от задач поиска экстремума в математическом анализе и вариационном исчислении [9].
1.1. История проблемы поиска экстремума
Общепринятыми являются такие утверждения:
отрезок прямой линии отражает самое короткое расстояние между его конечными точками;
дуга большого круга — это самая короткая кривая, посредством которой возможно соединение двух точек на сфере;
самая большая площадь из всех замкнутых плоских кривых эквивалентной длины охватывается окружностью, а наибольший объем — сферой.
Феномены максимизации и минимизации такого вида использовались еще древними греческими математиками. Но, стоит отметить, что те или иные формулировки не предполагали никакого доказательства [8]. В данном контексте, можно отметить ученого I в. н.э. Герона Александрийского. Еще в древности определили, что световой луч, исходящей точкой которого является тока Р и который совпадает с плоским зеркалом L, является отражаемым в направлении точки Q так, что PR и QR создают одинаковые углы с зеркалом (рис. 1.1, а). Герон выдвинул предположение — если
Рис. 1.1. Теорема Герона (а); проблема Штейнера (б); кратчайшая система путей, соединяющих данные точки (в); кратчайшие системы путей, соединяющих вершины квадрата (г, д)
В жизни каждого человека имеют место проблемы, связанные с вычислением предельных категорий — наибольшего и наименьшего, наилучшего и наихудшего и т.п. Задачи, сформулированные в такой форме, как правило, имеют практическое значение. В качестве примера можно привести следующую задачу — какая часть судна должна оказаться в воде, чтобы в процессе плавания сопротивление было наименьшим? Или, какое соотношение размеров следует соблюдать в резервуаре цилиндрической формы для достижения максимального объема при определенном расходе материала?
Теория экстремальных значений берет свое начало в XVII в и оказала влияние на многочисленные математические направления, выдвинув широкий спектр принципов науки. Так, первоначальное исследование Ферма в области дифференциального исчисления стало осуществляться стремительнее благодаря возникшей в дальнейшем цели определить методы для изучения вопросов о максимальных и минимальных значениях. С течением времени эти методы были расширены за счет появления вариационного исчисления. Более четко становилось понимание того, что физические законы могут быть определены в формулировках принципа минимальности, который реализует подход к наименее комплексному решению частных проблем.
1.2. Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП
Линейное программирование – направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием оптимальности.
Несколько слов о самом термине линейное программирование. Он требует правильного понимания. В данном случае программирование - это, конечно, не составление программ для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий [8].
К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов.
Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:
задача об оптимальном использовании ресурсов при производственном планировании;
задача о смесях (планирование состава продукции);
задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");
транспортные задачи (анализ размещения предприятия, перемещение грузов).
Линейное программирование – наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:
математические модели большого числа экономических задач линейны относительно искомых переменных;
данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;
многие задачи линейного программирования, будучи решенными, нашли широкое применение;
некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования.
Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.
В общем виде модель записывается следующим образом:
целевая функция:
| | (1.2) |
ограничения:
| (1.3) |
требование неотрицательности:
| xj ≥ 0, | (1.4) |
При этом aij, bi, cj (
Задача состоит в нахождении оптимального значения функции (1.2) при соблюдении ограничений (1.3) и (1.4).
Систему ограничений (1.3) называют функциональными ограничениями задачи, а ограничения (1.4) - прямыми.
Вектор
1.3. Алгоритм симплекс-метода
Симплекс метод – является универсальным методам, которым можно решить любую задачу линейного программирования.
Сформулировать алгоритм симплекс-метода для решения задач линейного программирования, заданных в канонической форме. Обычно он реализуется в виде симплекс-таблицы.
В первом столбце этой таблицы располагаются обозначения векторов, входящих в базис.
Второй столбец - коэффициенты
Третий столбец - компоненты опорного плана. В дополнительной строке в этом столбце пишется величина
Далее идут столбцы, соответствующие всем векторам
Заметим, что для векторов, входящих в базис, эти разности всегда равны нулю.
Далее идут следующие этапы, связанные с преобразованием этой таблицы. При ручном счете каждый раз эту таблицу лучше переписывать заново, при счете на ЭВМ (который, естественно, всегда используется при решении практических, а не учебных задач), эта таблица просто преобразуется в памяти ЭВМ.
Этап 1
Просматривается дополнительная строка снизу, где записаны разности .
| Если все эти разности |
Этап 2
Если есть столбцы, где
Пусть
Этап 3
Просматривается столбец, соответствующий этому вектору. Если все
| где просматриваются лишь те дроби |
Пусть этот минимум достигается для вектора
| помечать ее символом |
Этап 4
После того, как определены направляющие столбец и строка, начинает заполняться новая симплекс-таблица, в которой на месте направляющей
| строки будет стоять вектор |
Обычно заполнение этой новой таблицы начинается именно с направляющей строки. В качестве компоненты опорного плана туда
| пишется величина |
Остальные элементы этой строки заполняются величинами
Обратите внимание на особую роль элемента
Написанные выше формулы для пересчета элементов направляющей строки можно записать следующим правилом:
Этап 5
Далее начинается пересчет всех остальных строк таблицы, включая и дополнительную нижнюю строку по формулам: для компонент плана
для координат разложения по базису
для дополнительной строки
Обратите внимание на то, что все эти формулы по сути дела строятся по одному правилу
Это правило применимо и к компонентам плана, и к величинам
| 1 на месте бывшего элемента |
Далее итерации продолжаются.[3]
1.4. Метод полного исключения Жордана
Имеется система т линейных алгебраических уравнений с п неизвестными, решение которой надо найти:
Производят такие преобразования, в результате которых в каждой строке и в каждом столбце матрицы системы линейных алгебраических уравнений остаются по одному неизвестному с коэффициентами, равными единице, т. е. фактически получают решение системы. Например, необходимо исключить переменную xs
из всех строк за исключением i-й. Коэффициент ais
, стоящий перед переменной xs
, называют генеральным элементом, i-ю строку и 5-й столбец—разрешающими. Прежде всего разрешающую строку делят на ais
и она остается без изменения. Чтобы исключить переменную xs
из первого уравнения, умножают разрешающую строку на — ais
и складывают с первой строкой. В результате получают первую строку с нулевым элементом на месте ais
. Аналогично исключают xs
в остальных строках. Получают эквивалентную запись системы алгебраических уравнений. В ней i-я строка имеет прежний вид, но все коэффициенты у нее поделены на ais
; 5-й столбец состоит из нулевых элементов (кроме единичного, стоящего в /-й строке). Остальные элементы матрицы системы и столбец свободных переменных пересчитывают по правилу прямоугольника. Например, новое значение элемента, а новое значение элемента столбца свободных членов
Из правила прямоугольника следует, что когда в разрешающей строке (столбце) есть нулевые элементы, то элементы столбцов (строк), пересекающих эти нулевые элементы, остаются без изменения.[1]
2. Задачи линейного программирования
Далее приведем примеры некоторых типовых задач, решаемых при помощи методов линейного программирования. Такие задачи имеют реальное экономическое содержание. Сейчас лишь сформулируем их в терминах ЗЛП, а методы решения подобных задач рассмотрим ниже.
1. Задача об оптимальном использовании ресурсов при производственном планировании.
Общий смысл задач этого класса сводится к следующему.
Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц.
Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида (
Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj.
В планируемом периоде значения величин aij, bi и cj остаются постоянными.
Требуется составить такой план выпуска продукции, при реализации которого прибыль предприятия была бы наибольшей.
Далее приведем простой пример задачи такого класса.
Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 n-часов в день, участка В - 72 n-часа и участка С - 10 n-часов.
Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?
Условия задач указанного класса часто представляют в табличной форме (см. таблицу 2.1).
Таблица 2.1 - Исходные данные задачи об использовании производственных ресурсов
| производственные участки | затраты времени на единицу продукции, н-час | доступный фонд времени, н-час | |
| клюшки | наборы шахмат | ||
| А | 4 | 6 | 120 |
| В | 2 | 6 | 72 |
| С | - | 1 | 10 |
| прибыль на единицу продукции, $ | 2 | 4 | |
По данному условию сформулируем задачу линейного программирования.
Обозначим: x1 - количество выпускаемых ежедневно хоккейных клюшек, x2 - количество выпускаемых ежедневно шахматных наборов.
Формулировка ЗЛП:
| | | ||
| | ||
| x1 ≥ 0, x2 ≥ 0. | |
Подчеркнем, что каждое неравенство в системе функциональных ограничений соответствует в данном случае тому или иному производственному участку, а именно: первое - участку А, второе - участку В, третье - участку С.
Повторимся, методы решения ЗЛП мы будем рассматривать чуть позднее, а сейчас - пример задачи другого типа.
2. Задача о смесях (планирование состава продукции).
К группе задач о смесях относят задачи по отысканию наиболее дешевого набора из определенных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Иными словами, получаемые смеси должны иметь в своем составе m различных компонентов в определенных количествах, а сами компоненты являются составными частями n исходных материалов.[2]
На птицеферме употребляются два вида кормов - I и II. В единице массы корма I содержатся единица вещества A, единица вещества В и единица вещества С. В единице массы корма II содержатся четыре единицы вещества А, две единицы вещества В и не содержится вещество C. В дневной рацион каждой птицы надо включить не менее единицы вещества А, не менее четырех единиц вещества В и не менее единицы вещества С. Цена единицы массы корма I составляет 3 рубля, корма II - 2 рубля.
Составьте ежедневный рацион кормления птицы так, чтобы обеспечить наиболее дешевый рацион.
Представим условие задачи в таблице 2.2.
Таблица 2.2 - Исходные данные задачи о смесях
| питательные вещества | содержание веществ в единице массы корма, ед. | требуемое количество в смеси, ед. | |
| корм I | корм II | ||
| А | 1 | 4 | 1 |
| В | 1 | 2 | 4 |
| С | 1 | - | 1 |
| цена единицы массы корма, р | 3 | 4 | |
Cформулируем задачу линейного программирования.
Обозначим: x1 - количество корма I в дневном рационе птицы, x2 - количество корма II в дневном рационе птицы.
Формулировка ЗЛП:
| | | ||
| | ||
| x1 ≥ 0, x2 ≥ 0. | |
3. Транспортная задача.
Под транспортной задачей понимают целый ряд задач, имеющих определенную специфическую структуру. Наиболее простыми транспортными задачами являются задачи о перевозках некоторого продукта из пунктов отправления в пункты назначения при минимальных затратах на перевозку.
Три поставщика одного и того же продукта располагают в планируемый период следующими его запасами: первый – 120 условных единиц, второй – 100 условных единиц, третий – 80 условных единиц. Этот продукт должен быть перевезен к трем потребителям, потребности которых равны 90, 90 и 120 условных единиц, соответственно.
Обычно начальные условия транспортной задачи записывают в так называемую транспортную таблицу (см. таблицу 2.3). В ячейках таблицы в левом верхнем углу записывают показатели затрат (расходы по доставке единицы продукта между соответствующими пунктами), под диагональю каждой ячейки размещается величина поставки xij (т.е. xij - количество единиц груза, которое будет перевезено от i-го поставщика j-му потребителю).
Таблица 2.3 - Исходные данные транспортной задачи
Необходимо определить наиболее дешевый вариант перевозок, при этом каждый поставщик должен отправить столько груза, сколько имеется у него в запасе, а каждый потребитель должен получить нужное ему количество продукции.
Сформулируем ЗЛП:
| | | ||
| | ||
| xij ≥ 0, ( | |
2.1. Геометрическое решение ЗЛП
Если система ограничений задачи линейного программирования представлена в виде системы линейных неравенств с двумя переменными, то такая задача может быть решена геометрически. Таким образом, данный метод решения ЗЛП имеет очень узкие рамки применения.
Однако метод представляет большой интерес с точки зрения выработки наглядных представлений о сущности задач линейного программирования.[6]
Геометрический (или графический) метод предполагает последовательное выполнение ряда шагов. Ниже представлен порядок решения задачи линейного программирования на основе ее геометрической интерпретации.
1. Сформулировать ЗЛП.
2. Построить на плоскости {х1, х2} прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.
3. Найти полуплоскости, определяемые каждым из ограничений задачи.
4. Найти область допустимых решений.
5. Построить прямую c1x1 + c2x2 = h, где h - любое положительное число, желательно такое, чтобы проведенная прямая проходила через многоугольник решений.
6. Перемещать найденную прямую параллельно самой себе в направлении увеличения (при поиске максимума) или уменьшения (при поиске минимума) целевой функции. В результате, либо отыщется точка, в которой целевая функция принимает максимальное (минимальное) значение, либо будет установлена неограниченность функции на множестве решений.
7. Определить координаты точки максимума (минимума) функции и вычислить значение функции в этой точке.
Далее рассмотрим пример решения ЗЛП графическим методом. Для этого воспользуемся представленной выше задачей о хоккейных клюшках и шахматных наборах.
1. Выше уже приводилась формулировка задачи, здесь нам остается лишь повторить ее:
| | | ||
| | ||
| x1 ≥ 0, x2 ≥ 0. | |
2. Теперь построим прямые, соответствующие каждому из функциональных ограничений задачи (см. рисунок 2.1). Эти прямые обозначены на рисунке (1), (2) и (3).
Рисунок 2.1 - Геометрическое решение ЗЛП
3. Штрихи на прямых указывают полуплоскости, определяемые ограничениями задачи.
4. Область допустимых решений включает в себя точки, для которых выполняются все ограничения задачи. В нашем случае область представляет собой пятиугольник (на рисунке обозначен ABCDO и окрашен синим цветом).
5. Прямая, соответствующая целевой функции, на рисунке представлена пунктирной линией.
6. Прямую передвигаем параллельно самой себе вверх (направление указано стрелкой), поскольку именно при движении в этом направлении значение целевой функции увеличивается. Последней точкой многоугольника решений, с которой соприкоснется передвигаемая прямая, прежде чем покинет его, является точка C. Это и есть точка, соответствующая оптимальному решению задачи.
7. Осталось вычислить координаты точки С. Она является точкой пересечения прямых (1) и (2). Решив совместно уравнения этих прямых, найдем:
Таким образом, для максимизации прибыли компании следует ежедневно выпускать 24 клюшки и 4 набора. Реализация такого плана обеспечит ежедневную прибыль в размере $64.
2.2. Основные теоремы линейного программирования
Для обоснования методов решения задач линейного программирования сформулируем ряд важнейших теорем, опуская их аналитические доказательства. Уяснить смысл каждой из теорем поможет понятие о геометрической интерпретации решения ЗЛП, данное в предыдущем подразделе. [5]
Однако сначала напомним о некоторых понятиях, важных с точки зрения дальнейшего разговора.
Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными, если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные m-n переменных называются неосновными (или свободными).
Базисным решением системы m линейных уравнений c n переменными (m < n) называется всякое ее решение, в котором все неосновные переменные имеют нулевые значения.
Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.
В частном случае, когда в систему ограничений входят только две переменные x1 и x2, это множество можно изобразить на плоскости. Так как речь идет о допустимых решениях (x1, x2 ≥ 0), то соответствующее множество будет располагаться в первой четверти декартовой системы координат. Это множество может быть замкнутым (многоугольник), незамкнутым (неограниченная многогранная область), состоять из единственной точки и, наконец, система ограничений-неравенств может быть противоречивой.
Теорема 2. Если задача линейного программирования имеет оптимальное решение, то оно совпадает с одной (двумя) из угловых точек множества допустимых решений.
Из теоремы 2 можно сделать вывод о том, что единственность оптимального решения может нарушаться, причем, если решение не единственное, то таких оптимальных решений будет бесчисленное множество (все точки отрезка, соединяющего соответствующие угловые точки).
Теорема 3. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка области допустимых решений, и наоборот.
Следствием из теорем 2 и 3 является утверждение о том, что оптимальное решение (оптимальные решения) задачи линейного программирования, заданной (или приведенной) ограничениями-уравнениями, совпадает с допустимым базисным решением (допустимыми базисными решениями) системы ограничений.
Таким образом, оптимальное решение ЗЛП следует искать среди конечного числа допустимых базисных решений.
Заключение
Методы и модели линейного программирования широко применяются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределении ее по исполнителям, при размещении заказов между исполнителями и по временным интервалам, при определении наилучшего ассортимента выпускаемой продукции, в задачах перспективного, текущего и оперативного планирования и управления; при планировании грузопотоков, определении плана товарооборота и его распределении; в задачах развития и размещения производительных сил, баз и складов систем обращения материальных ресурсов и т.д.
Геометрическая интерпретация этого метода состоит в том, что если задача линейного программирования имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает, по крайней мере, с одним из допустимых базисных решений системы ограничений. Путь решения любой задачи линейного программирования: перебрать конечное число допустимых базисных решений системы ограничений и выбрать среди них то, на котором функция цели принимает оптимальное решение. Таким образом, в оптимальный план войдет только та продукция, которая выгодна предприятию, и не войдет убыточная продукция. В этом проявляется рентабельность оптимального плана.
Геометрически это соответствует перебору всех угловых точек многогранника решений. Такой перебор, в конце концов, приведет к оптимальному решению (если оно существует), однако его практическое осуществление связано с огромными трудностями, так как для реальных задач число допустимых базисных решений хотя и конечно, но может быть чрезвычайно велико.
Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирования - симплексного метода.
Список используемой литературы
1. Акулич И.Л. Математическое программирование в примерах и задачах./И.Л. Акулич. - Минск : Высшая школа, 2009 год.
2. Гельман В.Я. Решение математических задач средствами Excel: Практикум./ В.Я. Гельман. – СПб.: Питер, 2010. – 237 с.
3. Зайченко Ю.П. Исследование математических операций 2009 г.
4. Иванов Ю.П., Лотов А.В. Математические модели в экономике./ Ю.П. Иванов. – М., Наука, 1978 год.
5. Карасев А.Н., Кремер Н.Ш. , Савельева Т.Н. Математические методы в экономике, М.2005
6. Красс М.С. , Чупрынов Б.П. Основы математики и ее приложения в экономическом анализе. Учебник-3-е изд., исп.-М. Дело, 2002.-688с.
7. Кузнецов, А.Г., Новикова,Г.И., Холод.И.И. Высшая математика. Математическое программирование./А.Г.Кузнецов,Г.И. Новикова, И.И. Холод. - Минск: Высшая школа, 2004 год
8. Моисеев, Н.Н., Иванов, Ю.П., Столяров, Е.М. Методы оптимизации.
/ Н.Н. Моисеев, Ю.П. Иванов, Е.М. Столяров. – М., Наука, 2006
9. Павлова Т.Н., Ракова О.А.. Решение задач линейного программирования средствами EXCEL. Учебное пособие. Димитровград, 2005 г.
10. Шапкин А.С., Мазаев Н.П. Математические методы и методы исследования операций., М., 2004.
