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

Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина "математическое программирование". Термин "линейное программирование" возник в результате неточного перевода английского "linear programming". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом "linear programming" было бы не "линейное программирование", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термин линейное программирование в нашей литературе стало общепринятым.

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

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

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

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

Иначе говоря, первое определение трактует термин “оптимизация” как факт выработки и принятия оптимального решения Оптимальное решение (optimal solution) - решение, которое минимизирует или максимизирует (в зависимости от характера задачи) критерий качества оптимизационной модели (критерий оптимальности) при заданных условиях и ограничениях, представленных в этой модели. (в широком смысле): мы выясняем, какое состояние изучаемой системы будет наилучшим с точки зрения предъявляемых к ней требований (критерия оптимальности Критерий оптимальности (optimality criterion) - фундаментальное понятие современной экономики (которая переняла его из математического программирования и математической теории управления); применительно к той или иной экономической системе это один из возможных критериев (признаков) ее качества, а именно тот признак, по которому производится сравнение вариантов и один или несколько из них признаются наилучшими из возможных (в данных объективных условиях). ) и рассматриваем такое состояние как цель.

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

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

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

µ New Worksheet (создавать) - создание нового документа с очисткой окна редактирования.

µ Open Worksheet (открыть) - загрузка раннее созданного документа из диалогового окна.

µ Save Worksheet (сохранить) - запись текущего документа с его именем.

µ Печать и контроль документов.

µ Print Worksheet (печать) - распечатка документа на принтере.

µ Print Preview (просмотр) - предварительный просмотр документа.

µ Check Speling (проверка) - проверка орфографии документа.

Кнопки операций редактирования

Во время подготовки документов их приходится редактировать, т.е. видоизменять и дополнять.

µ Cut (вырезать) - перенос выделенной части документа в буфер обмена с очисткой этой части документа.

µ Copy (копировать) - копирование выделенной части документа в буфер обмена с сохранением выделенной части документа.

µ Paste (вставить) - перенос содержимого буфера обмена в окно редактирования на место, указанное курсором мыши.

µ Undo (отменить) - отмена предшествующей операции редактирования.

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

Кнопки размещения блоков

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

µ Align Across (выровнять по горизонтали) - блоки выравниваются по горизонтали.

µ Align Down (выровнять вниз) - блоки выравниваются по вертикали, располагаясь сверху вниз.

Пиктограммы этих кнопок изображают блоки и указанные варианты их размещения.

Кнопки операций с выражениями

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

Следующие группы кнопок являются специфичными именно для системы MathCAD.

Рисунок 4. Кнопки операций с выражениями

Insert Function (вставить функции) - вставка функции из списка, появляющегося в диалоговом окне.

Insert Unit (вставить единицы) - вставка единиц измерения.

Calculate (пересчитать) - вычисление выделенного выражения.

Доступ к новым возможностям MathCAD

Начиная с версии MathCAD 2001 появились новые кнопки, дающие доступ к новым возможностям системы:

Insert Giperlink (включение гиперссылки) - обеспечивает создание гиперссылки.

Component Wizard (мастер компонентов) - открывает окно Мастера, дающего удобный доступ ко всем компонентам системы.

Ran Math Connex (запуск системы Math Connex) - запуск системы для стимулирования блочно-заданных устройств.

Кнопки управления ресурсами

Resource Center (центр ресурсов) - дает доступ к центру ресурсов.

Help (справка) - дает доступ к ресурсам справочной базы данных системы.

4) Панель форматирования.

Четвертая строка верхней части экрана содержит типовые средства управления шрифтами:

µ Style - Переключатель выбора стилей;

µ Font - Переключатель выбора набора символов;

µ Point Size - Переключатель выбора размеров символов;

µ Bold - Установка жирных символов;

µ Italic - Установка наклонных символов;

µ Underline - Установка подчёркнутых символов;

µ Left Align - Установка левостороннего выравнивания;

µ Center Align - Установка выравнивания по центру;

µ Right Align - Установка правостороннего выравнивания.

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

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

5) Наборные математические панели инструментов

Для ввода математических знаков в MathCAD используются удобные перемещаемые наборные панели со знаками. Они служат для вывода заготовок - шаблонов математических знаков (цифр, знаков арифметических операций, матриц, знаков интегралов, производных и т.д.). Для вывода панели Math необходимо выполнить команду View => Toolbar => Math. Наборные панели появляются в окне редактирования документов при активизации соответствующих пиктограмм - первая линия пиктограмм управления системой. Используя общую наборную панель, можно вывести или все панели сразу или только те, что нужны для работы. Для установки с их помощью необходимого шаблона достаточно поместить курсор в желаемое место окна редактирования (красный крестик на цветном дисплее) и затем активизировать пиктограмму нужного шаблона, установив на него курсор мыши и нажав ее левую клавишу.

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

Алфавит MathCAD

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

Алфавит системы MathCAD содержит:

µ Строчные и прописные латинские буквы;

µ Строчные и прописные греческие буквы;

µ Арабские цифры от 0 до 9;

µ Системные переменные;

µ Операторы;

µ Имена встроенных функций;

