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

Наиболее простым и наглядным методом линейного программирования (ЛП) является графический метод. Он применяется для решения задач ЛП с двумя переменными. Рассмотрим задачу ЛП в стандартной форме:

max f(x 1 , x 2 , ..., x n) = ,

, i = 1, 2, …, m,

x j 0, j = 1, 2, …, n.

Положим n=2 и будем рассматривать задачу на плоскости. Пусть система неравенств совместна (имеет хотя бы одно решение).

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой а i 1 х 1 + а i 2 х 2 = b i , i = 1, 2,…, m. Условия неотрицательности определяют полуплоскости с гра­ничными прямыми х 1 = 0, х 2 = 0 соответственно. Система со­вместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, где ко­ординаты каждой точки являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, ограниченным и неограни­ченным многоугольником.

Таким образом, геометрически ЗЛП представляет собой отыс­кание такой точки многоугольника решений, координаты которой доставляют линейной функции цели максимальное (минимальное) значение, причем допустимыми решениями являются все точки многоугольника решений.

Линейное уравнение описывает множество точек, лежащих на одной прямой. Линейное неравенство описывает некоторую об­ласть на плоскости. Определим, какую часть плоскости описыва­ет неравенство 2х 1 + Зх 2 12.

Во-первых, построим прямую 2х 1 + Зх 2 = 12. Она проходит через точки (6; 0) и (0; 4). Для того чтобы определить, какая полуплоскость удовлетворяет неравенству, необходимо выбрать любую точку на графике, не принадлежащую прямой, и подставить ее координаты в неравенство. Если неравенство будет вы­полняться, то данная точка является допустимым решением, и полуплоскость, содержащая точку, удовлетворяет неравенству. Для подстановки в неравенство удобно использовать точку начала координат. Подставим х 1 = х 2 = 0 в неравенство 2х 1 + Зх 2 12. Получим 2х0 + 3х0 12. Данное утверждение является верным, следовательно, неравенству 2х 1 + Зх 2 12 соответствует нижняя полуплоскость, содержащая точку (0; 0). Это отражено на графике, изображенном на рис. 1.1.

Аналогично графически можно изобразить все ограничения задачи ЛП.

Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений, или областью определения. Необходимо помнить, что область допустимых решений удовлетворяет условиям неотрицательности (х j 0, j = 1, 2, …, n). Координаты любой точки, принадлежащей области определения, являются допустимым решением задачи.

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

Этот вектор показывает направление наискорейшего измене­ния целевой функции. Прямая с 1 х 1 + с 2 х 2 = f(х 0) , перпендикуляр­ная вектору-градиенту, является линией уровня целевой функции. В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине «а» . Меняя значение «а», получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.

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

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

Графический метод решения ЗЛП состоит из следующих этапов.

1. Строится многоугольная область допустимых решений (ОДР) ЗЛП.

2. Строится вектор-градиент целевой функции (ЦФ) в какой-нибудь точке х 0 , принадлежащей ОДР:

3. Линия уровня с 1 х 1 + с 2 х 2 = а (а - постоянная величина) - прямая, перпендикулярная вектору-градиенту , - передви­гается в направлении этого вектора в случае максимизации f(x 1 , х 2) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точ­кой максимума f(x 1 , х 2).

4. Для нахождения координат точки максимума достаточно решить два уравнения прямых, получаемых из соответствую­щих ограничений и дающих в пересечении точку максимума. Значение f(x 1 , х 2), найденное в получаемой точке, является мак­симальным.

При минимизации (максимизации) функции f(x 1 , х 2) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая, соответствующая линии уровня, при своем движении не покидает ОДР, то минимум (максимум) функ­ции f(x 1 , х 2) не существует.

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

Таблица 1.3

№	Вид ОДР	Вид оптимального решения	Примечания
	Многоугольная замкнутая	Единственное решение
	Единственное решение
	Многоугольная	ЦФ не ограничена снизу
	ЦФ не ограничена сверху
	Многоугольная незамкнутая	Единственное решение
	Бесконечное множество решений
	Отрезок	Единственное решение

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

Пример 1.1. Планирование выпуска продукции пошивочного предприятия (задача о костюмах).

Намечается выпуск двух видов костюмов – мужских и женских. На женский костюм требуется 1м шерсти, 2м лавсана и 1 чел./день трудозатрат. На мужской костюм – 3,5м шерсти, 0,5м лавсана и 1 чел./день трудозатрат. Всего имеется 350м шерсти, 240м лавсана и 150 чел./дней трудозатрат. Требуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского – 20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.

Введем следующие обозначения: х 1 - число женских костюмов; х 2 – число мужских костюмов. Прибыль от реализации женских костюмов составляет 10х 1 , а от реализации мужских - 20х 2 , т.е. необходимо максимизировать целевую функцию:

10х 1 + 20х 2

Ограничения задачи имеют вид:

х 1 + х 2 150,

2 х 1 + 0,5х 2 240,

х 1 + 3,5х 2 350,

х 2 60,

х 1 0.

Первое ограничение по труду х 1 + х 2 150. Прямая х 1 + х 2 = 150 проходит через точки (150; 0) и (0; 150) (рис. 1.2).

