Лекция 3-4. Элементы математического программирования

Выбор ЭВМ и программных средств для реализации ЭИС. Среди программных средств в первую очередь необходимо выбрать операционную систему и СУБД. Оценка требуемых объемов памяти и трудоемкости разработки программ.

Определение технологии работы ЭИС, т.е. определение порядка сбора, контроля и хранения данных, определение форматов ввода-вывода информации, установление объемных и временных характеристик выдачи информации, установление правил работы всех групп пользователей.

6. Проверка корректности проекта и определение сроков
его реализации.

Итогом перечисленных выше действий становится технический проект ЭИС.

7. На стадии рабочего проектирования необходимо:

• создать описания всех компонентов базы данных,

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

• разработать программы для всех приложений,

• заполнить ЭИС отладочными данными и оттестировать ее,

• составить инструкции по работе с ЭИС и обучить пользователей.

Стадия эксплуатации начинается с заполнения ЭИС реальными данными.

Этапы эксплуатации и модификации ЭИС поочередно меняют друг друга до тех пор, пока не наступит момент морального старения ЭИС и будет принято решение о ее ликвидации и разработке принципиально новой системы (рис. 1).

Рис. 1. Жизненный цикл ЭИС:

ТЗ - техническое задание; ТП - технический проект;

РП - рабочий проект; Э - эксплуатация; М – модификация

На стадии эксплуатации ЭИС требуется обеспечить реорганизацию БД, рес тарт и восстановление, копирование БД, контроль непротиворечивости БД.

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

Важность исследования процессов модернизации ЭИС можно пояснить такими данными: стоимостные затраты на модернизацию ЭИС достигают примерно трети объема эксплуатационных расходов, за год в ЭИС обычно меняется 10-40% первичных документов и 20-50% выходных документов.

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

• изменения на объекте управления и во внешней среде (дрейф параметров предметной области),

• изменение состава рабочей нагрузки вычислительной системы, замена оборудования, рост объема файлов,

• накопление опыта работы с ЭИС,

• обнаружение проектных ошибок.

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

На стадии эксплуатации системы в отсутствие специальных мероприятий по модернизации ИС ухудшаются ее эксплуатационные показатели, например, снижается пропускная способность. Происходит также ухудшение соответствия между параметрами предметной области и параметрами БД.

В процессе эксплуатации ЭИС производится слежение за изменением параметров ЭИС и предметной области. Для этого используются, например:

• информация об изменениях в системе документооборота и структуре отдельных документов,

• данные об изменениях в составе решаемых экономических задач, системе экономических показателей и методах их расчета,

• характеристики потока запросов к БД,

• оценки пользователей о качестве получаемой информации,

• информация системной мониторной программы или аналогичных средств, работающих в составе применяемых операционных систем и СУБД, сбор статистики о выполненных заданиях.

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

Сравнение результатов измерений с аналогичной информацией за прошлые периоды времени и отклонение текущих параметров функционирования ЭИС от нормативных могут дать основание для проведения модификации ЭИС. Анализ результатов наблюдений должен быть различным в зависимости от целей, которые предполагается достичь после проведения модификации. Первоначально должна быть поставлена цель модификации ЭИС и определено множество методов, ведущих к достижению требуемой цели. Собираемая и анализируемая информация должна лишь доказать (или опровергнуть) целесообразность применения конкретного метода модификации и позволить выработать его спецификацию (рис. 2).

Рис. 2. Взаимозависимость действий на стадиях эксплуатации

и модификации ЭИС

Цели модификации ЭИС можно разделить на шесть больших групп:

• исправление проектных ошибок,

• улучшение эксплуатационных характеристик ЭИС,

• адаптация к изменениям в предметной области,

• разработка нового приложения,

• обеспечение совместимости с другими ИС,

• перенос БД в новую аппаратно-программную среду.

Конкретные методы модификации ЭИС группируются по четырем направлениям (см. табл. 1):

• реструктуризация БД,

• перепрограммирование прикладных задач,

• реорганизация БД,

