- •Раздел 1
- •1. Предмет математического программирования
- •1.1. Модель задачи математического программирования
- •1.2. Классификация методов математического программирования
- •2. Линейное программирование
- •2.1. Виды задач линейного программирования
- •Задача о наилучшем использовании ресурсов
- •Задача о раскрое материалов
- •Задача о смесях
- •2.2. Формы записи задач линейного программирования
- •Переход к канонической форме
- •Переход к симметричной форме
- •2.3. Геометрическая интерпретация и графическое решение злп
- •Графический метод решения злп
- •Свойства решений злп
- •Симплексный метод
- •2.5.1. Построение начального опорного плана
- •Нахождение оптимального опорного плана. Переход к нехудшему опорному плану
- •Переход к нехудшему опорному плану
- •3. Двойственность в линейном программировании
- •3.1. Понятие двойственности. Построение двойственных задач
- •Правило построения двойственной задачи
- •Соответствия между неизвестными в паре взаимно двойственных задач
- •Основные теоремы двойственности и их экономическое содержание
Раздел 1
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
1. Предмет математического программирования
Среди многочисленных проблем современного производства и социальной сферы самой актуальной является, пожалуй, проблема управления. Промышленные и сельскохозяйственные предприятия, опытно-конструкторские, научно-исследовательские организации, научно-производственные объединения, предприятия сферы обслуживания и организации производственной и непроизводственной сфер являются сложными человеко-ма-шинными системами, эффективность работы которых во многом зависит от качественного уровня управления ими. Чтобы обеспечить высокий уровень управления, руководителю теперь недостаточно интуиции, личного опыта и хороших организаторских способностей. При принятии стратегических и тактических решений ему приходиться учитывать многочисленные факторы, влияющие на эффективность достижения конечной цели, и опираться на сложные и порой противоречивые критерии. Неоценимую помощь руководителю при выработке и принятии наилучших управленческих решений наряду с другими подходами и методами оказывает математика.
Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных вариантов в условиях рыночных отношений приходится отыскивать наилучшие в некотором смысле при ограничениях, налагаемых на природные, экономические и технологические возможности. До недавнего времени большинство таких задач решали исходя из здравого смысла и опыта лиц, принимающих решения, или просто «на глаз». При таком подходе не было и не могло быть никакой уверенности, что найденный вариант – наилучший. При современных масштабах производства даже незначительные ошибки оборачиваются громадными потерями. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику. Такие методы объединяются под общим названием – математическое программирование.
Математическое программирование – область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т.е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменны.
1.1. Модель задачи математического программирования
Для применения численных методов решения экстремальных задач с ограничениями необходимо построить математическую модель исходной задачи.
Математическая модель – это символическая запись (в виде уравнений, неравенств, систем уравнений, функций и т.д.), отражающая определенные особенности, свойства изучаемых реальных явлений, процессов или объектов.
Требования, предъявляемые к создаваемым моделям, весьма противоречивы. С одной стороны, желательно, чтобы модель была достаточно простой (это значительно упрощает процесс ее исследования). С другой стороны, модель должна быть достаточно полной, т.е. в ней должны быть учтены все существенные факторы, оказывающие наибольшее влияние на течение и исход действий.
Модель задачи математического программирования включает:
1) план задачи (вектор управления, решение, стратегия, поведение и др.) – совокупность неизвестных величин , действуя на которые, систему можно совершенствовать;
2) целевую функцию (показатель эффективности, критерий оптимальности, функционал задачи и др.) – функция, экстремальное значение которой нужно найти в условиях экономических возможностей. Целевую функцию обозначим . Это может быть прибыль, объем выпуска или реализации, затраты производства, уровень обслуживания, число комплектов, отходы и т.д.;
3) систему ограничений (условия), налагаемые на неизвестные величины. Ограничениями являются материальные, финансовые и трудовые ресурсы, возможности технического, технологического и вообще научного потенциала. Математически ограничения выражаются в виде уравнений и неравенств. Их совокупность образует область допустимых решений. Объединение всех условий (ограничений), налагаемых на неизвестные (искомые) величины задачи, обозначим буквой ( ).
В развернутом виде математическую модель можно представить следующим образом:
Найти план , доставляющий экстремальное значение целевой функции , т.е.
при ограничениях
.
Из экономических или физических соображений на план задачи или некоторые его компоненты (координаты), как правило, налагаются условия неотрицательности
,
иногда – целочисленности.
План X, удовлетворяющий системе ограничений задачи, называется допустимым ( ). Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным. Оптимальный план будем обозначать , экстремальное значение функции цели . Оптимальное решение, вообще говоря, не обязательно единственное, возможны случаи, когда оно не существует, имеется конечное или бесчисленное множество оптимальных решений.