что такое математическая постановка задачи

Математическая постановка задачи

Раздел 1. Линейное программирование

В наиболее общей форме математическая постановка задачи линейного программирования (ЛП) имеет вид

(D, f) : , (1.1)

i=1,…,m

x_j ≥ 0

или в матричной форме

(D,f) : , (1.2)

где х = (х₁, …, х_п) Т – вектор переменных задачи, f(x) целевая функция, D – множество допустимых решений. Целью задачи является нахождение такого вектора х * из D, который либо максимизирует, либо минимизирует целевую функцию, т. е. f(x * ) ³ f(x) » хÎ D (в случае максимума) или f(x * ) £ f(x) » хÎ D (в случае минимума). Такие решения называются оптимальными.

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

а) Множество допустимых решений D, если оно не пусто, то обязательно выпукло и либо ограничено (по расстоянию), либо не ограничено;

б) Множество D представляет собой многогранное множество (или выпуклый многогранник), имеющее вершины (их число ограничено – см. раздел 3), боковые ребра и боковые грани;

в) Линии уровня целевой функции представляют собой параллельные плоскости (или гиперплоскости), перпендикулярные направлению вектора коэффициентов с; направление вектора с определяет направление возрастания значения целевой функции f(x), а его обратное направление – направление убывания значения f(x);

г) Если множество D ограничено, то целевая функция достигает на нем и своего максимального значения, и минимального значения как следствие центральной теоремы математического анализа – теоремы Вейерштрасса.

е) Если задача имеет оптимальное решение, то оно находится по крайней мере в одной из вершин множества D; задача может не иметь оптимальное решение из-за неограниченности множества D, когда целевая функция на нем неограниченно возрастает или убывает;

ж) Алгоритм решения задачи представляет собой последовательность действий, связанных с генерацией вершин множества D и проверкой правила оптимальности (правила завершения работы).

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

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

б) ограничения задачи –

, i = 1,…, m,

в) целевая функция – функция дохода

.

Ниже мы рассмотрим решение этой задачи при конкретных числовых данных.

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

Таблица исходных данных

Рабочее время оплачивается в размере 3 ден.ед./ч., сырье стоит 4 ден.ед./кг, стоимость машинного времени несущественна. Имеются следующие ограничения на ресурсы в расчете на сутки: рабочее время – 24 часа, машинное время – 12 часов, сырье –18 кг. Необходимо определить, сколько продукции следует произвести каждым из способов (технологий), чтобы максимизировать прибыль?

б) ограничения на ресурсы:

прибыль на единицу продукции, произведенной первым способом (технологией) составляет по условию 20 – (2*3+2*4) = 6 ден.ед., вторым способом (технологией) 20 – (2*3+3*4) = 2 ден.ед., третьим способом (технологией) 20 – (4*3+1*4) = 4 ден.ед., так что

.

Математическая постановка задачи имеет вид

.

Пример 3. Фирма производит два вида краски для внутренних и наружных работ из сырья двух типов: М1 и М2. Расход сырья (в тоннах) на тонну краски каждого типа представлены в следующей таблице:

Таблица исходных данных

Затраты Сырье	Для наружных работ	Для внутренних работ	Максимальный ежедневный расход
М1
М2

Максимально возможный ежедневный расход сырья составляет 24 и 6 тонн каждого.

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

Источник

Математическая постановка задачи

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

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

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

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

Рис.6.1. Состав задачи для постановки единичного структурно-функционального элемента задачи

В общем виде постановка задачи состоит из четырех принципиально важных компонентов:

1) организационной части ее использования и описания;

2) свода применяемых математических моделей;

3) описания вычислительных алгоритмов;

4) концепции построения информационной модели системы.

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

Математическая модель и разрабатываемые на ее основе алгоритмы должны удовлетворять трем требованиям: определенности (однозначности), инвариантности по отношению к различным альтернативным ситуациям в задаче и результативности (возможности ее решения за конечное число шагов). Результатом алгоритмизации является логически построенная и отлаженная блок-схема.

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

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

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

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

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

Как правило, постановка задачи выполняется в соответствии с определенными требованиями или планом. Приведем пример одного из возможных его вариантов.

План постановки задачи

1. Организационно-экономическая сущность задачи:

— назначение (для каких объектов, подразделений, пользователей предназначена);