• настройка вычислительной системы.

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

Таблица 1.3. Соответствие целей и методов модификации ЭИС

Большинство процедур модификации ЭИС могут производиться без прекращения стадии эксплуатации. Однако необходим контроль всех компонентов ЭИС (базы данных, вычислительной системы, программных средств) после проведения каких-либо усовершенствований.

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

Математическое программирование является одним из разделов исследования операций – прикладного направления кибернетики, используемого для решения практических организационных задач.

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

Математическое программирование — математическая дисциплина, изучающая теорию и методы решения задач о нахождении экстремумов функций на множествах конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами).

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

Целевая функция в экстремальных задачах — функция, минимум или максимум которой требуется найти. Найдя экстремум целевой функции, и, следовательно, определив значения управляемых переменных, которые к нему приводят, мы тем самым находим оптимальное решение задачи. Таким образом, целевая функция выступает как критерий оптимальности решения задачи.

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

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

Под принятием решений в исследовании операций понимают сложный процесс, в котором можно выделить следующие основные этапы:

1-й этап. Построение качественной модели рассматриваемой проблемы, т. е. выделение факторов, которые представляются наиболее важными, и установление закономерностей, которым они подчиняются. Обычно этот этап выходит за пределы математики.

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

3-й этап. Исследование влияния переменных на значение целевой функции. Этот этап предусматривает владение математическим аппаратом для решения математических, задач, возникающих на втором этапе процесса принятия, решения. На третьем этапе, пользуясь математическим аппаратом, находят решение соответствующих экстремальных задач.

4-й этап. Сопоставление результатов вычислений, полученных на 3-м этапе, с моделируемым объектом, т. е. экспертная проверка результатов (критерий практики). Таким образом, на этом этапе устанавливается степень адекватности модели и моделируемого объекта в пределах точности исходной информации.

Здесь возможны два случая:

1-й случай. Если результаты сопоставления неудовлетворительны (обычная ситуация на начальной стадии процесса моделирования), то переходят ко второму циклу процесса. При этом уточняется входная информация о моделируемом объекте и в случае необходимости уточняется постановка задачи (1-й этап), уточняется или строится заново математическая модель (2-й этап), решается соответствующая математическая задача (3-й этап) и, наконец, снова проводится сопоставление (4-й этап).

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

В математическом программировании можно выделить два направления.

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

Ко второму направлению – так называемому стохастическому программированию, относятся задачи, в которых исходная информация содержит элементы неопределенности, либо когда некоторые параметры задачи носят случайный характер с известными вероятностными характеристиками. Так, планирование производственной деятельности зачастую производится в условиях неполной информации о реальной ситуации, в которой будет выполняться план. Или, скажем, когда экстремальная задача моделирует работу автоматических устройств, которая сопровождается случайными помехами. Заметим, что одна из главных трудностей стохастического программирования состоит в самой постановке задач, главным образом из-за сложности анализа исходной информации.

Традиционно в математическом программировании выделяют следующие основные разделы.

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

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

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

Среди задач математического программирования самыми простыми (и лучше изученными) являются так называемые задачи линейного программирования. Для этих задач характерно:

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

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

1. Примеры задач линейного программирования.

Задача о пищевом рационе. Ферма производит откорм скота с коммерческой целью. Для простоты допустим, что имеется всего четыре вида продуктов: П₁, П₂, П₃ и П₄. Стоимость единицы каждого продукта с₁, с₂, с₃ и с₄. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков – не менее в₁ единиц, углеводов – не менее в₂ единиц, жиров – не менее в₃ единиц. Для продуктов П₁, П₂, П₃ и П₄ содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано в таблице, а_ij – определенные числа, первый индекс указывает на номер продукта, а второй – на номер элемента (белки, углеводы, жиры).

продукт	белки	углеводы	жиры
П1	а11	а12	а13
П2	а21	а22	а23
П3	а31	а32	а33
П4	а41	а42	а43

