Методы линейного программирования

Введение 3
1 Сущность линейного программирования 3
2 Историческая справка о методе линейного программирования 5
3 Теоретические основы линейного программирования 6
4 Алгоритм решения задач линейного программирования 12
5 Пример решения задачи линейного программирования 13
6 Пример программной реализации симплекс-метода, как метода линейного программирования 15
Заключение 17
Список литературы 18

1 Сущность линейного программирования

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

2 Историческая справка о методе линейного программирования

Первое упоминание (1938 г.) о математических методах в эффективном управлении производством принадлежит советскому математику Л. В. Канторовичу.
Год спустя в 1939 г. в издании Ленинградского государственного университета появилась небольшая книга известного математика – профессора того же университета Л.В.Канторовича «Математические методы организации и планирования производства»
Термин «линейное программирование» ввели американские математики Дж. Данциг и Т. Купманс в конце 40-х годов. Дж. Данциг разработал математический аппарат симплексного метода решения задач линейного программирования (1951 г.).
Еще до Л.В. Канторовича в России были опубликованы работы, которые можно считать зародышами линейного программирования. Так, в 1930 г. советские экономисты-транспортники (А.Н. Толстой и др.
...

3 Теоретические основы линейного программирования

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

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

Алгоритм решения задач линейного программирования геометрическим методом имеет следующий вид:8
1. Построение области допустимых решений (ОДР) с учетом системы ограничений.
2. Построение вектора – вектора наискорейшего возрастания целевой функции.
3. Проведение произвольной линии уровня, перпендикулярной вектору .
4. Определение оптимального плана и оптимального значения целевой функции.
Обобщенный алгоритм симплекс-метода состоит из следующих этапов9:
1. Из стандартной формы линейной модели определяется начальное допустимое базисное решение, путем приравнивания к нулю m – n переменных.
2. Из числа текущих небазисных переменных выбирается включаемая в новый базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если такой переменной нет, то базисное решение оптимально.
3.
...

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

Рассмотрим пример решения задачи линейного программирования геометрическим (графическим) методом.
Условие задачи:
Решить графически задачу линейного программирования:

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

Находим общую часть полуплоскостей решений, учитывая при этом условия неотрицательности. Заштрихованный многоугольник является областью допустимых решений (ОДР). Далее строится вектор градиент (рисунок 3).
По условию задачи нужно найти минимум функции Z. Передвигая линию уровня параллельно самой себе в направлении возрастания вектора градиента, находим точку «входа» в ОДР – это точка В (рисунок 3). Найденная точка является точкой минимума. Найдем координаты точки В аналитически.

Рисунок 3 – Решение задачи графическим методом
Точка В является пересечением прямых (3) и .
...

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

С помощью программы, разработанной в среде программирования С++ Builder, осуществлено решение задачи симплексным методом.
Условие задачи:
Целевая функция:
Ограничения задачи:

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

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

Рисунок 5 – Решение задачи посредством программного средства
Таким образом, найдено значение искомой целевой функции F(X) = 160, x1 = 40, x2 = 0, x3 =0.
...

Заключение

В данном реферате рассмотрены основные методы линейного программирования, определена сущность линейного программирования, рассмотрена история возникновения методов линейного программирования, приведены алгоритмы методов линейного программирования, а также рассмотрены примеры решения задач, в том числе с помощью программного средства, разработанного в среде С++ Builder.
Линейное программирование решает задачи нахождения оптимальных значений переменных для линейной целевой функции и системы её ограничений, заданных линейными алгебраическими уравнениями или неравенствами.
Методы линейного программирования могут широко применяться на промышленных объектах при оптимизации производственной программы, ассортиментной загрузке оборудования, планировании грузопотоков, составлении оптимальных смесей, решении раскройных, производственно-транспортных задач, выборе ресурсосберегающих технологий и т.д.
...