— периодичность решения и требования к срокам решения;

— источники и способы получения данных;

— потребители результатной информации и способы ее отправки;

— информационная связь с другими задачами.

2. Описание исходной (входной) информации:

— перечень исходной информации;

— формы представления (документ) по каждой позиции перечня; примеры заполнения документов;

— количество формируемых документов (информации) в единицу времени, количество строк в документе (массиве);

— описание структурных единиц информации (каждого элемента данных, реквизита);

— точное и полное наименование каждого реквизита документа, идентификатор, максимальная разрядность в знаках;

— способы контроля исходных данных;

— контроль разрядности реквизита;

— контроль интервала значений реквизита;

— контроль соответствия списку значений;

— балансовый или расчетный метод контроля количественных значений реквизитов;

— метод контроля с помощью контрольных сумм и любые другие возможные способы контроля.

3. Описание результатной (выходной) информации:

— перечень результатной информации;

— формы представления (печатная сводка, машинный носитель и его макет и т.д.);

— периодичность и сроки представления;

— количество формируемых документов (информации) в единицу времени, количество строк в документе (массиве);

— перечень пользователей результатной информации (подразделение и персонал);

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

— способы контроля результатной информации;

— контроль интервала значений реквизита;

— контроль соответствия списку значений;

— балансовый или расчетный метод контроля отдельных показателей;

— метод контроля с помощью контрольных сумм и любые другие возможные способы контроля.

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

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

— описание связей между частями, операциями, формулами алгоритма;

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

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

5. Описание используемой условно-постоянной информации:

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

— описание структурных единиц информации (по аналогии с исходными записями);

— способы взаимодействия с переменной информацией.

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

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

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

Понятие алгоритма

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

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

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

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

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

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

3. Результативность (или конечность). Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.

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

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

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

Язык схем

Схемой называется наглядное графическое изображение алгоритма, когда отдельные действия (этапы) алгоритма изображаются при помощи различных геометрических фигур (блоков), а связи между этапами (последовательность выполнения этапов) указываются при помощи линий, соединяющих эти фигуры. Термин «блок» употребляется здесь и далее вместо термина «символ», используемого ГОСТом, в связи с употреблением термина «символ» в программировании в другом смысле.

Несмотря на все многообразие решаемых на ЭВМ задач, можно выделить несколько «типичных» действий (этапов), которые в различной последовательности выполняются при решении задач:

1. Присваивание. (Заметим, что присваивание является основной операцией, при помощи которой осуществляется обработка данных.)

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

3. Ввод данных и вывод результата.

4. Начало и конец вычислительного процесса.

Конкретные операции указаны внутри фигур в качестве примеров, Рассмотрим выполнение этих действий, а также функции других элементов схем, приведенных на рис.6.1.

вычисления). Следовательно, термины «переменная» или «функция» только условно соответствуют общепринятым математическим понятиям. Числа, используемые, например, в операторах присваивания для задания значений переменных, называются константами. Константы обозначают сами числа, а не фактические адреса ячеек памяти.

Оператор присваивания, обсуждающийся в этом разделе, используется только для выполнения арифметических операций, поэтому он называется арифметическим оператором присваивания. В языках программирования имеются и другие виды операторов присваивания. Арифметический оператор присваивания выполняет следующие действия. Операции, указанные справа от символа «=», выполняются над записанными в выражении константами (константа — величина, значение которой не изменяется в период ее существования) и теми числами, которые хранятся в ячейках памяти, обозначенных встречающимися именами. Результат помещается в ту ячейку памяти, символический адрес которой указан слева от символа «=». Говорят, что переменной присваивается значение посредством оператора присваивания. Следовательно, используемый здесь символ «=» (присвоить) имеет смысл, отличный от принятого в математике.

В операторах присваивания справа от знака “=“ часто используются арифметические выражения.

Арифметическим выражениемназывается математическая запись, состоящая из констант, переменных, стандартных и нестандартных функций, объединённых знаками арифметических операций:

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

Примеры операторов присваивания

Замечания:

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

2. При пересылке значение переменной копируется. Значение копируемой переменной не изменяется.

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

4. Если переменной не присвоено значение, то ее значение не определено.

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

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

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

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

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

Комментарии можно записывать около любого блока.

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

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

Источник