Второе ограничение по лавсану 2 х 1 + 0,5х 2 240. Прямая 2 х 1 + 0,5х 2 = 240 проходит через точки (120; 0) и (0; 480). Третье ограничение по шерсти х 1 + 3,5х 2 350. Добавим четвертое ограничение по количеству мужских костюмов х 2 60. Решением этого неравенства является полуплоскость, лежащая выше прямой х 2 = 60. На рис. 1.3 заштрихована область допустимых решений. Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными целевой функции, т.е.

Чтобы построить такой вектор, нужно соединить точку (10;20) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации – в противоположном направлении. Для удобства можно строить вектор, пропорциональный вектору . Так, на рис. 1.4 изображен вектор-градиент (30;60).

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

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

х 1 + 3,5х 2 = 350,

х 1 + х 2 = 150.

Отсюда легко записать решение исходной ЗЛП: max f(x) = 2300 и достигается при х 1 = 70 и х 2 = 80 (см. рис. 1.4).

1.3.ТЕХНОЛОГИЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ НАДСТРОЙКИ ПОИСК РЕШЕНИЯ В СРЕДЕ EXCEL

1.3.1. Общие сведения о работе с табличным процессором Excel

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

Элементы экрана Excel. После запуска Excel на экране появля­ется таблица, вид которой показан на рис 1.5.

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

Работа с формулами. В программах электронных таблиц формулы служат для выполнения множества разнообразных расчетов. С помощью Excel можно быстро создать формулу. Формула состоит из трех основных частей:

1) знака равенства;

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

3) операторов.

4) Если знак равенства отсутствует, то Excel интерпретирует данные не как формулу, а как ввод данных в ячейку. Формулы можно вводить непосредственно в ячейку или в строку формул – как текст, так и число. При этом нужно выполнить следующие действия:

· выделить ячейку, которая должна содержать формулу и ввести знак (=);

· ввести оператор или знак действия;

· выделить другую ячейку, включаемую в формулу;

· нажать на клавишу Enter.

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

Использование в формулах функций. Чтобы облегчить ввод формул, можно воспользоваться функциями Excel. Функции - это встроенные в Excel формулы. Excel содержит множество формул. Они сгруппированы по различным типам: логические, математи­ческие, инженерные, статистические и др.

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

Различные функции выполняют разные типы вычислений по определенным правилам. Когда функция является единичным объектом в ячейке рабочего листа, она начинается со знака (=), далее следует название функции, а затем - аргументы функции, заключенные в скобки.

Поиск решения - это надстройка Excel, которая позволяет решать оптимизационные задачи. Если в меню Сервис отсутствует коман­да Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду Сервис => Надстройки и активизируйте над­стройку Поиск решения. Если же этой надстройки нет в диалоговом окне Надстройки, то вам необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и уда­ление программ и с помощью программы установки Excel (или Office) установить надстройку Поиск решения.

После выбора команд Сервис => Поиск решения появится диало­говое окно Поиск решения.

В диалоговом окне Поиск решения есть три основных пара­метра;

Установить целевую ячейку.

Изменяя ячейки.

Ограничения.

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

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

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

Для решения задачи необходимо:

1) указать адреса ячеек, в которые будет помещен результат реше­ния (изменяемые ячейки);

2) ввести исходные данные;

3) ввести зависимость для целевой функции;

4) ввести зависимости для ограничении,

5) запустить команду Поиск решений;

6) назначить ячейку для целевой функции (установить целевую ячейку);

7) ввести ограничения;

8) ввести параметры для решения ЗЛП.

Рассмотрим технологию решения, используя условия примера 1.1 (задача о костюмах).

Экономико-математическая модель задачи

Пусть х 1 - число женских костюмов; х 2 - число мужских костюмов,

10 х х 1 + 20 х х 2 max

Ограничения задачи имеют вид:

х 1 + х 2 150 - ограничение по труду;

2 x х 1 + 0,5 х х 2 240 - ограничение по лавсану;

х 1 + 3,5 х х 2 350 - ограничение по шерсти;

х 2 60 - ограничение по мужским костюмам;

х 1 0 - ограничение по женским костюмам.

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

Обозначьте через x 1 , х 2 количество костюмов каждого типа. В нашей задаче оптимальные значения вектора = (х 1 , х 2) будут помещены в ячейках А2:В2, оптимальное значение целевой функ­ции - в ячейке СЗ.

2. Ввести исходные данные.

Введите исходные данные задачи, как показано на рис. 1.6.

3. Ввести зависимость для целевой функции.

· Поместить курсор в ячейку «СЗ», произойдет выделение ячейки.

· Поместить курсор на кнопку Мастер функций, расположенную на панели инструментов.

· Ввести Enter. На экране появляется диалоговое окно Мастер функ­ций шаг 1 из 2.

· В окне Функции выбрать строку СУММПРОИЗВ (рис. 1.7). На экране

· появляется диалоговое окно СУММПРОИЗВ (рис. 1.8).

· В строку Массив 1 ввести А2:В2 .

· В строку Массив 2 ввести АЗ:ВЗ.

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

5. Ввести зависимости для ограничений (рис 1.10).

· Поместить курсор в ячейку СЗ.

· На панели инструментов кнопка Копировать в буфер.

· Поместить курсор в ячейку С4.

· Поместить курсор в ячейку С5.

· На панели инструментов кнопка Вставить из буфера.

· Поместить курсор в ячейку Сб.

· На панели инструментов кнопка Вставить из буфера.

· Поместить курсор в ячейку С7.

