- •Оглавление
- •Краткая классификация моделей и методов математического программирования
- •Линейное программирование
- •1. Примеры экономических задач линейного программирования
- •1.1. Задача оптимального производственного планирования
- •1.2. Задача о смесях
- •1.3. Задача о раскрое
- •1.4. Транспортная задача
- •1.5. Вопросы для самопроверки
- •2. Некоторые сведения из линейной алгебры
- •2.1. Основные понятия и теоремы
- •Решение систем линейных алгебраических уравнений методом Жордана–Гаусса
- •3.3. Переход от задачи минимизации целевой функции к задаче максимизации
- •3.4. Переход от одной формы модели задачи линейного программирования к другой
- •3.4.1. Переход к канонической форме модели
- •3.4.2. Переход от канонической формы модели задачи линейного программирования к стандартной
- •3. 5. Выпуклые множества
- •4. Графический метод решения задачи линейного программирования
- •4.1. Геометрическая интерпретация множества решений линейного неравенства
- •4.2. Геометрическая интерпретация множества решений системы линейных неравенств
- •Возможные случаи области допустимых решений
- •4.3. Вопросы для самопроверки
- •5. Свойства допустимых планов задачи линейного программирования. Опорный план
- •Опорный план. Теорема о соответствии опорного плана вершине многогранника допустимых планов
- •6. Симплекс-метод
- •6.1. Идея симплекс-метода
- •6.2. Алгебра симплекс-метода
- •6.2.1. Алгоритм симплекс-метода
- •6.2.2. Выбор разрешающей строки в симплексных преобразованиях
- •6.2.3. Альтернативный оптимум
- •6.2.4. Признак неограниченности целевой функции
- •6.3. Понятие о вырождении
- •Примеры решения задач симплекс-методом
- •Пример 6.4. Решить симплекс-методом злп:
- •6.4. Вопросы для самопроверки
- •6.5. Индивидуальное задание
- •6.6. Задачи для самостоятельной работы
- •7. Двойственность в линейном
- •7.1. Пример двойственных задач линейного программирования
- •7.2. Правила построения двойственных задач
- •7.3. Симметричные двойственные задачи
- •Пример 7.3. Для задачи:
- •7.4. Основные теоремы двойственности
- •7.5. Анализ устойчивости двойственных оценок
- •7.6. Вопросы для самопроверки
- •7.7. Индивидуальное задание
- •Заключение
- •Библиографический список
- •Приложение. Применение программы Excel к решению задач линейного программирования
4.1. Геометрическая интерпретация множества решений линейного неравенства
Рассмотрим неравенство:
.
Известно, что точки, координаты которых удовлетворяют уравнению , лежат на прямой. Назовем эту прямую граничной. Граничная прямая разбивает плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству а другой полуплоскости – неравенству Следовательно, геометрической интерпретацией множества решений линейного неравенства является полуплоскость, лежащая по одну сторону от граничной прямой, включая прямую.
Чтобы определить искомую полуплоскость, нужно взять какую-либо точку, не принадлежащую граничной прямой, и проверить, удовлетворяют ли ее координаты данному неравенству.
Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой эта точка принадлежит, в противном случае – другая полуплоскость.
Пример 4.1. Геометрической интерпретацией решений неравенства является полуплоскость, изображенная на рис. 4.1 стрелками. Покажем это.
Рис. 4.1. Геометрическая интерпретация решений
линейного неравенства
Прежде всего в неравенстве заменим знак неравенства на знак точного равенства и построим соответствующую прямую . Эта прямая делит плоскость на две полуплоскости. Так как точка О (0,0) удовлетворяет неравенству , то областью решения данного неравенства является полуплоскость, которой принадлежит эта точка.
4.2. Геометрическая интерпретация множества решений системы линейных неравенств
Пусть дана система линейных неравенств с двумя неизвестными:
Общая часть (пересечение) всех полуплоскостей, соответствующих всем неравенствам, будет представлять собой ОДР системы линейных неравенств.
Возможные случаи области допустимых решений
На рис. 4.2. представлены возможные ситуации, когда ОДР ЗЛП – выпуклый многоугольник (а), неограниченная выпуклая многоугольная область (б), единственная точка (в), пустое множество (г), прямая линия (д), луч (е), отрезок (ж).
|
|
а |
б |
|
|
в |
г |
Рис. 4.2. Возможные случаи ОДР
|
|
|
д |
е |
ж |
Рис. 4.2. (окончание)
Пример 4.2. Построить ОДР системы линейных неравенств:
Решение. В неравенствах системы и условиях неотрицательности переменных ( ) знаки неравенств заменим на знаки равенств: , (4.1)
, (4.2)
, (4.3)
(ось 0Х2), (4.4)
(ось0Х1). (4.5)
Построим полученные прямые, найдем соответствующие неравенствам полуплоскости и их пересечение.
Итак, ОДР системы линейных неравенств является выпуклый многоугольник АВСDЕ.
Рис. 4.3. Область допустимых решений системы
линейных неравенств
Этап 2
Теперь предположим, что ОДР найдена. Перейдем к следующему этапу графического метода решения ЗЛП. Покажем, как среди всех точек ОДР найти такую точку, в которой функция цели имеет максимальное значение. Для этого рассмотрим функцию цели:
Из курса высшей математики известно, что уравнение при фиксированном значении Z определяет прямую, а при изменении значения Z – семейство параллельных прямых. Для всех точек, лежащих на одной из прямых, функция Z принимает одно и то же значение, поэтому указанные прямые называются линиями уровня для функции Z.
Вектор называется градиентом функции Z. Он перпендикулярен линиям уровня и показывает направление наибольшего возрастания функции Z. Так как , то .
Изобразим на одном чертеже ОДР, градиент и одну из линий уровня (например, ) и будем перемещать линию уровня по ОДР параллельно самой себе в направлении вектора до тех пор, пока она не пройдет через последнюю (крайнюю) ее общую точку с ОДР. Координаты этой точки и являются оптимальным решением данной задачи. Будем обозначать оптимальное решение а координаты оптимального решения (плана) , . Для их нахождения необходимо решить систему линейных уравнений, соответствующих прямым, пересекающимся в точке оптимума. Подставив координаты и в функцию цели Z, получим .
Рис. 4.4. Функция Z принимает максимальное значение
в точке М
Пусть, например, выпуклый многоугольник АВМСD является ОДР, а расположен так, как изображено на рис. 4.4. Тогда принимает максимальное значение в точке М.
Пример 4.3. Фирма выпускает продукцию двух видов: А и В, используя два вида взаимозаменяемого оборудования. Фонд времени работы оборудования ограничен соответственно величинами 120 и 260 ч. В таблице приведены нормы затрат времени на изготовление единицы продукции каждого вида:
Вид продукции
Вид оборудования |
Нормы затрат времени, ч |
Фонд времени, ч |
|
А |
В |
||
1 |
2 |
4 |
120 |
2 |
4 |
2 |
260 |
Известен план выпуска продукции А и В, составляющий соответственно 50 и 70 единиц (перевыполнение плана не предполагается).
Определить, сколько единиц продукции А и В должно быть выпущено с использованием оборудования первого и второго вида, чтобы суммарные затраты на выполнение плана были минимальными.
Решение. Обозначим через количество продукции j-го вида , выпускаемой на i-м оборудовании .
Условия задачи запишем в виде таблицы:
Вид продукции
Вид оборудования |
А |
В |
Фонд времени |
1 |
2 |
4 |
120 |
|
|
||
2 |
4 |
2 |
260 |
|
|
||
План |
50 |
70 |
|
Построим математическую модель задачи. Целевая функция описывает затраты времени, связанные с выпуском всей продукции:
.
Ограничения по фонду рабочего времени:
Ограничения по необходимости выполнения плана:
Принимая также во внимание условия неотрицательности переменных, получим математическую модель:
Чтобы решать задачу графическим методом, прежде всего запишем модель в стандартной форме. Для этого выразим x11 и x12 из последних двух ограничений и подставим их в ограничения-неравенства и целевую функцию. В результате преобразований получим:
Построив соответствующие данным ограничениям-неравенствам граничные прямые:
определим полуплоскости, в которых выполняются соответствующие неравенства. Общей частью всех полуплоскостей (с учетом ) является многоугольник ABCD.
Рис. 4.5. Целевая функция достигает минимального значения
в точке B
Далее построим вектор .
Так как нас интересует только направление этого вектора, мы можем взять его произвольной длины.
Перпендикулярно к этому вектору проводим линию уровня через начало координат и, перемещая ее по области ABCD в направлении антиградиента, получаем точку В, в которой целевая функция достигает минимума.
Для нахождения координат этой точки решим систему, составленную из уравнений граничных прямых АВ и ВС:
Получим .
Координаты и найдем из соотношений:
Итак, искомый оптимальный план
.
При этом минимальное значение целевой функции
.
Исходя из условий задачи, можно дать интерпретацию полученного решения: первый вид оборудования используется для выпуска продукции А в количестве 30 единиц, продукция В на первом виде оборудования не производится. На втором виде оборудования производится 20 единиц продукции А и 70 единиц продукции В. При этом затраты на выпуск продукции будут минимальными и составят 280 условных единиц.