µ Спецзнаки;

µ Строчные и прописные буквы кириллицы (при работе с русифицированными документами).

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

Числовые константы

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

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

123 - целочисленная десятичная константа.

12.3 - десятичная константа с дробной частью;

12.3*10^-5 - десятичная константа с мантиссой (12.3) и порядком - 5.

Система MathCAD может работать с восьмеричными и шестнадцатеричными числами. Восьмеричные числа в конце отмечаются латинской буквой O (от слова octal - восьмеричное). Шестнадцатеричные числа имеют в конце отличительный признак в виде буквы h или H, такие числа надо начинать с цифры 0 (ноль).

Комплексные числа

Большинство вычислений система выполняет как с действительными, так и с комплексными числами, которое обычно представляются в алгебраическом виде: Z=ReZ+i*ImZ или Z=ReZ+j*ImZ. Здесь ReZ - действительная часть комплексного числа Z, ImZ - его мнимая часть, а символы i или j обозначают мнимую единицу. Такое представление характерно для системы MathCAD.

Однако система не всегда знает, какой символ применить для обозначения мнимой единицы. Поэтому перед использованием любых операций с комплексными числами полезно вначале определить i или j как мнимую единицу (т.е. присвоить им значение квадратного корня из - 1).

Переменные

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

Идентификатор начинается только с буквы, например: x, x1. Идентификатор не должен содержать пробелов не должен совпадать с именами встроенных или определенных пользователем функций. Нельзя использовать для идентификаторов буквы русского языка.

Операторы

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

Встроенные функции

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

µ встроенные элементарные функции;

µ встроенные специальные математические функции;

µ функции с условиями сравнения.

Математические выражения

Функции могут входить в математические выражения. Например, в выражении:

Y-переменная, 1 и 2 - числовые константы, "*" и "+" - операторы, а ln (x) - встроенная функция с аргументом х.

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

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

Рисунок 5. Вид указателя при вводе формул

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

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

Введенную выше формулу можно ввести по-другому:

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

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

Рисунок 6. Вид курсора в режиме вставки

При редактировании формул случаются ошибки. На этот случай в меню Edit имеется команда Undo, отменяющая последнее действие. Того же результата можно достичь, воспользовавшись соответствующей кнопкой панели инструментов Standart или комбинацией клавиш [Alt+Backspace].

Для удаления отдельных чисел или фрагментов формул используется клавиша [Backspace] - если курсор находится в режиме ввода, и клавиша [Del] - если курсор находится в режиме вставки.

В MathCAD существует возможность разбивки больших выражений на строки, если выражения состоит из нескольких слагаемых. Для этого:

µ выполните щелчок на операнде, который, по вашему мнению, следует перенести на следующую страницу;

µ увеличьте след курсора в режиме вставки таким образом, чтобы отметить всю правую часть формулы;

µ нажмите клавишу Backspace, стоящий перед курсором знак "+" будет удален. При этом обе части формулы заключаются в скобки;

µ нажмите комбинацию клавиш [Ctrl+Enter] (осуществляется перевод строки).

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

Если вы по ошибке удалили знак умножения и осуществили перенос строки, то результат будет неправильным, поскольку MathCAD заменит умножение сложением. Разбивка на строки не может применяться для выражений, результаты вычислений которых получены в символьном виде.

Присваивание переменным значений

Обычные переменные отличаются от системных тем, что они должны быть предварительно определены пользователем. В качестве оператора присваивания используется знак ": =". Если переменной присваивается начальное значение с помощью оператора ": =", такое присваивание называется локальным.

С помощью знака "є" (три горизонтальные чёрточки, вводится клавишей [~] (тильда)) можно обеспечить глобальное присваивание, то есть оно может производиться в любом месте документа. Для вывода результата или для контроля значений переменных используется обычный знак равенства "=" (если выводится численный результат) или знак символьного равенства ">" (стрелка), если вычисления производятся в символьном виде.

2. Технология решения оптимизационных задач средствами

Решение задач линейного программирования при помощи симплекс таблиц

Допустим, имеется исходная задача линейного программирования в канонической форме:

В общем случае m любых переменных можно выразить через оставшиеся (n-m) переменных, например - X₁. X_m через X_m+1. X_n:

Здесь коэффициенты В_i и А_i,j выражаются через b_i и a_i,j. Переменные X₁. X_m называются базисными, а X_m+1. X_n - свободными.

Если положить X_m+1=. =X_n=0, то X_i=B_i и если при этом все B_i =0, то и X_i =0, и такой вектор: X= (B₁, B₂,., B_m, 0, 0,., 0) называется базисным или опорным.

Выражаем целевую функцию через свободные переменные:

F=C₀- (C_m+1X_m+1+. +C_nX_n).

Здесь коэффициенты C₀, C_m+1,., C_n выражаются через с_j, B_i, a_i, _j.

Начальная симплекс-таблица

Составим по этим данным так называемую начальную симплекс-таблицу (базис).

Замечание: В простейшем случае в качестве базисных переменных можно взять такие m переменных, каждая из которых входит только в одно ограничение, причем с положительным знаком, а все свободные члены b_i>0.

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