Требуется составить такой пищевой рацион (то есть назначить количества продуктов П₁, П₂, П₃ и П₄, входящих в него), чтобы условия по белкам, углеводам и жирам были выполнены и при этом стоимость рациона была минимальна.

Составим математическую модель. Обозначим через - количества продуктов П₁, П₂, П₃ и П₄, входящих в рацион. Показатель эффективности, который требуется минимизировать, - стоимость рациона L; стоимость линейно зависит от элементов решения , то есть

.

Запишем в виде формул ограничительные условия по белкам, углеводам и жирам. Учитывая, что в одной единице продукта П₁ содержится а₁₁ единиц белка, а в х₁ единицах - а₁₁ х₁ единиц белка, в х₂ единицах продукта П₂ содержится а₂₁ х₂ единиц белка и так далее, получим три неравенства:

(*)

Эти линейные неравенства представляют собой ограничения, накладываемые на элементы решения .

Таким образом, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных , чтобы они удовлетворяли ограничениям-неравенствам (*) и одновременно обращали в минимум линейную функцию этих переменных

.

Имеем типичную задачу линейного программирования.

Задача о снабжении сырьем. Имеются три промышленных предприятияП₁, П₂, П₃, требующих снабжения определенным видом сырья. Потребности в сырье каждого предприятия равны соответственно а₁,а₂, а₃ единиц. Имеется пять сырьевых баз, расположенных от предприятий на каких-то расстояниях и связанных с ними путями сообщения с разными тарифами. Единица сырья, получаемая предприятием П_i с базы Б_j обходится предприятию в с_ij рублей (первый индекс – номер предприятия, второй – номер базы).

предприятие	Б1	Б2	Б3	Б4	Б5
П1	с11	с12	с13	с14	с15
П2	с21	с22	с23	с24	с25
П3	с31	с32	с33	с34	с35

Возможности снабжения сырьем с каждой базы ограничены ее производственной мощностью: базы Б₁, Б₂ ,Б_3, Б_4, Б₅ могут дать не более b₁, b₂, b₃, b₄, b₅ единиц сырья. Требуется составить такой план снабжения предприятий сырьем (то есть, с какой базы, куда и какое количество сырья везти), чтобы потребности предприятия были обеспечены при минимальных расходах на сырье.

Опять поставим задачу линейного программирования. Обозначим х_ij – количество сырья, получаемое i -ым предприятием с j -ой базы. Всего план будет состоять из 15-ти элементов решения

Введем ограничения по потребностям. Они состоят в том, что каждое предприятие получит нужное ему количество сырья (ровно столько, сколько ему требуется)

(*)

Далее запишем ограничения-неравенства, вытекающие из производственных мощностей баз

(**)

Запишем суммарные расходы на сырье, которые мы хотим минимизировать. С учетом данных таблицы получим

. (***)

Мы получили задачу линейного программирования – найти такие неотрицательные значения переменных х_ij, которые удовлетворяли бы ограничениям-равенствам (*), ограничениям-неравенствам (**) и обращали бы в минимум их линейную функцию (***).

2. Основная задача линейного программирования

Любую задачу линейного программирования можно свести к стандартной форме, так называемой «основной задаче линейного программирования» (ОЗЛП), которая формулируется следующим образом:

найти неотрицательные значения переменных , которые удовлетворяли бы условиям-равенствам

и обращали бы в максимум линейную функцию этих переменных

.