· На панели инструментов нажать кнопку Вставить из буфера. (Содержимое ячеек С4-С7 необходимо проверить. Они обяза­тельно должны содержать информацию, как это показано для примера на рис. 1.11; в качестве примера представлено содер­жимое ячейки С5.)

· В строке Меню указатель мышки поместить на Сервис. В развер­нутом меню выбрать команду Поиск решения. Появляется диа­логовое окно Поиск решения (рис. 1.12).

5. Запустить команду Поиск решения.

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

· Поместить курсор в строку Установить целевую ячейку.

· Ввести адрес ячейки $С$3.

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

· Поместить курсор в строку Изменяя ячейки.

· Ввести адреса искомых переменных А$2:В$2 (рис. 1.13).

7. Ввести ограничения.

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

· Ввести знак ограничения.

· В строке Ограничение ввести адрес $D$4 (рис. 1.14).

· Поместить указатель мыши на кнопку Добавить. На экране вновь появится диалоговое окно Добавление ограничения.

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

· После введения последнего ограничения нажать на кнопку ОК. На экране появится диалоговое окно Поиск решения с введенны­ми условиями (рис. 1.15).

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

· В диалоговом окне поместить указатель мышки на кнопку Пара­метры. На экране появится диалоговое окно Параметры поиска решения (рис. 1.16).

· Установить флажки в окнах Линейная модель (это обеспечит применение симплекс-метода) и Неотрицательные значения.

· Поместить указатель мыши на кнопку ОК. На экране появится диалоговое окно Поиск решения.

· Поместить указатель Мыши на кнопку Выполнить.

Через непродолжительное время появятся диалоговое окно Результаты поиска решения и исходная таблица с заполненными ячейками АЗ:ВЗ для значений х i и ячейка СЗ с максимальным значением целевой функции (рис. 1.17).

Если указать тип отчета Устойчивость, то можно получить до­полнительную информацию об оптимальном решении (рис. 1.18).

В результате решения задачи был получен ответ: необходимо сшить 70 шт. женских костюмов и 80 шт. мужских костюмов, чтобы получить максимальную прибыль 2300 у.е.

1.4. ДВОЙСТВЕННОСТЬ В ЗАДАЧАХ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. АНАЛИЗ ПОЛУЧЕННЫХ ОПТИМАЛЬНЫХ РЕШЕНИЙ

В 1975 г. наш соотечественник Л.В. Канторович был удостоен Нобелевской премии по экономике (совместно с американским экономистом Т. Купмансом) за разработку теории оптимального использования ресурсов (см. Приложение 1).

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

Переменные двойственной задачи y i называются объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.

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

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

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

2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная мат­рица А Т в двойственной задаче получаются друг из друга транс­понированием;

3) число переменных в двойственной задаче равно числу функци­ональных ограничений исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной;

4) коэффициентами при неизвестных в целевой функции двой­ственной задачи являются свободные члены в системе ограни­чений исходной задачи, а правыми частями в ограничениях двойственной задачи - коэффициенты при неизвестных в це­левой функции исходной; j 0.

Две приведенные задачи образуют пару симметричных двой­ственных задач. Основные утверждения о взаимно двойственных задачах содержатся в двух следующих теоремах.

Первая теорема двойственности. Для взаимно двойственных за­дач имеет место один из взаимоисключающих случаев.

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

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

3. В двойственной задаче допустимое множество не пусто, а целе­вая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.

4. Обе из рассматриваемых задач имеют пустые допустимые мно­жества.

Вторая теорема двойственности (теорема о дополняющей неже­сткости). Пусть = (x 1 ,х 2 ,..., х п) - допустимое решение прямой задачи, a = (у 1 ,у 2 ,…,у т) - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соот­ветственно прямой и двойственной задач, необходимо и достаточ­но, чтобы выполнялись следующие соотношения:

(1.4)

(1.5)

Условия (1.4) и (1.5) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное реше­ние другой задачи.

Рассмотрим еще одну теорему, выводы которой будут исполь­зованы в дальнейшем.

Теорема об оценках. Значения переменных y i в оптимальном реше­нии двойственной задачи представляют собой оценки влияния сво­бодных членов b i системы ограничений (неравенств) прямой задачи на величину

Решая ЗЛП симплекс-методом, мы одновременно решаем двой­ственную ЗЛП. Переменные двойственной задачи y i называют объективно обусловленными оценками.

Рассмотрим экономическую интерпретацию двойственной за­дачи на примере задачи о коврах.

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

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

2. Используя Поиск решения, найти такой план выпуска продук­ции, при котором общая стоимость продукции будет макси­мальной.

3. Сформулировать экономико-математическую модель двой­ственной задачи к задаче о коврах.

4. Найти оптимальный план двойственной задачи, используя теоремы двойственности, пояснить равенство нулю Х 1 и Х 4 .

5. Используя протоколы Поиска решения, выполнить анализ по­лученного оптимального решения исходной задачи.

6. Определить, как изменится общая стоимость и план выпуска продукции при увеличении запаса ресурса труб на 12 ед.

1. Сформулируем экономико-математическую модель задачи.

Обозначим через Х 1 , Х 2 , Х 3 , Х 4 число ковров каждого типа. Целевая функция имеет вид

F(X) = ЗХ 1 + 4Х 2 + ЗХ 3 + Х 4 max,

а ограничения по ресурсам

7Х 1 + 2Х 2 + 2Х 3 + 6Х 4 80,

