Какая программа называется линейной. Кратко о линейном программировании. Составление простейших программ

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

Здесь мы рассмотрим задачу линейного программирования с ограничениями-равенствами - так называемую основную задачу линейного программирования (0ЗЛП).

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

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

Имеется ряд переменных

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

и, кроме того, обращали бы в минимум линейную функцию

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

Условимся называть допустимым решением ОЗЛП любую совокупность переменных

удовлетворяющую уравнениям (2.1).

Оптимальным решением будем называть то из допустимых решений, при котором линейная функция (2.2) обращается в минимум.

Основная задача линейного программирования необязательно должна иметь решение.

Может оказаться, что уравнения (2.1) противоречат друг другу; может оказаться, что они имеют решение, но не в области неотрицательных значений . Тогда ОЗЛП не имеет допустимых решений. Наконец, может оказаться, что допустимые решения ОЗЛП существуют, но среди них нет оптимального: функция L в области допустимых решений неограничена снизу.

С примерами таких особенностей ОЗЛП мы познакомимся в дальнейшем.

Рассмотрим, прежде всего, вопрос о существовании допустимых решений ОЗЛП.

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

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

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

Матрицей системы линейных уравнений

называется таблица, составленная из коэффициентов при

Расширенной матрицей системы линейных уравнений называется та же матрица, дополненная столбцом свободных членов:

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

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

Пример 1. Дана система трех уравнений с четырьмя неизвестными:

Определить, является ли эта система совместной?

Решение. Матрица системы:

Расширенная матрица:

Определим ранг первой матрицы. Он не может быть больше, чем 3 (так как число строк равно 3). Составим какой-нибудь определитель, вычеркивая из матрицы какой-нибудь столбец, например, последний. Получим

Вычисляя этот определитель по известному правилу, получим:

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

Пример 2. Исследовать на совместность систему двух уравнений с тремя неизвестными :

Решение. Расширенная матрица системы:

(левая ее часть - матрица системы).

Найдем ранг матрицы системы, составляя все возможные определители второго порядка:

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

Найдем ранг расширенной матрицы. Определитель

Отсюда ранг расширенной матрицы он не равен рангу матрицы системы: Грфг, следовательно, система уравнений несовместна.

Пример 3. Исследовать на совместность систему трех уравнений с четырьмя неизвестными:

Решение Расширенная матрица системы (вместе с матрицей системы):

Найдем ранг матрицы системы. Возьмем определитель третьего порядка, составленный из ее элементов, например:

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

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

Так как имеется неравный нулю определитель второго порядка, например,

то ранг матрицы системы равен

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

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

Итак, если система уравнений-ограничений ОЗЛП совместна, то матрица системы и ее расширенная матрица имеют один и тот же ранг.

Этот общий ранг называется рангом системы; он представляет собой не что иное, как число линейно независимых уравнений среди наложенных ограничений.

Очевидно, ранг системы не может быть больше числа уравнений :

Очевидно, также, что ранг системы не может быть больше общего числа переменных :

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

Структура задачи линейного программирования существенно зависит от ранга системы ограничений (2.1).

Рассмотрим, прежде всего, случай, когда , т. е. когда число линейно независимых уравнений, входящих в систему (2.1), равно числу переменных п. Отбросим «лишние» уравнения, являющиеся линейными комбинациями других. Система уравнений-ограничений ОЗЛП принимает вид:

Так как то определитель, составленный из коэффициентов,

не равен нулю. Из алгебры известно, что в этом случае система (2.4) имеет единственное решение. Чтобы найти величину достаточно в определителе заменить столбец - столбцом свободных членов и разделить на .

Итак, при система уравнений-ограничений ОЗЛП имеет единственное решение:

Если в этом решении хотя бы одна из величин отрицательна, это значит, что полученное решение недопустимо и, значит, ОЗЛП не имеет решения.

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

Очевидно, этот тривиальный случай не может нас интересовать.

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

Линейной называется программа, все операторы которой выполняются последовательно, в том порядке, в котором они записаны. Это самый простой вид программ.

Переменные

Переменная - это величина, которая во время работы программы может -

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

Для каждой переменной задается ее имя и тип, например:

var number: integer; х, у: real; option: char;

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

Тип переменных выбирается исходя из диапазона и требуемой точности представления данных.

При объявлении можно присвоить переменной некоторое начальное значение, т.е. инициализировать ее. Под инициализацией понимается задание значения, выполняемое до начала работы программы. Инициализированные переменные описываются после ключевого слова const:

const number: integer = 100; x: real = 0.02; option: char = "ю";

