Важным методом научного анализа статистического материала выступают графические изображения. Первые попытки использования графических методов в экономических исследованиях начались еще в 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.,%
Наиболее простым и наглядным методом решения задачи линейного программирования (ЗЛП) является графический метод. Он основан на геометрической интерпретации задачи линейного программирования и применяется при решении ЗЛП с двумя неизвестными:
Будем рассматривать решение этой задачи на плоскости. Каждое неравенство системы функциональных ограничений геометрически определяет полуплоскость с граничной прямой а п х, + + a j2 х 2 = b n i = 1, т. Условия неотрицательности определяют полуплоскости с граничными прямыми х { = 0, х 2 = 0 соответственно. Если система совместна, то полуплоскости, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек; координаты каждой из этих точек являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, ограниченным и неограниченным многоугольником.
Геометрически ЗЛП представляет собой отыскание такой угловой точки многоугольника решений, координаты которой доставляют максимальное (минимальное) значение линейной целевой функции, причем допустимыми решениями являются все точки многоугольника решений.
Линейное уравнение описывает множество точек, лежащих на одной прямой. Линейное неравенство описывает некоторую область на плоскости.
Определим, какую часть плоскости описывает неравенство 2х { + Зх 2 12.
Во-первых, построим прямую 2х, + Зх 2 =
12. Она проходит через точки (6; 0) и (0; 4). Во-вторых, определим, какая полуплоскость удовлетворяет неравенству. Для этого выбираем любую точку на графике, не принадлежащую прямой, и подставляем ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением и полуплоскость, содержащая точку, удовлетворяет неравенству. Для подстановки в неравенство удобно использовать начало координат. Подставим х { = х 2 =
0 в неравенство 2х, + Зх 2 12. Получим 2 0 + 3 0
Аналогично графически можно изобразить все ограничения задачи линейного программирования.
Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений (ОДР) или областью определения.
Необходимо помнить, что область допустимых решений удовлетворяет условиям неотрицательности (Xj > 0, j = 1, п). Координаты любой точки, принадлежащей области определения, являются допустимым решением задачи.
Для нахождения экстремального значения целевой функции при графическом решении ЗЛП используют вектор-градиент, координаты которого являются частными производными целевой функции:
Этот вектор показывает направление наискорейшего изменения целевой функции. Прямая c [ x l + с 2 х 2 = f(x 0), перпендикулярная вектору-градиенту, является линией уровня целевой функции (рис. 2.2.2). В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине а. Меняя значение а, получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.
Рис. 2.2.2.
Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении в д р у г у ю сторону - только убывает.
Графический метод решения ЗЛП состоит из четырех этапов:
- 1. Строится область допустимых решений (ОДР) ЗЛП.
- 2. Строится вектор-градиент целевой функции (ЦФ) с началом в точке х 0 (0; 0): V = (с, с 2).
- 3. Линия уровня CjXj + с 2 х 2 = а (а - постоянная величина) - прямая, перпендикулярная вектору-градиенту V, - передвигается в направлении вектора-градиента в случае максимизации целевой функции f(x v х 2) до тех пор, пока не покинет пределов ОДР. При минимизации /(*, х 2) линия уровня перемещается в направлении, противоположном вектору-градиенту. Крайняя точка (или точки) ОДР при этом движении и является точкой максимума (минимума) f(x p jc 2).
Если прямая, соответствующая линии уровня, при своем движении не покидает ОДР, то минимума (максимума) функции f(x р х 2) не существует.
Если линия уровня целевой функции параллельна функциональному ограничению задачи, на котором достигается оптимальное значение ЦФ, то оптимальное значение ЦФ будет достигаться в любой точке этого ограничения, лежащей между двумя оптимальными угловыми точками, и, соответственно, любая из этих точек является оптимальным решением ЗЛП.
4. Определяются координаты точки максимума (минимума). Для этого достаточно решить систему уравнений прямых, дающих в пересечении точку максимума (минимума). Значение f(x { , х 2), найденное в полученной точке, является максимальным (минимальным) значением целевой функции.
Возможные ситуации графического решения ЗЛП представлены в табл. 2.2.1.
Таблица 2.2.1
|
Вид ОДР |
Вид оптимального решения |
|
Ограниченная |
Единственное решение |
|
Бесконечное множество решений |
|
|
Неограниченная |
ЦФ не ограничена снизу |
|
ЦФ не ограничена сверху |
|
|
Единственное решение |
|
|
Бесконечное множество решений |
|
|
Единственное решение |
|
|
Бесконечное множество решений |
Пример 2.2.1. Планирование выпуска продукции пошивочного предприятия (задача о костюмах).
Намечается выпуск двух видов костюмов - мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 человекодень трудозатрат; на мужской - 3,5 м шерсти, 0,5 м лавсана и 1 человекодень трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человекодней трудозатрат.
Требуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 ден. ед., а от мужского - 20 ден. ед. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.
Экономико-математическая модель задачи
Переменные : х, - число женских костюмов; х 2 - число мужских костюмов.
Целевая функция :
Ограничения :
Первое ограничение (по шерсти) имеет вид х { + 3,5х 2 х { + 3,5х 2 = 350 проходит через точки (350; 0) и (0; 100). Второе ограничение (по лавсану) имеет вид 2х { + 0,5х 2 2х х + 0,5х 2 = 240 проходит через точки (120; 0) и (0; 480). Третье ограничение (по труду) имеет вид х у +х 2 150. Прямая х { + х 2 = 150 проходит через точки (150; 0) и (0; 150). Четвертое ограничение (по количеству мужских костюмов) имеет вид х 2 > 60. Решением этого неравенства является полуплоскость, лежащая выше прямой х 2 = 60.
В результате пересечения построенных четырех полуплоскостей получаем многоугольник, который и является областью допустимых решений нашей задачи. Любая точка этого многоугольника удовлетворяет всем четырем функциональным неравенствам, а для любой точки вне этого многоугольника хотя бы одно неравенство будет нарушено.
На рис. 2.2.3 затенена область допустимых решений (ОДР). Для определения направления движения к оптимуму построим вектор- градиент V, координаты которого являются частными производными целевой функции:
Чтобы построить такой вектор, нужно соединить точку (10; 20) с началом координат. Для удобства можно строить вектор, пропорциональный вектору V. Так, на рис. 2.2.3 изображен вектор (30; 60).
Затем построим линию уровня 10xj + 20х 2 = а. Приравняем целевую функцию постоянной величине а. Меняя значение а , получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.
Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции F*(X) = -F(X) . Также имеется возможность составить двойственную задачу .Решение происходит в три этапа:
- Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b (F(X) → extr) сводится к виду ax = b , F(X) → max ;
- Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
- Решение симплексным методом;
Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .
Переход от задачи минимизации целевой функции к задаче максимизации
Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .Проиллюстрируем этот факт графически:
| F(x) → min
|
F(x) → max
 |
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).
Ведущий (разрешающий) элемент
– коэффициент свободной неизвестной, которая становится базисной, а сам коэффициент преобразуется в единицу.
Направляющая строка
– строка ведущего элемента, в которой расположена с единичным коэффициентом базисная неизвестная, исключаемая при преобразовании (строка с минимальным предельным коэффициентом, см. далее).
Направляющий столбец
– столбец ведущего элемента, свободная неизвестная которого переводится в базисную (столбец с максимальной выгодой, см. далее).
Переменные x 1 , …, x m , входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми - в остальные, называются базисными
или зависимыми
. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса-Жордана . Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (x m +1 ,…, x n) называются небазисными
или независимыми переменными
.
Базисное решение
называется допустимым базисным решением
, если значения входящих в него базисных переменных x j ≥0, что эквивалентно условию неотрицательности b j ≥0.
Допустимое базисное решение является угловой точкой
допустимого множества S задачи линейного программирования и называется иногда опорным планом
.
Если среди неотрицательных чисел b j есть равные нулю, то допустимое базисное решение называется вырожденным
(вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной
.
Пример №1
. Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x 1 + 2x 2 - 2x 3 → min при ограничениях:
4x 1 + 3x 2 - x 3 ≤10
- 2x 2 + 5x 3 ≥3
x 1 + 2x 3 =9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x 4 ; во втором неравенстве смысла (≥) вводим базисную переменную x 5 со знаком минус.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x 1 + 0x 2 + 2x 3 + 0x 4 + 0x 5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Переход к СЗЛП
.
Расширенная матрица системы ограничений-равенств данной задачи:
| 4 | 3 | -1 | 1 | 0 | 10 |
| 0 | -2 | 5 | 0 | -1 | 3 |
| 1 | 0 | 2 | 0 | 0 | 9 |
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x 4 .
2. В качестве базовой переменной выбираем x 2 .
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x 2 , получена в результате деления всех элементов строки x 2 на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 2 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
| 4-(0 3):-2 | 3-(-2 3):-2 | -1-(5 3):-2 | 1-(0 3):-2 | 0-(-1 3):-2 | 10-(3 3):-2 |
| 0: -2 | -2: -2 | 5: -2 | 0: -2 | -1: -2 | 3: -2 |
| 1-(0 0):-2 | 0-(-2 0):-2 | 2-(5 0):-2 | 0-(0 0):-2 | 0-(-1 0):-2 | 9-(3 0):-2 |
Получаем новую матрицу:
| 4 | 0 | 6 1 / 2 | 1 | -1 1 / 2 | 14 1 / 2 |
| 0 | 1 | -2 1 / 2 | 0 | 1 / 2 | -1 1 / 2 |
| 1 | 0 | 2 | 0 | 0 | 9 |
3. В качестве базовой переменной выбираем x 3 .
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x 3 , получена в результате деления всех элементов строки x 3 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 3 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
| 4-(1 6 1 / 2):2 | 0-(0 6 1 / 2):2 | 6 1 / 2 -(2 6 1 / 2):2 | 1-(0 6 1 / 2):2 | -1 1 / 2 -(0 6 1 / 2):2 | 14 1 / 2 -(9 6 1 / 2):2 |
| 0-(1 -2 1 / 2):2 | 1-(0 -2 1 / 2):2 | -2 1 / 2 -(2 -2 1 / 2):2 | 0-(0 -2 1 / 2):2 | 1 / 2 -(0 -2 1 / 2):2 | -1 1 / 2 -(9 -2 1 / 2):2 |
| 1: 2 | 0: 2 | 2: 2 | 0: 2 | 0: 2 | 9: 2 |
Получаем новую матрицу:
| 3 / 4 | 0 | 0 | 1 | -1 1 / 2 | -14 3 / 4 |
| 1 1 / 4 | 1 | 0 | 0 | 1 / 2 | 9 3 / 4 |
| 1 / 2 | 0 | 1 | 0 | 0 | 4 1 / 2 |
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
3 / 4 x 1 + x 4 - 1 1 / 2 x 5 = -14 3 / 4
1 1 / 4 x 1 + x 2 + 1 / 2 x 5 = 9 3 / 4
1 / 2 x 1 + x 3 = 4 1 / 2
Выразим базисные переменные через остальные:
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4
x 3 = - 1 / 2 x 1 +4 1 / 2
Подставим их в целевую функцию:
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
или
Система неравенств:
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4 ≥ 0
- 1 / 2 x 1 +4 1 / 2 ≥ 0
Приводим систему неравенств к следующему виду:
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 5 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 5 -10 1 / 2 → max
Упростим систему.
3 / 4 x 1 - 1 1 / 2 x 2 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 2 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → max
Пример №2
. Найдите сначала графическим методом, а затем симплекс-методом решение задачи
F(X) = x 1 + x 2 - x 3 + x 5 +15 → max (min) при ограничениях:
-3x 1 + x 2 + x 3 =3
4x 1 + 2x 2 - x 4 =12
2x 1 - x 2 + x 5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0
Графический метод решения ЗЛП основан на утверждениях, приведенных в пункте 2.1. Согласно теореме 2, оптимальное решение находится в вершине области допустимых решений и поэтому решить ЗЛП – найти вершину области допустимых решений, координаты которой дают оптимальное значение целевой функции.
Графический метод используют для решения ограниченного класса задач с двумя переменными, иногда с тремя переменными. Надо заметить, что для трех переменных эта область является недостаточно наглядной.
Алгоритм графического метода решения злп
Реализацию графического метода решения ЗЛП рассмотрим на примерах.
Пример 2.2.1. Решить ЗЛП графическим методом:
(2.2.1)
max z =x 1 + 4x 2 (2.2.2)
Решение. Для построения области допустимых решений, которая состоит из пересечения полуплоскостей, соответствующих каждому неравенству системы ограничений (2.2.1), запишем уравнения граничных прямых:
l 1: x 1 + 5x 2 = 5; l 2: x 1 + x 2 = 6; l 3: 7x 1 + x 2 = 7.
l
1
к виду (2.2.3.) разделим
обе его части на 5:
.
Таким образом, прямаяl
1
отсекает на оси Ох
1
5 единиц, на оси Ох
2
1 единицу. Аналогично
имеем для l
2:
иl
3:
.
Для определения полуплоскостей, которые отвечают ограничениям системы (2.2.1), в ограничения нужно подставить координаты какой-либо точки, не лежащей на граничной прямой. Если получим верное неравенство, то все точки из этой полуплоскости являются решениями данного неравенства. В противном случае выбирают другую полуплоскость.
Таким образом,
первая и вторая искомые полуплоскости
расположены в противоположную сторону
от начала координат (0 – 5·0
–
5; 7·0 + 0
7),
а вторая – в сторону начала координат
(0 + 0
6). Область допустимых решений на рисунке
2.2.1 заштрихована.
Рисунок 2.2.1 – Область допустимых решений
Для
нахождения оптимального плана, который
будет находиться в вершине многоугольника
решений, нужно построить вектор
направлений
=(с
1 ,с
2),
который указывает направление наибольшего
возрастания целевой функцииz
=с
1 х
1 +с
2 х
2 .
В
данной задаче вектор направлений
=
(1, 4): он начинается в точкеО
(0,0) и
заканчивается в точкеN
(1, 4).
Далее строим прямую, которая проходит через область допустимых решений, перпендикулярно к вектору , и называетсялинией уровня целевой функции. Передвигаем линию уровня в направлении векторав случае максимизации целевой функцииz и в направлении противоположном, в случае минимизацииz , до последнего пересечения с областью допустимых решений. В результате определяется точка или точки, где целевая функция достигает экстремального значения, или устанавливается неограниченность целевой функцииz на множестве решений задачи.
Таким образом, точкой максимума целевой функции z является точкаА пересечения прямыхl 2 иl 3 .
Для вычисления оптимального значения целевой функции z найдем координаты точки А. Поскольку точка А – это точка пересечения прямых l 2 и l 3 , то ее координаты удовлетворяют системе уравнений, составленной из уравнений соответствующих граничных прямых:
Таким образом, точка А имеет координаты x 1 =1/6, x 2 = 35/6.
Для вычисления оптимального значения целевой функции нужно подставить в нее координаты точки А.
Подставив координаты точки А в целевую функцию (2.4), получим
max z = 1/6 + 4·(35/6) = 47/2.
Пример 2.2.2. Построить на плоскости область допустимых решений системы линейных неравенств (2.2.4) и найти наибольшее и наименьшее значения целевой функции (2.2.5):
(2.2.4)
z = –2x 1 –x 2 (2.2.5)
Решение. Для построения области допустимых решений, которая состоит из пересечения полуплоскостей, соответствующих каждому неравенству системы ограничений (2.2.4), запишем уравнения граничных прямых:
l 1: 4x 1 – x 2 = 0; l 2: x 1 + 3x 2 = 6; l 3: x 1 – 3x 2 = 6; l 4: x 2 = 1.
Прямая l 1 проходит через точку с координатами (0;0). Для ее построения выразим x 2 через x 1: x 2 = 4x 1 . Найдем еще одну точку, через которую проходит прямая l 1 , например (1;4). Через точку с координатами (0;0) и точку с координатами (1;4) проведем прямую l 1 .
Для
приведения уравнения прямой l
2
к виду в отрезках на
осях (2.2.3) разделим обе его части на 6:
.
Таким образом, прямаяl
2
отсекает на оси Ох
1
6 единиц, на оси Ох
2
- 2 единицы. Аналогично
имеем для l
3:
и Прямаяl
4
параллельна оси Ох
1
и проходит через точку с координатами
(0;1) .
Для
определения полуплоскостей, которые
отвечают ограничениям системы (2.2.4) в
ограничения нужно подставить координаты
какой-либо точки, не лежащей на граничной
прямой. В силу ограничений
х
1 
0,
х 2 
0, область допустимых решений ЗЛП лежит
в первой четверти координатной плоскости.
О
бласть
допустимых решений на рисунке 2.2.2
заштрихована.
Рисунок 2.2.2 – Область допустимых решений
Построим
вектор направлений
=
(–2,–1). Далее строим линию уровня,
перпендикулярно к вектору.
Для нахождения наибольшего значения целевой функции передвигаем линию уровня в направлении вектора до последнего пересечения с областью допустимых решений. Таким образом, точкой максимума целевой функцииz является точкаА (пересечение прямыхl 1 иl 2).
Для вычисления оптимального значения целевой функции z найдем координаты точкиА . Поскольку точкаА – это точка пересечения прямыхl 1 иl 2 , то ее координаты удовлетворяют системе уравнений, составленной из уравнений соответствующих граничных прямых:
Таким образом, точка А имеет координаты x 1 =6/13, x 2 = 24/13.
Подставив координаты точки А в целевую функцию (2.2.5), получим оптимальное значение целевой функции
max z = – 2·(6/13) – (24/13) = – 36/13.
Для нахождения наименьшего значения целевой функции передвигаем линию уровня в направлении, противоположном вектору до последнего пересечения с областью допустимых решений. В этом случае целевая функция неограниченна в области допустимых решений, т.е. ЗЛП минимума не имеет.
В результате решения ЗЛП возможны следующие случаи:
Целевая функция достигает оптимального значения в единственной вершине многоугольника решений;
Целевая функция достигает оптимальное значение в любой точке ребра многоугольника решений (ЗЛП имеет альтернативные опорные планы с одинаковыми значениями z);
ЗЛП не имеет оптимальных планов;
ЗЛП имеет оптимальный план в случае неограниченной области допустимых решений.
На этом уроке будем знакомиться с графическим методом решения задач линейного программирования , то есть, таких задач, в которых требуется найти такое решения системы линейных уравнений и (или) неравенств (системы ограничений), при котором функция цели - линейная функция - принимает оптимальное значение.
Ввиду того, что наглядность графического решения достигается лишь на плоскости, мы можем познакомиться с графическим представлением задачи только в двумерном пространстве. Это представление пригодно для системы ограничений-неравенств с двумя переменными или для систем уравнений, в которых число переменных на 2 превышает число уравнений, то есть число свободных переменных равно двум.
Поэтому графический метод имеет такие узкие рамки применения, что о нём как об особом методе решения задач линейного программирования говорить нельзя.
Однако для выработки наглядных представлений о решениях задач линейного программирования графический метод представляет определённый интерес. Кроме того, он позволяет геометрически подтвердить справедливость теорем линейного программирования .
Теоретические основы графического метода
Итак, задача линейного программирования. Требуется найти неотрицательные значения переменных и , удовлетворяющих системе неравенств
при которых линейная форма принимает оптимальное значение.
Пример 3.
Пример 4. Решить графическим методом задачу линейного программирования, в которой требуется найти минимум функции при ограничениях
Продолжаем решать задачи графическим методом вместе
До сих пор полученные выводы были основаны на том, что множество решений задачи линейного программирования сконфигурировано так, что оптимальное решение конечно и единственно. Теперь рассмотрим примеры, когда это условие нарушается. В этих примерах многоугольник решений строится так, как показано в предыдущих примерах, остановимся же на признаках, которые отличают эти исключительные примеры.
Пример 5. Решить графическим методом задачу линейного программирования, в которой требуется найти максимум функции при ограничениях
Решение. На рисунке изображены: неограниченная многогранная область решений данной системы ограничений, исходная линия уровня (чёрного цвета), вектор (бордового цвета), указывающий направление движения исходной линии уровня для нахождения максимума целевой функции.
Легко заметить, что функция F может неограниченно возрастать при заданной системе ограничений, поэтому можно условно записать, что .
Пример 6. Решить графическим методом задачу линейного программирования, в которой требуется найти максимум функции при ограничениях