5Х 1 + 8Х 2 + 4 Х 3 + ЗХ 4 480,

2Х 1 + 4 Х 2 + Х 3 + 8X 4 130,

Х 1 , X 2 , X 3 , Х 4 0.

2. Поиск оптимального плана выпуска.

Решение задачи выполним с помощью надстройки Excel Поиск решения. Технология решения задачи была подробно рассмотрена в задаче о костюмах. В нашей задаче оптимальные значения вектора Х=(Х 1 , X 2 , X 3 , Х 4) будут помещены в ячейках ВЗ:ЕЗ, оптимальное значение целевой функции - в ячейке F4 .

Введем исходные данные. Сначала опишем целевую функцию с помощью функции - СУММПРОИЗВ (рис. 1.19). А потом введем данные для левых частей ограничений. В Поиске решения введем направление целевой функции, адреса искомых переменных, до­бавим ограничения. На экране появится диалоговое окно Поиск решения с введенными условиями (рис. 1.20).

После ввода параметров для решения ЗЛП следует нажать кнопку Выполнить. На экране появится сообщение, что решение найдено (рис. 1.21).

Полученное решение означает, что максимальный доход 150 тыс. руб. фабрика может получить при выпуске 30 ковров второго вида и 10 ковров третьего вида. При этом ресурсы «труд» и «оборудование» будут использованы полностью, а из 480 кг пряжи (ресурс «сырье») будет использовано 280 кг.

Создание отчета по результатам поиска решения. Excel позволяет представить результаты поиска решения в форме отчета (табл. 1.4). Существует три типа таких отчетов:

· Результаты (Answer). В отчет включаются исходные и конечные значения целевой и изменяемых ячеек, дополнительные све­дения об ограничениях.

· Устойчивость (Sensitivity). Отчет, содержащий сведения о чувстви­тельности решения к малым изменениям в изменяемых ячей­ках или в формулах ограничений.

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

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

Общая постановка злп

Найти значения n переменных x 1 , x 2 , …,x n , доставляющих экстремум (минимум или максимум) линейной функции Z=C 1 x 1 ,+ C 2 x 2+…+ C n x n

и одновременно удовлетворяющих m ограничениям вида

a 1,1 x 1 +a 1,2 x 2 +…+a 1,n x n £ =≥b 1 ,

a 2,1 x 1 +a 2,2 x 2 +…+a 2,n x n £ = ≥b 2 ,

. . . . . . . . . . . . . . . . . . . . . . .,

a m,1 x 1 +a m,2 x 2 +…+a m,n x n £ = ≥b m ,

при заданных a i,j , b i, C j (i=1,2,…,m; j=1,2,…,n). Знак отношения может принимать любое из трех приведенных значений.

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

Рассмотрим следующую задачу. Менеджер предприятия, изготавливающего два вида красок, описал исследователю операций ситуацию, сложившуюся на производстве и рынке сбыта красок. Оказалось, что фабрика изготавливает два вида красок: для внутренних и внешних работ. Обе краски поступают в оптовую продажу. Для производства красок используются два исходных продукта – А и В. Максимально возможные суточные запасы этих продуктов 6 и 8 тонн соответственно. Опыт показал, что суточный спрос на внешнюю краску никогда не превышает спрос на внутреннюю более чем на 1 тонну. Кроме того, установлено, что спрос на внешнюю краску никогда не превышает 2 тонны в сутки. Оптовые цены одной тонны красок сложились следующим образом: 3 тысячи рублей на внешнюю краску и 2 тысячи рублей – на внутреннюю. Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации был максимальным?

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

При построении математической модели специалист по исследованию операций ставит перед собой три вопроса.

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

Введем переменные:

x 1 – суточный объем производства внешней краски (в тоннах),

x 2 – суточный объем производства внутренней краски (в тоннах).

Учитывая оптовые цены на тонну каждого вида краски, суточный доход от продажи произведенной продукции задается линейной целевой функцией Z = 3x 1 + 2x 2 .

Целью производства является получение максимальной прибыли, значит, необходимо найти значения x 1 и x 2 , которые максимизируют целевую функцию Z.

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

Первый тип ограничений определяется запасами продуктов А и В, из которых производятся краски. Из технологии производства известно, что на производство тонны внешней краски идут две части продукта А, а на тонну внутренней – одна часть. Для продукта В соотношение обратное. Эти технологические условия описываются неравенствами

2x 1 + x 2 £ 6 (на складе 6 тонн продукта А),

x 1 + 2x 2 £ 8 (на складе 8 тонн продукта В).

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

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

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

найти ® max{ Z=2× x 1 + 3× x 2 } при следующих ограничениях на значения переменных x 1 и x 2

2 × x 1 + x 2 £ 6 ограничение (1),

X 1 + 2 × x 2 £ 8 ограничение (2),

X 1 - x 2 £ 1 ограничение (3),

X 1 £ 2 ограничение (4)

и требование неотрицательности переменных x 1 ³ 0 (5), x 2 ³ 0 (6).

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

Графический метод решения злп

Графический метод решения злп может быть реализован только в двумерном случае.

Математическая модель, полученная для сформулированной типовой задачи, требует исследования, так как заранее не известно, имеет ли она (как математическая задача) решение. Исследование проведем с использованием графических построений. Одновременно с таким исследованием найдем (если оно есть) и решение.

1 этап. Построение области допустимых решений