По умолчанию все переменные, описанные в главной программе, обнуляются.

Выражения

Выражение - это правило вычисления значения. В выражении участвуют -

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

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

1. Унарная операция not, унарный минус -, взятие адреса @.
2. Операции типа умножения:* / div mod and shl shr.
3. Операции типа сложения: + - or xor.
4. Операции отношения: = о = in.

Функции, используемые в выражении, вычисляются в первую

Примеры выражений:

t + sin (х)/2 * х -результат имеет вещественный тип; а

(х > 0) and (у

Структура программы

Программа на ПАСКАЛЕ состоит из необязательного заголовка, разделов описании и раздела операторов:

program имя; {заголовок) разделы описаний begin раздел операторов end. (* программа заканчивается точкой *)

Программа может содержать комментарии, заключенные в фигурные скобки {} или в скобки вида (* *).

Общая структура программы приведена на рис. 2.1.

В разделе операторов записываются исполняемые операторы программы. Ключевые слова begin и end не являются операторами, а служат для их объединения в так называемый составной оператор, или блок. Блок может записываться в любом месте программы, где допустим обычный оператор.

Разделы описаний бывают нескольких видов: описание модулей, констант, типов, переменных, меток, процедур и функций.

Модуль - это подключаемая к программе библиотека ресурсов (подпрограмм, констант и т.п.).

Рис. 2.1.

Раздел описания модулей, если он присутствует, должен быть первым. Описание начинается с ключевого слова uses, за которым через запятую перечисляются все подключаемые к программе модули, как стандартные, так и собственного изготовления, например: uses crt, graph, my_module;

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

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

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

const weight: real = 61.5; n = 10;

Раздел описания меток начинается с ключевого слова label, за которым через запятую следует перечисление всех меток, встречающихся в программе. Метка - это либо имя, либо положительное число, не превышающее 9999. Метка ставится перед любым исполняемым оператором и отделяется от него двоеточием. Пример описания меток: label 1, 2, error;

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

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

Ввод с клавиатуры. Для ввода с клавиатуры определены следующие процедуры: read и readln: read (список); readln [(список)];

В скобках указывается список имен переменных через запятую. Квадратные скобки указывают на то, что список может отсутствовать. Например:

read (a, b, с); readln (у); readln;

ВНИМАНИЕ

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

Ввод значения каждой переменной выполняется так:

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

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

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

Вывод на экран. При выводе выполняется обратное преобразование: из внутреннего представления в символы, выводимые на экран. Для этого в языке определены стандартные процедуры write и writeln: write (список); writeln [(список)];

Процедура write выводит указанные в списке величины на экран, а процедура writeln вдобавок к этому еще и переводит курсор на следующую строку. Процедура writeln без параметров просто переводит курсор на следующую строку.

Выводить можно величины логических, целых, вещественных, символьного и строкового типов. В списке могут присутствовать не только имена переменных, но и выражения, а также их частный случай - константы. Кроме того, для каждого выводимого значения можно задавать его формат, например: writeln (а:4, Ь:6:2);

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

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

Составление простейших программ

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

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

для блока Начало - оператор REM с названием программы;

для блока Ввод - оператор ввода;

для блока Процесс - оператор присваивания;

для блока Вывод - оператор вывода;

для блока Останов - оператор END.

В этом все правило!

Теперь приведем примеры конкретных программ рассматриваемого вида.

Задача 12.2

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

Задача 12.3

Переставить значения величин А и В.

Решение задач 12.2 и 12.3. Эти задачи рассматривались в главе 10, поэтому на рис. 12.2 приведены без пояснений схема алгоритма и программа задачи 10.2, а на рис. 12.3 - то же для задачи 10.3.

На рис. 12.2 и 12.3 стрелками показано соответствие операторов программы блокам схемы алгоритма.

Приведем программы решения еще двух задач. Программа задачи 12.1 иллюстрирует использование величин различного типа. Программа задачи 12.2 демонстрирует организацию вывода данных на печатающее устройство.

Рис. 12.2

Задача 12.1

Вычислить значения У и Z по формулам:

где В и В - целые величины.

Решение

Исходные данные: Э%, В%, С, X, А(а).

Результат: Y,Z%.

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

10 REM ЗАДАЧА 1
20 PRINT "ВВЕСТИ D%, В%, С, X, А"
30 INPUT D%,В%, С, X, А 40 R$="HBAH0B, 10А КЛ"
50 Z%=2*D%-3*В%
60 Y=(3*ABS(X)+С:(1/3)+SIN(A)/COS(А))*Z%
70 PRINT "Z%=";Z%; "Y="; Y 80 PRINT R$
90 END

Задача 12.2

Вычислить значение функции У = Л 2 + В 1 и отпечатать (вывести на принтер) значения исходных данных и результатов.

Решение

Программа вычисления функции Y:

20 REM ВЫВОД НА ПЕЧАТЬ 30 PRINT "ВВЕСТИ А, В"
40 INPUT А, В 50 У=А Л 2+В Л 2
60 LPRINT "ДАННЫЕ:"," А=";А;" В=";В 70 LPRINT
80 LPRINT "РЕЗУЛЬТАТ:"," Y=";Y 90 END

Оператор в 30-й строке этой программы выводит текст на экран дисплея, а операторы 60-80 - на принтер. Оператор в 70-й строке печатает пустую строку на листе бумаги.

Линейные программы с массивами

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

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

Внимание! В Бейсике отсутствуют операции обработки массивов в целом, т.е. операции вида «ввести массив Р(1:99)», которые мы привыкли использовать в главах 8 и 9. Для выполнения операции над массивом необходимо перечислить операции, выполняемые над каждым его элементом.

Рассмотрим общий вид элемента массива в Бейсике:

- элемент одномерного массива: (к);
- элемент двумерного массива: (i,j),

где - имя массива, должно отвечать тем же правилам, что и имя простой переменной;

к - индекс (номер) элемента одномерного массива, к

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

Примеры записи элементов массива:

Р$(0), С2(101) , X(4 б,5*К+1) , Т%(N/2, М) .

В схеме алгоритма те же элементы имели бы такие обозначения: Р 0 ,

С2ю1, X46,5?+i, T w /2>m-

Внимание! Если в программе используется массив, то он должен быть предварительно объявлен, т.е. ЭВМ должна быть сообщена информация о типе и размерах этого массива с помощью оператора DIM.

Пример: оператор DIM Р$(6), i_iB% (4,8) сообщает о наличии в программе

текстового Р(0:6) и целого В(0:4, 0:8) массивов.

Исходя из информации, содержащейся в операторе DIM, ЭВМ выделяет (резервирует) для каждого массива область памяти требуемого размера.

Общий вид оператора DIM:

В случае одномерного массива:

DIM (d) ,

В случае двумерного массива:

DIM (п, ш)

где DIM - имя оператора (от слова dimension - «размерность»); - имя массива; d, п, ш - размеры массива, т.е. d - номер последнего элемента одномерного массива; n(m) - номер последней строки (последнего столбца) двумерного массива.

Размер массива выражается в большинстве версий Бейсика {в том числе в QBASIC) целым числом или целой переменной.

Особенности записи оператора DIM:

1) в одном операторе DIM можно объявлять любое число массивов (см. пример);
2) оператор DIM рекомендуется помещать в начале программы;
3) не следует использовать в программе простую переменную и массив с одним и тем же именем.