В случае, когда L надо обратить не в максимум, а в минимум, знак L меняется на противоположный (максимизировать не L, а L` = - L). Кроме того, от любых условий-неравенств можно перейти к условиям-равенствам с помощью новых «дополнительных» переменных. Покажем, как это делается.

Пусть требуется найти неотрицательные значения переменных x₁,x₂, x₃, удовлетворяющие ограничениям – неравенствам

(3)

и обращающие в максимум линейную функцию от этих переменных

(4)

Начнём с того, что приведём условия (3) к стандартной форме, так, чтобы знак неравенств был одинаковый, а справа стоял нуль. Получим

(5)

А теперь обозначим левые части неравенств (6.5.) соответственно через y₁ и y₂

(6)

Из условий (5) и (6) видно, что новые переменные y₁, y₂ также должны быть неотрицательными.

Какая же теперь перед нами стоит задача? Найти неотрицательные значения переменных x₁,x₂,x₃,y₁,y₂ такие, чтобы они удовлетворяли условиям – равенствам (6) и обращали в максимум линейную функцию этих переменных (то, что в L не входит дополнительные переменные y₁, y₂, неважно: можно считать, что они входят, но с нулевыми коэффициентами).

Мы получили основную задачу линейного программирования (ОЗЛП). Переход к ней от первоначальной задачи с ограничениями – неравенствами (3) получен с помощью увеличения числа переменных на два (число неравенств).

Возможен и обратный переход – от ОЗЛП к задаче с ограничениями-неравенствами.

3. Существование решения ОЗЛП и способы его нахождения

Рассмотрим основную задачу линейного программирования (ОЗЛП):

найти неотрицательные значения переменных , удовлетворяющие m условиям:

(1)

и обращающие в максимум линейную функцию этих переменных

(2)

Назовём допустимым решением ОЗЛП всякую совокупность неотрицательных значений , удовлетворяющую условиям (1). Оптимальным назовём то из допустимых решений, которое обращает в максимум функцию (2).

Требуется найти оптимальное решение. Всегда ли эта задача имеет решение?

1. Может оказаться, что уравнения (1) вообще несовместны (противоречат друг другу).

2. Может оказаться и так, что они совместны, но не в области неотрицательных решений, т.е. не существует ни одной совокупности положительных чисел , удовлетворяющей условиям (1).

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

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

Для более наглядного представления ОЗЛП, обратимся к геометрической интерпретации. Пусть число уравнений m на два меньше числа переменных n (n-m = k = 2). Такой частный случай даёт возможность геометрической интерпретации ОЗЛП на плоскости. Мы знаем, что n линейно независимых уравнений (1) всегда можно разрешить относительно каких-то m базисных переменных, выразив их через остальные, свободные, число которых равно n-m = k (в нашем случае k = 2).

4. Решение задачи линейного программирования графически

Среди всех точек выпуклой области, являющейся решением системы ограничений, выбрать такую, координаты которой минимизируют (максимизируют) линейную функцию F = с₁x + с₂y. Заметим, что переменные x, y в ЗЛП принимают, как правило, неотрицательные значения (x≥ 0, y ≥ 0), поэтому область расположена в I четверти координатной плоскости.

Рассмотрим линейную функцию F = с₁x + с₂y и зафиксируем какое-нибудь ее значение F. Пусть, к примеру, F = 0, т.е. с₁x + с₂ y = 0. Графиком этого уравнения будет прямая, проходящая через начало координат (0;0).

При изменении фиксированного значения F = d, прямая с₁x+ с₂y = d будет смещаться параллельно и «зачертит» всю плоскость. Пусть D – многоугольник – область решения системы ограничений. При изменении d прямая с₁x + с₂y = d, при некотором значении d = d₁ достигнет многоугольника D, назовем эту точку А «точкой входа», и затем, пройдя многоугольник, при некотором значении d = d₂ будем иметь с ним последнюю общую точку В, назовем В «точкой выхода». Очевидно, что своего наименьшего и наибольшего значения целевая функция F = с₁x + с₂y достигнет в точках «входа» А и «выхода» В.

Учитывая, что оптимальное значение на множестве допустимых решений целевая функция принимает в вершинах области D, можно предложить следующий план решения ЗЛП:

· построить область решений системы ограничений;

· построить прямую, соответствующую целевой функции, и параллельным переносом этой прямой найти точку «входа» или «выхода» (в зависимости от требования минимизировать или максимизировать целевую функцию);

· определить координаты этой точки, вычислить в них значение целевой функции.

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

При графическом решении ЗЛП возможны два случая, которые требуют особого обсуждения.

Дата добавления: 2014-01-11