Цель – построить область, каждая точка которой удовлетворяет всем ограничениям.

Каждое из шести ограничений геометрически задает полуплоскость. Для того, чтобы ее построить, нужно:

• · заменить в ограничении знак неравенства на равенство (получим уравнение прямой);

• · построить прямую по двум точкам;

• · определить, какую полуплоскость задает знак неравенства. Для этого подставить в неравенство какую-нибудь точку (например, начало координат). Если она удовлетворяет неравенству – закрашиваем полуплоскость, ее содержащую.

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

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

Множество точек, удовлетворяющих всем шести ограничениям задачи – многоугольник AFEDCB.

2 этап Построение линий уровня целевой функции и определение точки максимума

Цель - найти в построенном многоугольнике A FEDCB точку, в которой функция цели Z=2x 1 + 3x 2 принимает максимальное значение.

Проведем прямую 2x 1 + 3x 2 = Сonst (линию уровня) так, чтобы она пересекала многоугольник AFEDCB (например, Const=10). Эта линия уровня на рисунке изображена пунктирной линией.

Если рассматривать значения линейной целевой функции Z на множестве точек (x 1 ,x 2), принадлежащих отрезку пунктирной прямой, расположенному внутри шестиугольника, то все они равны одному и тому же значению (Const=10).

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

Сдвиг можно продолжать до тех пор, пока перемещаемая прямая пересекает многоугольник допустимых решений. Последнее положение прямой, когда она имеет одну общую точку с многоугольником AFEDCB (точка С), соответствует максимальному значению целевой функции Z и достигается в точке С с координатами x 1 = 4/3 (» 1.333), x 2 =10/3 (» 3.333). При этом Z = 38/3 (» 12.667).

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

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

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

Задание 1 (выполнить на занятии, показать преподавателю)

Решить графическим методом

А) F =2 x 1 +3 x 2 è max При ограничениях x 1 +3 x 2 ≤ 18 2 x 1 + x 2 ≤ 16 x 2 ≤ 5 3 x 1 ≤ 21 x 1 ≥ 0 x 2 ≥ 0	B ) F =4 x 1 +6 x 2 è min При ограничениях 3 x 1 + x 2 ≥ 9 x 1 +2 x 2 ≥ 8 x 1 +6x 2 ≥ 12 x 1 ≥ 0 x 2 ≥ 0
C ) F =3 x 1 +3 x 2 è max При ограничениях x 1 +x 2 ≤ 8 2x 1 -x 2 ≥ 1 x 1 -2x 2 ≤ 2 x 1 ≥ 0 x 2 ≥ 0	D ) F =2 x 1 -3 x 2 è min При ограничениях x 1 +x 2 ≥ 4 2x 1 -x 2 ≥ 1 x 1 -2x 2 ≤ 1 x 1 ≥ 0 x 2 ≥ 0

A) x1=6 x2=4 F=24

B) x1=2 x2=3 F=26

C) x1Î x2=8-x1 F=24

Задание 2 (выполнить на занятии, показать преподавателю)

Ответить на вопросы, выделенные курсивом.

Задание 3 (домашнее)

Написать программу.

Дан текстовый файл вида

2 3 (коэффициенты целевой функции)

4 (количество ограничений)

2 2 12 (ограничения)

1 2 8

4 0 16

0 4 12

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

Построить несколько линий уровня целевой функции (нажимаем клавишу – прямая перемещается, отображается значение целевой функции). Отобразить масштаб.

Важным методом научного анализа статистического материала выступают графические изображения. Первые попытки использования графических методов в экономических исследованиях начались еще в 1780-х годах. Однако более широкого применения графический метод получил позже - в середине XVIII в., Особенно после впервые в истории сделанной статистики докладе представителя Берлинского статистического бюро Швабе "Теория графических изображений" на 8-м Международном статистическом конгрессе (Петербург, 1872 г.). По известному выражению немецкого физика Ф. Ауэрбаха, XX в. ознаменовалось "триумфальной поступью графического метода в науке".

Что же такое график? График - это форма наглядного представления статистических данных о социально-экономические явления и процессы через геометрические образы, рисунки или схематические географические карты и пояснения к ним.

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

Рис. 10.3. Основные элементы графика

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

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

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

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

Экспликация графика - словесное объяснение его конкретного содержания, которое обычно включает:

1) заголовок с необходимыми дополнительными пояснениями;

2) точное объяснение сущности, условно предоставляется в данном графике его графическим знакам (геометрическим, изобразительным, фоновым, чисто условным)

3) другие объяснения, примечания и т.

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

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

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

Для обобщения и анализа данных;

Изображение распределения данных;

Выявление закономерностей развития исследуемых явлений и процессов в динамике;

Отражение взаимосвязей показателей;

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

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

По форме графических образов различают следующие типы графиков:

1) точечные;

2) линейные;

3) плоскостные;

4) объемные;

5) художественные (изобразительные, условные).

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

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

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

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

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

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

Двухмерный "знак Варзара" (по имени его изобретателя русского статистика В.Е. Варзара) - это прямоугольник с основанием а высотой Ь и площадью Sab, который является полезным для графического выражения довольно частых подобных соотношений трех величин a, by S.

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

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

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

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

Большое значение имеет классификация графиков по их содержанию. Учитывая это графики делятся на два класса - диаграммы и статистические карты.

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

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

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

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

Диаграммы и статистические карты выполняют такие важные задачи по исследованию совокупности:

