Тема 1.5. Методы математического программирования.

Оглавление | Назад| Далее| Глоссарий понятий

Выше уже упоминалось о самых простых - детерминированных и одноцелевых задачах, исследованием которых занимается математическое программирование. Слово программирование в данном случае означает "планирование".

К математическому программированию относится:

1. Линейное программирование: состоит в нахождении экстремального значения линейной функции многих переменных при наличии линейных ограничений, связывающих эти переменные;
2. Нелинейное программирование: целевая функция и ограничения могут быть нелинейными функциями;
3. Особым случаем в задачах линейного и нелинейного программирования является случай, когда на оптимальные решения накладывается условие целочисленности. Такие задачи относятся к целочисленному программированию;
4. Динамическое программирование: для отыскания оптимального решения планируемая операция разбивается на ряд шагов (этапов) и планирование осуществляется последовательно от этапа к этапу. Однако выбор метода решения на каждом этапе производится с учетом интересов операции в целом;
5. Теория графов: с помощью теории графов решаются многие сетевые задачи, связанные с минимальным протяжением сети, построение кольцевого маршрута и т.д.
6. Стохастическое линейное программирование
   Бывает много практических ситуаций, когда коэффициенты c_i целевой функции, коэффициенты a_ij в матрице коэффициентов, коэффициенты ограничений b_i - являются случайными величинами. В этом случае сама целевая функция становится случайной величиной, и ограничения типа неравенств могут выполняться лишь с некоторой вероятностью. Приходится менять постановку самих задач с учётом этих эффектов и разрабатывать совершенно новые методы их решения. Соответствующий раздел получил название стохастического программирования.
7. Геометрическое программирование
   Под задачами геометрического программирования понимают задачи наиболее плотного расположения некоторых объектов в заданной двумерной или трехмерной области. Такие задачи встречаются в задачах раскроя материала для производства каких-то изделий и т.п. Это - еще недостаточно разработанная область математического программирования и имеющиеся здесь алгоритмы в основном ориентированы на сокращение перебора вариантов с поиском локальных минимумов.
8. Задачами теории массового обслуживания является анализ и исследование явлений, возникающих в системах обслуживания. Одна из основных задач теории заключается в определении таких характеристик системы, которые обеспечивают заданное качество функционирования, например, минимум времени ожидания, минимум средней длины очереди.
9. Теория игр пытается математически объяснить явления, возникающие в конфликтных ситуациях, в условиях столкновения сторон. Такие ситуации изучаются психологией, политологией, социологией, экономикой.

Тема 2.1. Основные понятия линейного программирования.

Оглавление | Назад| Далее| Глоссарий понятий

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

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

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

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

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

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

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

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

Имеются какие-то переменные х = (х₁ , х₂ , … х_n ) и функция этих переменных f(x) = f (х₁ , х₂ , … х_n ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что
а) функция f(x) является линейной функцией переменных х₁ , х₂ , … х_n
б) область G определяется системой линейных равенств или неравенств.

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

• максимум или минимум целевой функции (критерий оптимальности);
• систему ограничений в форме линейных уравнений и неравенств;
• требование неотрицательности переменных.

Пример 2.1.1

Пусть имеется два станка (S₁ , S₂ ), на каждом из которых можно производить два вида продукции (P₁ , P₂ ). Станок S₁ производит единицу продукции P₁ за 1 час, а единицу продукции P₂ - за 2 часа. Станок S₂ затрачивает на единицу продукции P₁ - 2 часа, а на единицу продукции P₂ - 1 час. Станок S₁ может работать в сутки не более 10 ч., а станок S₂ - не более 8 ч. Стоимость единицы продукции P₁ составляет C₁ руб., а стоимость единицы продукции P₂ - C₂ руб.

Требуется определить такие объемы выпуска продукции P₁ и P₂ на станок, чтобы выручка от реализации производственной продукции была максимальной.

Составим математическую модель задачи:

Обозначим через х₁ и х₂ количества продукции P₁ и P₂, которое планируется произвести на каждом отдельном станке. Стоимость произведенной продукции F = c₁ х₁ + c₂ х₂ . Мы должны назначить х₁ и х₂ так, чтобы величина F была максимальной. Переменные х₁ , х₂ не могут принимать произвольных значений. Их значения ограничены условиями производства, а именно тем, что станки могут работать ограниченное время. На изготовление продукции P₁ станок S₁ тратит 1x₁ часов, а на изготовление продукции P₂ – 2x₂ часов. Поскольку время работы станка S₁ не превосходит 10 ч, то величины х₁ и х₂ должны удовлетворять неравенству x₁ + 2x₂<= 10.

Аналогично можно получить неравенство для станка S₂: 2x₁ + x₂ <= 8.

Кроме того, величины х₁ , х₂ не могут быть отрицательными: x₁ >= 0, x₂ >= 0, по смыслу задачи.

Такие задачи кратко записываются следующим образом:

(2.1)

(2.2)

(2.3)

Итак, математическая модель задачи: найти такой план выпуска продукции Х = ( х₁ , х₂ ), удовлетворяющий системе (2.1) и условию (2.2), при котором функция (2.3) принимает максимальное значение.

Решения, удовлетворяющие системе ограничений (2.1) и требованием неотрицательности (2.2), являются допустимыми, а решения, удовлетворяющие одновременно и требованием (2.3) оптимальными.

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

	(2.4)
	(2.5)
	(2.6)

Коэффициенты a_i,j, b_i, c_j, j = 1, 2, ... , n, i =1, 2, ... , m – любые действительные числа (возможно 0).

Итак, решения, удовлетворяющие системе ограничений (2.4) условий задачи и требованиям неотрицательности (2.5), называются допустимыми, а решения, удовлетворяющие одновременно и требованиям минимизации (максимализации) (2.6) целевой функции, - оптимальными.

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

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

	(2.7)
	(2.8)
	(2.9)

К канонической форме можно преобразовать любую задачу линейного программирования.

Правило приведения ЗЛП к каноническому виду:

1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «≤» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «≥» - со знаком «-»

(2.10)

Вводим переменную

.

Тогда неравенство (2.10) запишется в виде:

(2.11)

В каждое из неравенств вводится своя “уравнивающая” переменная, после чего система ограничений становится системой уравнений.

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

, l - свободный индекс

3. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1)

4. Наконец, если исходная задача была задачей на минимум, то введением новой целевой функции F₁ = -F мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F₁.

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

В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений ее состоит из одних линейных неравенств типа « <= » или « >= ». Все переменные задачи неотрицательны.

	(2.12)

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

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

Пример 2.1.2

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

Введем дополнительные переменные x₃ , x₄ , x₅ . Причем в первое неравенство введем неотрицательную переменную x₃ со знаком минус, а во второе и в третье – со знаком плюс переменные x₄ , x₅ запишем задачу в виде:

Переведем max на min, домножив целевую функцию на (-1)

что и дает эквивалентную задачу в канонической форме.