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

Некоторый однородный продукт, сосредоточенный у т поставщиков Ai в количестве аi {I = 1, 2, ..., т) единиц соответственно необходимо доставить п потребителям Вj, в количестве bj (j = 1,2, ..., п) ед.

Из­вестна стоимость Сij перевозки единицы груза от i-го поставщика к j-му потребителю.

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

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

Составим математическую модель задачи. Так как от i-го поставщи­ка к j-му потребителю запланировано к перевозке хij единиц груза,

то стоимость перевозки составит Сijхij. Стоимость всего плана выра­зится двойной суммой:

Z=

Систему ограничений получаем из следующих условий задачи:

а) все грузы должны быть вывезены, т. е. (i=1,2, ...m)

) все потребности должны быть удовлетворены, т. Е .

Таким образом, математическая модель транспортной задачи име­ет следующий вид. '

Найти наименьшее значение линейной функции

Z=

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

(i=1,2, ...m)

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

Такая модель называется закрытой.

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

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

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

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

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

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

Общая задача нелинейного программирования (ОЗНП) оп­ределяется как задача нахождения максимума (или минимума) целевой функции f(x_{, х₂,..., х_п) на множестве D, определяемом системой ограничений

(2.1)

где хотя бы одна из функций f или g_i является нелинейной.

По аналогии с линейным программированием ЗНП однознач­но определяется парой (D,f) и кратко может быть записана в следующем виде

(2.2)

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

Как и в ЗЛП, вектор называется допус­тимым планом, а если для любого xD выполняется неравен­ство , то х^* называют оптимальным планом. В этом случае х^* является точкой глобального максимума.

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

Задача (2.2) является весьма общей, т. к. допускает запись логических условий, например:

или запись условий дискретности множеств:

Набор ограничений, определяющих множество D, при необ­ходимости всегда можно свести либо к системе, состоящей из одних неравенств:

либо, добавив фиктивные переменные у, к системе уравнений:

Перечислим свойства ЗИП, которые существенно усложня­ют процесс их решения по сравнению с задачами линейного про­граммирования:

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

2. Глобальный максимум (минимум) может достигаться как внутри множества D, так и на его границах (где он, вообще гово­ря, будет не совпадать ни с одним из локальных экстремумов).

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

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

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

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

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

Рассмотрим несколько примеров решения задач графическим методом. Пример 10.1.

Построим область допустимых решений (рис. 10.1):

На этом же графике построим одну из семейства целевых функций, для этого преобразуем Z в каноническую форму Получим уравнение эллипса с полуосями Полагая Z = 16, имеем b = 4; a =2,8. Согласно чертежу максимальное значение Z достигается в точке (0;0) Zmax=2*25+49=99; Zmin достигается в точке D, в которой эллипс касается области ОАВС. Для нахождения координат точки D приравняем угловые коэффициенты первой прямой и целевой функции: y=-1/2x-6; 0=4(x-5)+2(y-7)y1; y1= -(2(x-5))/(y-7); -1/2= -(2(x-5))/(y-7); упрощая, получим: 4(x-5)= y-7.

Решая совместно систему находим координаты точки D(38/9; 35/9). Zmin=2*(38/9-5)^2+(35/9-7)^2=11.

6. Операцио́нная систе́ма, ОС (англ. operating system) — базовый комплекс компьютерных программ, обеспечивающий интерфейс с пользователем, управление аппаратными средствами компьютера, работу с файлами, ввод и вывод данных, а также выполнение прикладных программ и утилит.

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

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

Существуют две группы определений ОС: «совокупность программ, управляющих оборудованием» и «совокупность программ, управляющих другими программами». Обе они имеют свой точный технический смысл, который, однако, становится ясен только при более детальном рассмотрении вопроса о том, зачем вообще нужны операционные системы. Есть приложения вычислительной техники, для которых ОС излишни. Напр., встроенные микрокомпьютеры содержатся сегодня во многих бытовых приборах, автомобилях (иногда по десятку в каждом), сотовых телефонах и т. п. Зачастую такой компьютер постоянно исполняет лишь одну программу, запускающуюся по включении. И простые игровые приставки — также представляющие собой специализированные микрокомпьютеры — могут обходиться без ОС, запуская при включении программу, записанную на вставленном в устройство «картридже» или компакт-диске. Тем не менее, некоторые микрокомпьютеры и игровые приставки всё же работают под управлением особых собственных ОС. В большинстве случаев, это UNIX-подобные системы (последнее особенно верно в отношении программируемого коммутационного оборудования: фаерволов, маршрутизаторов).

Операционные системы, в свою очередь, нужны, если:

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

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

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

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

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

использующие файловые системы (с универсальным механизмом доступа к данным),

многопользовательские (с разделением полномочий),

многозадачные (с разделением времени).

Многозадачность и распределение полномочий требуют определённой иерархии привилегий компонентов самой ОС. В составе ОС различают три группы компонентов:

ядро, содержащее планировщик; драйверы устройств, непосредственно управляющие оборудованием; сетевую подсистему, файловую систему;

системные библиотеки и

оболочка с утилитами.

Большинство программ, как системных (входящих в ОС), так и прикладных, исполняются в непривилегированном («пользовательском») режиме работы процессора и получают доступ к оборудованию (и, при необходимости, к другим ядерным ресурсам, а также ресурсам иных программ) только посредством системных вызовов. Ядро исполняется в привилегированном режиме: именно в этом смысле говорят, что ОС (точнее, её ядро) управляет оборудованием.

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

8. (Задача нелінійного програмування в 5 питанні.) Оптимизационные задачи для выпуклых функ­ций. Общим недостатком рассмотренных выше методов безус­ловной оптимизации было, с одной стороны, то, что они позволя­ют отыскивать только точки, подозрительные на локальный экстремум, а с другой — то, что найденные решения могут суще­ственно зависеть от начального приближения. Поиск глобально­го оптимума подразумевает перебор найденных точек, который, в случае градиентных методов, может быть осуществлен за счет подбора соответствующих начальных приближений х⁽⁰⁾.

Рис. 2.1 Рис. 2.2

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

►Функция называется выпуклой в области D, если для любых двух точек и любо­го выполняется неравенство

(2.14)

если же

(2.15)

то функция называется вогнутой.

Геометрический смысл понятий выпуклости и вогнуто­сти для случая функции одной переменной представлен на рис. 2.3. Из него, в частности, видно, что график выпуклой функ­ции лежит ниже отрезка, соединяющего точки и , а график вогнутой — выше.

Рис. 2.3

Можно доказать, что достаточным условием выпуклости функции является положительная определен­ность матрицы

называемой также матрицей Гессе, во всех точках xD. Со­ответственно, достаточным условием вогнутости являет­ся отрицательная определенность матрицы Гессе. В част­ности, для функций одной переменной достаточным условием выпуклости (вогнутости) является выполнение неравенства .

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

Теорема 2.2. Если f(x) выпуклая (вогнутая) на Rⁿ функция и , то х^* — точка глобального мини­мума (максимума).

Доказательство.

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

Пусть х — произвольная точка, отличная от точки х^*. Тогда, для любого , в силу вогнутости функции f(x) будет вы­полняться

из чего следует

Если ввести вектор l = х — х^* и обозначить , то длина вектора будет равна . Следовательно,

Устремив и учитывая, что вектор l сонаправлен с , получим

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

Следовательно, для любой точки х, не равной х^*, справедли­во неравенство , т.е. х* — точка гло­бального максимума. ▲

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