Общее их сравнения;

Изучение структуры;

Изучение динамики;

Изучение взаимосвязей их признаков;

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

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

При построении графиков следует соблюдать следующие требования:

1) опираться на достоверные числовые данные;

2) графики должны быть значимыми по замыслу и интересными по содержанию;

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

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

5) технически хорошо выполненными.

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

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

	Подкласс		Разновидности и графическая форма, чаще всего встречается
Диаграммы	И. Диаграммы общего сравнения совокупностей	1. однородных совокупностей	Колонке, ленточные, художественные
		2. Разнородных совокупностей	Колонке, ленточные, плоскостные
	II. Диаграммы структуры	1. Диаграммы распределения численности	Полигон, гистограмма, кумулята, огива, кривая распределения, график Лоренца, корреляционное поле
		2. Диаграммы группам	Диаграммы из столбиков, лент, разделенных на абсолютные или процентные части, секторные, балансовые диаграммы, "возрастная пирамида» и др.
	III. Диаграммы динамики	1. Диаграммы динамики объемов	Колонке, линейные, кумулятивные, спиральные, художественные диаграммы
		2. Диаграммы динамики структуры	Диаграммы из столбиков с процентным делением, по кругам с разделением на сектора и др.
		3. Диаграммы сезонных колебаний	Линейные, столбиковые, радиальные диаграммы
	IV. Диаграммы взаимосвязей признаков	1. Диаграммы конфигурации совокупности	Точечные, фоновые
		2. Диаграммы формы связи	Диаграммы с ломаных или с плавных кривых
		3. Диаграммы степени тесноты связи	Замкнутые контуры корреляционного поля в виде ступенчатых ломаных или эллипсообразных кривых и т.д.
	V. Диаграммы выполнения планов	1. Диаграммы текущего выполнения	Линейные диаграммы, графики Ганта
		2. Диаграммы выполнения от начала периода	Кумуляты, кумулятивные графики Ганта, графики Лоренца
Статистические карты	VI. Картограммы	1. Картограммы размещения единиц совокупности	Точечные картограммы
		2. Картограммы размещения совокупного объема признаки	Точечные картограммы
		3. Картограммы изменения сводных признаков	Точечные, фоновые картограммы
		4. Изолинийни картограммы	Линейные картограммы
		5. Центрограмы	Точечные картограммы

Таблица 10.28. Инвестиции в основной капитал в жилищное строительство Украины в 2000-2005 pp., В фактических ценах, млн грн

Данные графика свидетельствуют, что объемы инвестиций в основной капитал в жилищное строительство Украины в фактических ценах росли с 2000 в 2005

Рис. 10.4. Динамика объема инвестиций в основной капитал в жилищное строительство Украины в 2000-2005 гг., В фактических ценах, млн грн

Планово-линейные графики строят на специально разработанной сетке, где по горизонтали откладывают единицы времени, а по вертикали размещают объекты исследования. Причем, каждый отрезок по горизонтали соответствует 100% -му выполнению планового задания. Эти отрезки делятся на 5 равных частей, каждая из которых соответствует 20% планового задания.

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

Рассмотрим порядок построения планово-линейного графика на примере.

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

Таблица 10.29. Выполнение планового задания бригадой рабочих из строительно-монтажных работ

График выполнения планового задания бригадой строителей по строительно-монтажных работ представлен на рис. 10.5.

Тонкая непрерывный линия первого дня соответствует 90% выполнения плана и занимает четыре с половиной ячейки, а линия второго дня - 80% и занимает четыре клетки, линия третий день протянулась ровно на пять, а четвертого - на пять ячеек (100%) плюс еще дополнительный отрезок ниже, который занимает 20% и т.п.

Изображение уровня выполнения плана нарастающим итогом требует некоторых дополнительных расчетов. Так, за первый день сплошная жирная линия будет такой длины, как и тонкая непрерывный - 90% и займет четыре с половиной клетки. Далее следует сделать следующие расчеты: за два дня фактически выполнено 513 м 2 (225 + 288). Из этой суммы 250 м 2 относят в счет выполнения плана за первый день. Тогда в счет второго дня останется 263 м 2, что согласно плану в этот день составляет 91% (263 288).

Согласно жирная линия занимает пять ячеек первого дня и 91% второго. За три дня фактически было выполнено 923 м 2 (225 + 288 + 410). В счет выполнения плана первых двух дней записывается 610 м 2, а в счет третьего дня - 313 м 2, что согласно плану на этот день составляет 76% (313: 410). Жирная линия займет по 5 ячеек первого и второго дней и 76% третьему. Аналогично проводятся все дальнейшие расчеты. Степень выполнения плана за каждый день на жирной линии сказывается точками.

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

Высота столбиков должна соответствовать величине изображенных явлений. Если же столбики размещают горизонтально, то такой график называется ленточным (рис. 10.7).

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

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

Как свидетельствуют данные графика (рис. 10.8), основным источником финансирования лизинговых операций в Украине выступают банковские кредиты (80,9%), затем - собственные средства (16,1%). Заемные средства юридических лиц составляют лишь 3,6%.

Рис. 10.6. Динамика объема инвестиций в основной капитал в жилищное строительство Украины в 2000-2005 pp., В фактических ценах, млн грн

Рис. 10.7. Динамика объема инвестиций в основной капитал в жилищное строительство Украины в 2000-2005 pp., В фактических ценах, млн грн