Пример: оператор DIM D% (2), А (2,3), К$ (3) сообщает:

массив D% - одномерный целый, содержащий элементы D%(0), D%(1), D%(2);
массив К - одномерный текстовой, включает элементы К$(0), к$(1), К$(2), К$(3);
массив А - двумерный вещественный, включает такие элементы:

Составление линейных программ с массивами. Прежде всего отметим особенности работы с массивами в программе.

1. Элементы массивов получают значения с помощью операторов ввода или присваивания как простые переменные. При вводе (выводе) массивов в операторах ввода (вывода) перечисляются имена всех вводимых (выводимых) элементов массива.

Пример: программа ввода и вывода массива Р (1:3) может иметь такой вид:

20 DIM Р(3)
30 INPUT Р(1), Р(2), Р (3)
40 PRINT Р(1), Р(2), Р(3)
50 END
2. Все массивы можно разделить на два вида:
- массивы постоянного размера (например, Р(1:7), В(1:4, 1:8)];
- массивы переменного размера [например, А(1:&); С(1 :т, 1: d). В главах 8 и 9 мы использовали оба вида, не делая различий между ними.

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

Следует только помнить: переменные - размеры массивов должны быть определены до обращения к оператору DIM.

Пример:

10 INPUT М 20 DIM Х(М)

Линейные программы с массивами составляются в соответствии с рассмотренным ранее правилом составления простейших программ, которое можно дополнить одним пунктом - «после оператора REM следует записать в программе оператор DIM». Кроме того, необходимо учитывать только что изложенные сведения о работе с массивами.

Теперь покажем построение рассматриваемых программ на конкретных примерах. Для начала вернемся к задаче 8.5. Схема алгоритма ее приведена на рис. 10.11. Заменив каждый блок этой схемы соответствующим оператором согласно правилу, приведенному в 12.2, и добавив оператор DIM, получим программу, приведенную ниже. После ознакомления с этой программой рекомендуем читателю самому составить программу решения задачи 10.7 и сравнить ее с приведенной ниже:

10 REM СУММА
20 DIM В(3, 3), S (2)
30 PRINT "ВВЕСТИ МАТР. В(3, 3)"
4 0 INPUT В(1, 1), В(1, 2), В(1, 3)
50 INPUT В (2, 1), В (2, 2), В(2, 3)
60 INPUT В(3, 1), В(3, 2), В(3, 3)
70 S(l) =В (1, 1)+В(1, 2) +В (1, 3)
80 S (2) =В (1, 3) +В (2, 3)+В(3, 3)
90 PRINT "S(1)="; S (1); "S(2)=";
S (2)
100 END
10 REM СДВИГ 20 DIM В(4)
30 PRINT "ВВЕСТИ МАССИВ В (4) "
40 INPUT В(1), В(2),

50 D=B(1)
60 В(1)=В(2)
70 В(2)=В(3)
80 В(3)=В (4)
90 В(4)=D
100 PRINT "МАССИВ В=(";
110 PRINT В(1); В(2);

В (3) ; В (4) ; ") "

Контрольные вопросы

1. Какой оператор в Бейсике указывает тип и размеры массива?
2. Каково обозначение элементов массива в Бейсике? Каково наименьшее значение индекса элемента массива?

Задачи для самостоятельного решения

2. Вычислить среднее арифметическое переменных В, Си И.
3. Рабочие Иванов и Петров изготовили за смену А и В деталей соответственно, перевыполнив норму. Определить процент перевыполнения нормы (норма - С деталей в смену).
4. Определить разницу в возрасте невест для двух братьев Пети и Димы. Их возраст а и Ь соответственно. Возраст невесты определяется по формуле

где (7 - возраст жениха.

5. Вычислить значение у:

где

Примем кф 0; г,Ф 0.

6. Вычислить объем и площадь поверхности цилиндра диаметром О и высотой Н.
7. Вычислить стоимость мебельного гарнитура, содержащего четыре стула, два кресла и один стол. Стоимость изделий соответственно А, В и С руб.
8. Определить среднее арифметическое элементов массива С(1:5).
9. Определить произведение сумм элементов каждой строки матрицы Р(1:2, 1:3).
10. Переставить соответствующие элементы первой и второй строк матрицы А(1:2, 1:2).
11. Переставить элементы массива Я(1: 6): 1-й элемент и 6-й, 2-й и 5-й, 3-й и 4-й.

15. Аналитические методы. Методы линейного программирования.

15.1. Аналитические методы

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

Наилучшие в определенном смысле решения задач принято называть оптимальными . Без использования принципов оптимизации в настоящее время не решается ни одна более или менее сложная проблема. При постановке и решении задач оптимизации возникают два вопроса: что и как оптимизировать?

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

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

Составной частью методов оптимизации является линейное программирование.

15.2. Основные понятия линейного программирования

Первое упоминание (1938 г.) о математических методах в эффективном управлении производством принадлежит советскому математику Л. В. Канторовичу. Год спустя,в 1939 г., Л. В. Канторович опубликовал работу «Математические методы организации и планирования производства» и практически применил полученные результаты. Термин «линейное программирование» ввели американские математики Дж. Данциг и Т. Купманс в конце 40-х годов. Дж. Данциг разработал математический аппарат симплексного метода решения задач линейного программирования (1951 г.). Симплексный метод находит применение для решения широкого круга задач линейного программирования и до настоящего времени является одним из основных методов.

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

быть единственным для данной задачи;

измеряться в единицах количества;

линейно зависеть от входных параметров.

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

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

при ограничениях в виде равенств:

(2.2)

при ограничениях в виде неравенств:

(2.3)

и условиях неотрицательности входных параметров:

В краткой форме задача линейного программирования может быть записана так:

(2.5)

при условии

где
- входные переменные;

Числа положительные, отрицательные и равные нулю.

В матричной форме эта задача может быть записана так:

Задачи линейного программирования можно решить аналитически и графически.

15.3. Каноническая задача линейного программирования

, i=1,…,m,

, j=1,…,n.

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

15.4. Общая задача линейного программирования

Необходимо максимизировать (минимизировать) линейную функцию от n переменных.

при ограничениях

, i =1,…, k ,

, i =1+ k ,…, m ,

, …,

Здесь k ≤ m , r ≤ n . Стандартная задача получается как частный случай общей при k = m , r = n ; каноническая – при k =0, r = n .

Пример.

Кондитерская фабрика производит несколько сортов конфет. Назовем их условно "A", "B" и "C". Известно, что реализация десяти килограмм конфет "А" дает прибыль 90 рублей, "В" - 100 рублей и "С" - 160 рублей. Конфеты можно производить в любых количествах (сбыт обеспечен), но запасы сырья ограничены. Необходимо определить, каких конфет и сколько десятков килограмм необходимо произвести, чтобы общая прибыль от реализации была максимальной. Нормы расхода сырья на производство 10 кг конфет каждого вида приведены в таблице 1.

Таблица 1. Нормы расходов сырья

на производство

Экономико-математическая формулировка задачи имеет вид

Найти такие значения переменных Х=(х1, х2, х3) , чтобы

целевая функция

при условиях-ограничениях:

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

Оператор присваивания. Он задает или изменяет текущее значение некоторой переменной. При этом изменяется содержание конкретного элемента памяти, отведенного для этой переменной. Поскольку цель любого алгоритма - это получение в определенном месте памяти нужного значения, практически любая программа содержит этот оператор. Операторы ввода-вывода. Стандартные процедуры ввода данных используются для определения начальных значений определенных переменных и состоят из имени процедуры и списка ввода, содержащий имена переменных, значения которых будут вводиться с клавиатуры или из файла, т.е. переменным будут присваиваться какие-то определенные значения.
Чаще для определения начальных значений удобнее пользоваться командой ввода, а не командой присваивания, потому что при необходимости использования программы с другими исходными данными не приходится менять текст программы.
Если в записи алгоритма стоит команда ввода, то его выполнение прерывается и управление передается программе, которая может осуществить ввод данных. После ввода данных управление передается следующей команде алгоритма.
На языке Паскаль процедура ввода данных имеет вид:
READ (список ввода);
READLN (список ввода).
При выполнении процедур READ и READLN программа переходит в состояние ожидания ввода данных. Если в списке ввода указано несколько переменных, то их можно вводить в одной строке, отделяя друг от друга символом «пробел», или в отдельных строках (в столбик), завершая ввод каждого значения клавишей Enter.
Работа процедуры не завершится, пока не будут введены значения для всех переменных, указанных в списке. Тип вводимых значений, должно совпадать с тем, который имеет соответствующая переменная.
Оператор READLN отличается от оператора READ тем, что после введения необходимого числа данных курсор перемещается на следующую строку.
Если ввод данных осуществляется с клавиатуры, то список ввода - это список переменных, т.е. последовательность имен переменных, разделенных запятыми. Если ввод осуществляется из файла, то в списке ввода первая переменная - файловая, связана с именем реального файла.
Стандартные процедуры вывода результатов вычислений используются для вывода их значений на экран, принтер или в файл. На языке Паскаль процедуры вывода имеют вид:
WRITE (список вывода);
WRITELN (список вывода).
Список элементов вывода значительно шире, чем в процедурах ввода. В него могут входить:
идентификаторы величин, значения которых будут выводиться на соответствующее устройство или в файл;
выражения, значение которых сначала будут вычислены, а затем выведены на устройство;
стали величины (числовые, символьные, строковые).
Различие между WRITE и WRITELN заключается в том, что вывод оператором WRITE начинается с текущего местоположения курсора на экране монитора и курсор после окончания вывода остается в той же строке. Оператор WRITELN выводит значения с текущего места, а затем курсор перемещается на следующую строку. Можно использовать оператор WRITELN без списка вывода для перемещения курсора на новую строку.
Если вывод осуществляется на экран монитора, то список вывода - это список переменных, или последовательность имен переменных, констант или выражений, разделенных запятыми. Если вывод осуществляется в файл, то в списке вывода первая переменная - файловая, связана с именем реального файла.
В команде вывода после элемента списка вывода через двоеточие можно указать формат вывода, т.е. ширину экрана, на котором будут располагаться значения. При выводе действительных данных можно указать также количество десятичных цифр в дробной части, которую нужно вывести на экран.
Пример: write (А: 10: 3, В: 8).
Оператор вызова вспомогательного алгоритма. В Паскале реализовано подпрограммы-процедуры и подпрограммы-функции. Вызов подпрограммы осуществляется по ее имени с указанием фактических параметров. При этом на месте фактических аргументов могут быть конкретные значения, имена фактических переменных, выражения, а на месте результатов - только имена фактических переменных. При этом количество, типы и назначение формальных и фактических параметров в соответствующих списках параметров должны совпадать.