Контрольная работа по дисциплине «Количественный анализ управленческих и хозяйственных решений»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ
Федеральное государственное бюджетное образовательное учреждение
Высшего профессионального образования
«УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ»
ЦЕНТР ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ


КОНТРОЛЬНАЯ РАБОТА
по дисциплине «Количественный анализ управленческих и хозяйственных решений »
На тему: «Задачи линейного программирования: особенности, область применения, основные типы задач.
»

Студент группы

ИДО ЗБ КЭиПУБ-20 Узб
Мехмонов.Э.М

Екатеринбург

2023

сОДЕРЖАНИЕ

Введение
Общая задача линейного программирования (ЛП)
1 Постановка задачи
2 Графический метод решения задач ЛП
3. Основные типы линейного програмирование
Заключение
Список использованных источников


Введение

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

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

Задача линейного программирования (ЛП) ассоциируется с задачей распределительного типа, в которой требуется распределить ограниченные ресурсы по нескольким видам деятельности. Интерпретация задачи ЛП в этом случае состоит в следующем. Моделируемая ЭИС характеризуется наличием нескольких видов деятельности j (j = 1, …, n), для осуществления которых требуются имеющиеся в ограниченном количестве различные ресурсы bi, (i = 1, …, m). Интенсивность расходования каждого из ресурсов на каждый из видов деятельности ЭИС известна и равна aij. Результативность или ценность каждого j-го вида деятельности ЭИС характеризуется величиной cj. Цель построения модели заключается в определении уровней каждого вида деятельности ЭИС xj, при которых оптимизируется общий результат деятельности ЭИС в целом при выполнении ограничений, накладываемых на использование ресурсов, т. е. cj xj ≤ bi, i = 1, …, m. Структура целевой функции y(u) отражает вклад каждого вида деятельности ЭИС в общий результат. При максимизации сj представляет собой “полезность” j-го вида деятельности (ущерб, наносимый конкуренту по бизнесу, предотвращенный ущерб), а в случае минимизации характеризует затраты (потери собственные, расход материальных средств). Линейность модели выявляется или принимается в качестве допущения на этапе формализации задачи. Линейность предполагает наличие двух свойств - пропорциональности и аддитивности, присущих как целевой функции, так и ограничениям. Пропорциональность целевой функции означает, что вклад каждой управляемой переменной в целевую функцию пропорционален величине этой переменной. Аддитивность же целевой функции заключается в том, что целевая функция представляет собой сумму вкладов от различных управляемых переменных. Пропорциональность ограничений проявляется в том, что общий объем потребляемых ресурсов прямо пропорционален величинам управляемых переменных. Аддитивность ограничений состоит в том, что величина ресурса должна представлять собой сумму расходов по видам деятельности, каждое слагаемое которой пропорционально величине соответствующей управляемой переменной. В формализованном виде задачу ЛП можно представить следующим образом:

Определить

где , (1.1)

Условие неотрицательности, накладываемое на переменные xj, означает, что ни одному виду деятельности ЭИС не может быть приписан отрицательный уровень. Ограничение типа ≥ нельзя рассматривать как ограничение в буквальном смысле этого слова. Наличие такого неравенства предполагает необходимость обязательного выполнения каких-либо планов, заданий, нормативов.

Математическая формулировка задачи ЛП выглядит следующим образом: необходимо определить значения управляемых переменных xj, доставляющих экстремум целевой функции y(u) на всем множестве стратегий U = {u} и удовлетворяющих всем имеющимся в задаче ограничениям. Этой формулировкой задача ЛП считается поставленной математически, что позволяет осуществлять поиск ее оптимального решения известными математическими методами.
Формальную постановку задачи ЛП (1.1) для удобства можно представить в упрощенном виде:
определить max (или min) W(x) = при ограничениях:
cj xj (≤, = или ≥) bi, i = 1, …, m; xj ≥ 0,

где W(x) - новое обозначение ЦФ, т. е. W(x) = y(u) = f(x).

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

Графический метод, несмотря на свою очевидность и применимость лишь в случае малой размерности задачи, позволяет понять качественные особенности задачи линейного программирования, характерные для любой размерности пространства переменных и лежащие в основе численных методов ее решения. Поясним графический метод на примере задачи ЛП в основной форме для n = 2

(c, x) → max≤ b,

где x = (x1, x2), c = (c1, c2), b = (b1, b2, ..., bm), A - матрица размера (m × 2).

