МИНИСТЕРСТВО ОБРАЗОВАНИЯ УКРАИНЫ
Севастопольский государственный технический университет
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
по дисциплине «Экономический анализ(теория)»
к лабораторным занятиям по теме: «Особенности
и область применения в экономическом анализе
линейного программирования»
с применением ПВЭМ для студентов специальностей
7.050206 «Учет и аудит» и 7.050104 «Финансы».
Разработано:
доц.Мараховская Т.А.
СЕВАСТОПОЛЬ
1998
ОСОБЕННОСТИ И ОБЛАСТЬ ПРИМЕНЕНИЯ В АНАЛИЗЕ ХОЗЯЙСТВЕННОЙ ДЕЯТЕЛЬНОСТИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ГРАФИЧЕСКИМ МЕТОДОМ С ПРИМЕНЕНИЕМ ПЭВМ )
ЦЕЛЬ РАБОТЫ : изучение метода линейного программирования для оптимизации
материальных и трудовых затрат в производстве.
1.ПОСТАНОВКА ЗАДАЧИ .
1.1.ВВЕДЕНИЕ.
Управление хозяйственной деятельностью начинается с планирования. Различные варианты плана связаны с неодинаковыми материальными и трудовыми затратами. Поэтому выбор наиболее оптимального из них во многом определяет конечные результаты.Его преимущества перед другими планами устанавливают с помощью критерия оптимальности F. Для промышленных и сельскохозяйственных предприятий оптимальным считается план,обеспечивающий выпуск заданного объёма продукции при минимальных затратах, а также получение максимума прибыли при ограниченном объёме ресурсов.
Критерий (показатель) оптимальности F(x) называют функцией плана,а сравниваемые варианты планов(x) - аргументами этой функции.
Выбор оптимального плана можно рассматривать как математическую задачу максимизации или миними-зации значения целевой функции.Один из математических методов нахождения минимума функции,аргумен-ты которой выбираются из ограниченной области допустимых значений,- это линейное программирование.
Линейное программирование позволяет определять экстремальное (минимальное или максимальное) значение искомой величины (максимального объёма производства,минимальных затрат на производство заданного объёма продукции,максимальной прибыли и т.д.) при определённых ограничениях и характеризуется линейной зависимостью между переменными.
К задачам линейного программирования относятся следующие :
- задача о назначениях (как распределить рабочих по станкам,чтобы общая выработка была наибольшей или затраты на заработную плату наименьшими и т.п.);
- задача о раскрое (помогает с наименьшими отходами использовать листы металла,стекла,картона и других материалов при их раскрое на заданные количества деталей различных размеров);
- задача о смесях (определение такого рациона,который удовлетворял бы потребностям человека или животного в питательных веществах при минимальной общей стоимости используемых продуктов);
- транспортная задача (требуется найти такой план доставки грузов от поставщиков к потребителям,чтобы стоимость перевозки была наименьшей)и т.д.
Существует множество методов решения этих задач. Все эти методы могут быть разделены на две группы :
- К первой группе относятся универсальные методы,позволяющие решать практически любые задачи линейного программирования.Наиболее распространенным из универсальных является симплекс-метод и его модификации.
- Вторую группу составляют специальные методы,к которым относятся : венгерский метод,распредели тельный метод,метод разрешающих слагаемых А.Л.Лурье и др. В частности,специальным является и геометрический (графический) метод,обеспечивающий простое и наглядное решение в частных случаях.
1.2.ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЛП-ЗАДАЧ :
Если общее число переменных ЛП-задачи n=2 или она может быть
сведена к соответствующей задаче с числом независимых переменных k=2,то такая
задача может быть легко решена графическим методом. Итак,пусть ЛП-задача имеет
вид: максимизировать f(x ,x )=(c x +c x ) (1)
при ограничениях
g (x ,x )<b ;
g (x ,x )<b ; (2)
. . . . . . . .
g (x ,x )<b ;
x >0, x >0. (3)
Графический метод решения заключается в следующем .
X2
X2 X2
2 Fmaax
2
3 1 F=C2
1 Xорт
R 3 F=C1
R
N Fmax Fmax
0 X1 4 X1 0 X1
а б в
рис.1
1.Строим допустимое множество решений R , определяемое (2) и (3).
2.Далее строим вектор нормали N к целевой функции f(x ,x ).Его проекция на ось Ox равна kc , a на ось Ox - kc ,где k - произвольный положительный скаляр .
Заметим , что N указывает направление возрастания f (x ,x ).
3.Перемещаем прямую f(x ,x ) = const в направлении N так , чтобы она оставалась перпендикулярной N до тех пор , пока эта прямая не выйдет на границу множества R.
При этом возможен один из следующих случаев :
а)f(x ,x ) и R будут иметь лишь одну общую точку (крайнюю точку R ); эта точка определяет единственное оптимальное решение ;
б)f(x ,x ) и R имеют целое множество общих точек , это будет в том случае , когда вектор N окажется нормален к соответствующей грани множества R, данное множество общих точек представляет собой множество оптимальных решений задачи ;
в)прямая f(x ,x ) = const не выходит на границу множества R, сколько бы её не перемещали (это будет в случае, если множество R - неограниченно ), тогда целевая функция f(x ,x ) оказывается также неограниченной .Соответствующие случаи иллюстрируются рис 1 а, б, в. Заметим , что при решении задачи минимизации f(x, x) перемещают в направлении , противоположном N.
1.3. Алгоритм решения задачи «симплекс-методом»
1.3.1 По условию задачи определите:
- что является ресурсами? (по ресурсам всегда указан удельный расход (Aij) и даны ограничения, т.е. максимально доступное количество – (Вj))
- что является вариантами или направлениями использования ресурсов?
- что является целевой функцией (т.е. какую величину необходимо максимизировать)?
1.3.2. Примите за Хi – количество единиц варианта i вида (количество изделий i-го вида, пакетов ценных бумаг i-го вида). С использованием принятого обозначения запишите:
- по каждому виду ресурсов в виде неравенства ограничения по расходу
- значения Хi не могут быть отрицательными
Также запишите в общем виде значение целевой функции, т.е. функции, учитывающей вклад каждого варианта и стремящейся к мах
1.3.3. Перейдите от системы неравенств к системе равенств, введя значения остатков (Уi – остаток ресурсов i-го вида). При этом У оставляется в левой части y, а все остальные переносим в правую часть, но знак «-» ставят не перед значением удельного расхода, а ставят перед Х
В связи изменениями знака переменных необходимо внести изменения в целевую функцию задачи F= (-С1)(-X1) + (-С2)(-X2) + (-С3)(-X3) → max.
Таким образом, для решения системы уравнений при переходе к матрице решений выносятся в столбцы значения (-Хi) …, в строках за границы матрицы выносят обозначение Уj.
|
-X1 |
-X2 |
- X3 |
|
y1 |
A11 |
A12 |
A13 |
B1 |
y2 |
A21 |
A22 |
A23 |
B2 |
y3 |
A31 |
A32 |
A33 |
B3 |
F |
A41 (-C1) |
A42 (-C2) |
A43 (-C3) |
B4 (0) |
1.3.4. Далее полученную матрицу необходимо оптимизировать.
Этапы оптимизации целевой функции:
- поиск опорного решения, опорному решению соответствует симплекс – таблица с неотрицательными значениями всех свободных членов в строке F;
- поиск оптимального решения:
а) выбор разрешающего столбца - для этого в F-cтроке выбирают наибольший по модулю отрицательный элемент столбца свободного члена (мах по модулю отрицательное (-С1; -С2; - С3) =например -Х3);
б) выбор разрешающей строки - для этого находим минимальное частное от деления элементов столбца свободных членов на соответствующем им элементы, разрешающего столбца (Q = мин (В1/А13; В2/А23; В3/А33) - например В2);
в) на пересечении разрешённого столбца и разрешённой строки выбирают разрешённый элемент (А23);
г) выполняем преобразование исходной симплексной таблицы с записью результатов в новую таблицу, начиная всегда с пересчета разрешённого элемента: ;
* пересчет элементов разрешённой строки:
* пересчет элементов разрешённого столбца ; ;
* прочие элементы таблицы внешние свободные члены и элементы F строки вычисления по правилу прямоугольника: проводит прямоугольник ч/з элемент, подлежит пересчету и ч/з разрешённый элемент и пересчет по формуле: ; ;
д) При создании новой симплекс-таблицы необходимой учитываемой изменении, которая возникает при замене в шапке таблицы значения разрешённого столбца и разрешения строки.
е) оптимального решения соответствующего симплекса таблицы y которые все элементы F-строки положительны. До того, момента, когда появляется критерий оптимальной выполняется все вышеперечисленные действия.
|
-X1 |
-X2 |
Y2 |
В |
y1 |
A11 |
A12 |
A13 |
A14 |
-x3 |
A21 |
A22 |
A23 |
A24 |
y3 |
A31 |
A32 |
A33 |
A34 |
F |
A41 |
A42 |
A43 |
A44 |
1.3.5. Не забывайте интерпретировать промежуточные и конечную (оптимизированную) матрицы. Помните, что столбец В – всегда отвечает за результаты (это и значение вариантов, и величина возможных остатков), строка F – это всегда влияние на целевую функцию, величина переменных стоящих или вышедших в столбцы (кроме В) =0. Пересечение Х и У – это количество вовлеченных (высвобождаемых) ресурсов при изменении структуры выпуска (реализации вариантов); Х и Х – соотношение внедряемых и изымаемых из производства вариантов; У и У - -«»- ресурсов.
1.4.КОНТРОЛЬНЫЙ ПРИМЕР .
Необходимо решить экономическую задачу линейного программирования с использованием графического метода решения.
Экономическое содержание задачи состоит в следующем:
Швейная фабрика выпускает два вида изделий: костюм мужской "двойка" и жилеты. Для выпуска продукции используется два вида материала, а именно : ткань костюмная и ткань подкладочная; а также используется фурнитура. Предприятие располагает данными видами ресурсов в определённых количествах. Расход материалов и фурнитуры на единицу каждого вида изделия и количество имеющихся на предприятии ресурсов приведены в таблице:
Вид ресурсов |
Расход ресурсов на единицу изделия |
Количество ресурсов, имеющихся у предприятия |
|
Костюм «двойка» |
Жилет |
||
Ткань костюмная, м |
4 |
0,7 |
95000 |
Ткань подкладочная, м |
2 |
0,6 |
49400 |
Фурнитура, шт |
12 |
21 |
660000 |
Необходимо определить максимальный выпуск продукции с учётом имеющихся ресурсов.