В современных условиях развития информационно-компьютерных систем появилась возможность строить графики с помощью пакетов компьютерных программ, в том числе электронных таблиц EXCEL, "Statistica-6" и др. Они удобны в использовании и значительно упрощают эту работу.

Рис. 10.8. Структура источников финансирования лизинговых операций в Украине на начало 2005 p.,%

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

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

В математически формализованной системе анализа, планирования и управления особое место занимают сетевые графики. Они дают большой экономический эффект при строительстве и монтаже промышленных и других предприятий.
Сетевой график (рис. 6.1) позволяет выделить из всего комплекса работ наиболее важные, лежащие на критическом пути, и сосредоточить на них основные ресурсы строительномонтажных организаций, устанавливать взаимосвязь между различными специализированными организациями и координировать их работу. Работы, лежащие на критическом пути, требуют наиболее продолжительного ожидания поступления очередного события. На стадии оперативного анализа и управления сетевой график дает возможность осуществлять действенный контроль за ходом строительства, своевременно принимать меры по устранению возможных задержек в работе.
Применение сетевых графиков анализа, планирования и управления обеспечивает, как показывают многие примеры, сокращение сроков строительства на 20-30%, повышение производительности труда на 15-20%.
При анализе, осуществляемом непосредственно на стройках, использование материалов сетевого планирования и управления способствует правильному определению причин, влияющих на ход строительства, и выявлению предприятий, не обеспечивающих выполнение порученных им работ или поставку оборудования в сроки, установленные графиком.
Разработка сетевого графика в строительстве осуществляется при наличии: норм продолжительности строительства и срока ввода в действие объекта или комплекса объектов, проектно-сметной документации, проекта организации строительства и производства работ, типовых технологических карт, действующих норм затрат труда, материалов и работы машин. Кроме того, при составлении графика используются опыт выполнения отдельных работ, а также данные о производственной базе строительных и монтажных организаций.
На основе всех этих данных составляется таблица работ и ресурсов, где в технологической последовательности производства работ указываются их характеристика, объем, трудоемкость в человеко-днях, исполнитель (организация и бригада), численность рабочих, сменность, потребность в механизмах и материалах, источники их поступления, общая продолжительность выполнения работы в днях, а также предшествующее задание, после окончания которого можно начинать данную работу. Исходя из показателей такой таблицы, подготавливают сетевой график, который может иметь различную степень детализации в зависимости от принятой схемы произ
водства работ и уровня руководства; кроме общего графика исполнители разрабатывают график выполняемых ими работ.
Основные элементы сетевого графика: событие, работа, ожидание, зависимость.
При анализе хода строительства объекта следует устанавливать, правильно ли составлен сетевой график, не допущено ли при этом завышение критического пути, учтены ли при оптимизации графика все возможности его сокращения, нельзя ли какие-либо работы выполнять параллельно или сократить время, затрачиваемое на них, путем увеличения средств механизации и др. Это особенно важно в тех случаях, когда продолжительность работ по графику не обеспечивает окончание строительства в срок.
Основным материалом сетевого планирования, используемого при анализе, является информация о ходе работ по графику, который обычно составляется не реже одного раза в декаду. В качестве примера приводится карта задания и информации о ходе работы по объекту строительства, осуществляемому по сетевому графику (табл. 6.1). По данным карты, критические работы выполнялись в начале месяца с опережением графика, однако затем было допущено отставание монтажа подкрановых балок по ряду Б, а последующая работа - монтаж подкрановых балок по ряду А - закончена с отставанием на один день.
Оптимизация сетевых графиков осуществляется на стадии планирования посредством сокращения критического пути, т. е. минимизации сроков выполнения строительных работ при заданных уровнях ресурсов, минимизации уровня потребления материальных, трудовых и финансовых ресурсов при фиксированных сроках выполнения строительных работ. Возможен и смешанный подход: для одной части работ (более дорогостоящих) - минимизировать уровень потребления ресурсов при фиксированных сроках выполнения работ, для другой - минимизировать сроки при фиксированном уровне ресурсов.
Решение оптимизационных задач существенно облегчается наличием пакетов прикладных программ (ППП), приспособленных к составлению оптимальных сетевых графиков на ЭВМ.
В зарубежной практике системного анализа распространен графо-математический метод, получивший название «дерево решений». Суть этого метода заключается в следующем.
Путем предварительной оценки потребностей, предварительного анализа возможных организационных, технических или технологических условий намечаются все предполагаемые варианты решения данной задачи. Вначале разрабатываются

	Задание					Информация				Резерв времени по работам		Чис тый
Наименование работ	шифр	дата начала	дата оконча	плановая продол	Ре зерв вре	% тех-	требуемое время для	при чина	фактическая дата	находя щимся	не находящимся	резерв времени с
	работ	работ (план)	ния работ (план)	житель ность, дней	мени	кой готов ности	оконча ния работ, дней	задер жки	оконча ния работ	на критическом пути	аа критическом пути	начала месяца, дней