Очевидно, что при данной постановке задачи допустимое множество X в плоскости (x1, x2) представляет собой многоугольник (не обязательно замкнутый), образованный пересечением полуплоскостей H+aibi (где ai - i-я строка матрицы A, i = 1, ..., m), соответствующих ограничениям вида ai1x1 + ai2x2 ≤ bi в исходной задаче. Линии уровня функции f(x) = (c, x) (линией уровня называется множество {x R: f(x)= α, α R}) образуют семейство параллельных прямых Hcα. При этом grad f(x) = c, т.е. градиент целевой функции всюду одинаков и является нормалью каждой из данных полуплоскостей. В соответствии с предыдущим, поиск решения задачи сводится к нахождению максимального числа α* среди всех таких α, что полуплоскость Hcα имеет непустое пересечение с X. При этом X - множество решений задачи. При неограниченном решений может и не быть, т.е. Hcα X Ø при всех α→ .
Из графического представления ясна характерная особенность задачи ЛП (при c ≠ 0): если ее решение существует, то оно достигается обязательно на границе. Отметим, что в рассмотренной задаче ЛП на максимум при поиске α* происходит как бы перемещение прямой Hcα в направлении вектора c. Если же решается задача ЛП на минимум, и, следовательно, ищется минимальное α*, удовлетворяющее указанным требованиям, то Hcα перемещается в направлении, противоположном вектору c.
Пример 1.2.1 Пусть дана задача ЛП

x + y → max

x + y ≤ 2,+ 2y ≤ 7,
x - 3y ≤ 6,≥ 0, y ≥ 0.

Геометрическая интерпретация задачи приведена на рисунке 1.

Рисунок 1

Ясно, что решением является точка пересечения прямых

+ 2y = 7 и 4x - 3y = 6, т.е. (x*, y*) = (3, 2).

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

Постановка задачи

Задача линейного программирования (ЛП) ассоциируется с задачей распределительного типа, в которой требуется распределить ограниченные ресурсы по нескольким видам деятельности. Интерпретация задачи ЛП в этом случае состоит в следующем. Моделируемая ЭИС характеризуется наличием нескольких видов деятельности j (j = 1, …, n), для осуществления которых требуются имеющиеся в ограниченном количестве различные ресурсы bi, (i = 1, …, m). Интенсивность расходования каждого из ресурсов на каждый из видов деятельности ЭИС известна и равна aij. Результативность или ценность каждого j-го вида деятельности ЭИС характеризуется величиной cj. Цель построения модели заключается в определении уровней каждого вида деятельности ЭИС xj, при которых оптимизируется общий результат деятельности ЭИС в целом при выполнении ограничений, накладываемых на использование ресурсов, т. е. cj xj ≤ bi, i = 1, …, m. Структура целевой функции y(u) отражает вклад каждого вида деятельности ЭИС в общий результат. При максимизации сj представляет собой “полезность” j-го вида деятельности (ущерб, наносимый конкуренту по бизнесу, предотвращенный ущерб), а в случае минимизации характеризует затраты (потери собственные, расход материальных средств). Линейность модели выявляется или принимается в качестве допущения на этапе формализации задачи. Линейность предполагает наличие двух свойств - пропорциональности и аддитивности, присущих как целевой функции, так и ограничениям. Пропорциональность целевой функции означает, что вклад каждой управляемой переменной в целевую функцию пропорционален величине этой переменной. Аддитивность же целевой функции заключается в том, что целевая функция представляет собой сумму вкладов от различных управляемых переменных. Пропорциональность ограничений проявляется в том, что общий объем потребляемых ресурсов прямо пропорционален величинам управляемых переменных. Аддитивность ограничений состоит в том, что величина ресурса должна представлять собой сумму расходов по видам деятельности, каждое слагаемое которой пропорционально величине соответствующей управляемой переменной. В формализованном виде задачу ЛП можно представить следующим образом:

Определить

где , (1.1)

Условие неотрицательности, накладываемое на переменные xj, означает, что ни одному виду деятельности ЭИС не может быть приписан отрицательный уровень. Ограничение типа ≥ нельзя рассматривать как ограничение в буквальном смысле этого слова. Наличие такого неравенства предполагает необходимость обязательного выполнения каких-либо планов, заданий, нормативов.

Математическая формулировка задачи ЛП выглядит следующим образом: необходимо определить значения управляемых переменных xj, доставляющих экстремум целевой функции y(u) на всем множестве стратегий U = {u} и удовлетворяющих всем имеющимся в задаче ограничениям. Этой формулировкой задача ЛП считается поставленной математически, что позволяет осуществлять поиск ее оптимального решения известными математическими методами.
Формальную постановку задачи ЛП (1.1) для удобства можно представить в упрощенном виде:
определить max (или min) W(x) = при ограничениях:

cj xj (≤, = или ≥) bi, i = 1, …, m; xj ≥ 0,

где W(x) - новое обозначение ЦФ, т. е. W(x) = y(u) = f(x).

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

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

2. Задача линейного программирования в стандартной форме: В этом типе задачи цель состоит в оптимизации линейной функции цели при ограничениях в виде равенств.

3. Максимизация или минимизация: Линейные программы могут быть сформулированы для максимизации или минимизации линейной функции цели.

4. Задача с ограничениями в виде равенств: Некоторые задачи линейного программирования имеют ограничения, заданные в виде равенств.

5. Задача с ограничениями в виде неравенств: Другие задачи линейного программирования имеют ограничения, заданные в виде неравенств.

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