1	2	3	4	5	6	7	8	9	10	11	12	13
Разработка грунта	1-2	1/IV	6/IV	5	0	100	-	-	6/IV	¦-	-	-
Бетонирование фундаментов под котлы	2-3	7/IV	17/1V	9	0	100	14/IV	2	2
Бетонирование фундаментов по ряду А	2-4	7/IV	14/1V	7	2	100	14/IV
То же по ряду Б	2-5	7/IV	14/IV	7	2	100	-	-	14/IV
Устройство трубной разводки	6-18	18/IV	21/IV	4	19	100	-	-	29/IV	-7
Устройство обратной засыпки	6-7	18/IV	19/IV	2	0	100	17/IV	2	2
Монтаж сборных железобетонных ко
лонн: по ряду Б	7-8	20/IV	22/IV	3	1	100	-	-	22/IV	_	-	-
по ряду А	7-9	20/IV	22/IV	3	1	100	-	-	22/IV	-	-	-

Устройство подкрановых путей и монтаж башенного крана 7-10
Установка опорных рам на фундамент под оборудование 7-16 Монтаж подкрановых балок:
по ряду Б 8-11
20/IV 24/IV 4
20/IV 24/IV 4
24/IV 25/IV 2

по ряду А 10-12 25/IV 26/IV
Монтаж первой части балок и плит покрытия 12-13 27/IV 4/V
Монтаж подкрановых путей мостового lt;3 крана 12-14 27/IV 3/V

6	7	8	9	10	11	12	13
0	100	-	-	22/IV	1	-	1
14	100.	-	-	29/IV	-	-5	-
1	100	за-	27/IV	-2

27/IV -1
держ- ка с поставкой ж/б конструкций

1. 100 -

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

Графический метод довольно прост и нагляден для решения задач ЛП с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

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

Примечание № 1. Все вышесказанное относится и к случаю, когда система ограничений (1.1) включает равенства, поскольку любое равенство

a il x 1 +a i 2 x 2 =b

можно представить в виде системы двух неравенств (рис. 1)

A i 2 x 2 <Ь 1э +a i 2 x 2 >bj.

ЦФ L(x)= с1х1 + с2х2 при фиксированном значении L(х)=L определяет на плоскости прямую линию с1х1 + с2х2 = L. Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

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

Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

Вектор C = (c1;c2) с координатами из коэффициентов ЦФ при х1 и х2 перпендикулярен к каждой из линий уровня (см. рис. 1). Направление вектора С совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора С.

Суть графического метода заключается в следующем. По направлению (против направления) вектора С в ОДР производится поиск оптимальной точки X = (х1; х2). Оптимальной считается точка, через которую проходит линия уровня L max (L min), соответствующая наибольшему (наименьшему) значению функции L(x). Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

При поиске оптимального решения задач ЛП возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений - единственная точка; задача не имеет решений.

Допустимая область - полуплоскость

Рисунок 1

1.2. Методика решения задач лп графическим методом

I. Вограничениях задачи замените знаки неравенств на знаки точных равенств и постройте соответствующие прямые.

II. Найдите и заштрихуйте полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого подставьте в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверьте истинность полученного неравенства.

Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

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

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

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

Если ОДР - не пустое множество, то постройте целевую прямую, т.е. любую из линий уровня с 1 х 1 + с 2 х 2 = L, где L - произвольное число, например, кратное с 1 и с 2 , т.е. удобное для проведения расчетов. Способ построения аналогичен построению прямых ограничений.

V. Постройте вектор C = (c 1 ,с 2), который начинается в точке (0;0), заканчивается в точке (c 1 ,с 2). Если целевая прямая и вектор С построены верно, то они будут перпендикулярны.

VI. При поиске max ЦФ передвигайте целевую прямую в направлении вектора С, при поиске min ЦФ - против направления вектора С. Последняя по ходу движения вершина ОДР будет точкой max или min ЦФ. Если такой точки (точек) не существует, то сделайте вывод о неограниченности ЦФ на множестве планов сверху (при поиске шах) или снизу (при поиске min).

Определите координаты точки max (min) ЦФ X = (х1 * ; х2 * ) и вычислите значение ЦФ l(x *). Для вычисления координат оптимальной точки X * решите систему уравнений прямых, на пересечении которых находится X * .

Задача 1

Найдем оптимальное решение задачи, математическая модель которой имеет вид

L(Х) = 3x 1 + 2x 2 → max

х 1 + 2х 2 < 6, (1)

2х 1 + х 2 < 8, (2)

Х 1 +х 2 <1, (3)

х 2 < 2, (4)

х 1 >0,х 2 >0.

Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис. 2).

х 1 + 2х 2 = 6,(1)

2х1 + х2= 8,(2)

(1) х1=0, х1=6, х2=3, х2=0,

(2) х1=0, х1=4, х2=8, х2=0,

(3) х1=0, х1=-1, х2=1, х2=0,

Прямая (4) проходит через точку х 2 = 2 параллельно оси L(Х).

Рис. 2. Графическое решение задачи

Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (3), получим 0 < 1, что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (3). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (рис. 2). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDEF.

Целевую прямую можно построить по уравнению

Строим вектор С из точки (0;0) в точку (3;2). Точка Е- это последняя вершина многоугольника допустимых решений ABCDEF, через которую проходит целевая прямая, двигаясь по направлению вектора С. Поэтому Е -это точка максимума ЦФ. Определим координаты точки Е из системы уравнений прямых ограничений (1) и (2)

Х1 +2х 2 =6, (1) х1=10/3=3 1/3, х2=4/3=1 1/3

2 Х1 +х 2 =8, (2) Е 3 1/3; 1 1/3

Максимальное значение ЦФ равно L(E) = 3*10/3+2*4/3 = 12 2 / 3