Мет по симп. мет.

министерство сельского хозяйства российской федерации

Федеральное государственное образовательное учреждение высшего профессионального образования

«БАШКИРСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ»






Кафедра статистики и информационных систем в экономике




ОПД.Р.02 ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ



Лабораторные занятия №№7,8. Применение симплексного метода для решения задач линейного программирования

Задания к выполнению лабораторной работы



Специальность 080502 Экономика и управление на предприятии (в аграрном производстве)

080801 Прикладная информатика в экономике






Уфа 2006


УДК 519.8
ББК 22.18
Л 12




Рекомендовано к изданию методической комиссией экономического факультета (протокол № 7 от «__29_» мая 2006 г.)




Составитель: ст. преподаватель Сагадеева Э. Ф.


Рецензент: к.т.н., доцент кафедры информатики и информационных технологий Т. Г. Дидык







Ответственный за выпуск: заведующий кафедрой статистики и информационных систем в экономике д.э.н., профессор Рафикова Н.Т.














ОГЛАВЛЕНИЕ


Введение
4

1. Алгоритм симплексного метода
4

2. Пример решения задачи линейного программирования симплексным методом
6

3. Задачи для самостоятельного решения
8

Библиографический список
14



















































Введение


Решение любой ЗЛП можно найти либо симплекс методом, либо симплекс методом с искусственным базисом.
Симплекс метод – это вычислительная процедура, основанная на принципе последовательного улучшения решения.
Симплекс метод позволяет, исходя из известного опорного плана задачи, за конечное число шагов получить ее оптимальное решение.
Каждый из шагов (итераций) состоит в нахождении нового плана, которому соответствует лучшее, или, по крайней мере, не худшее значение целевой функции (по сравнению с предыдущим планом).
Доказано, что если оптимальное решение существует, то оно будет найдено через конечное число шагов.
Если задача не имеет решения или линейная функция не ограничена, симплекс метод позволяет установить это в процессе вычисления.
В отличие от графического метода, симплекс метод позволяет решать задачи не с двумя, а с п переменными.
Симплексный метод - это вычислительная процедура, основанная на принципе последовательного улучшения решений при переходе от одной базисной точки (базисного решения) к другой. При этом значение целевой функции улучшается.
Базисным решением является одно из допустимых решений, находящихся в вершинах области допустимых значений. Проверяя на оптимальность вершину за вершиной симплекса, приходят к искомому оптимуму. На этом принципе основан симплекс-метод.
Симплекс - это выпуклый многоугольник в n-мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости (гиперплоскость делит пространство на два полупространства).
Например, линия бюджетных ограничений делит блага на доступные и недоступные.
Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число итераций (шагов), кроме случаев «зацикливания».

1 Алгоритм симплексного метода.

Алгоритм симплексного метода состоит из ряда этапов
Первый этап. Строится исходная ОМ. Далее исходная матрица условий преобразуется в приведенную каноническую форму, которая среди всех других канонических форм выделяется тем, что:
а) правые части условий (свободные члены bi) являются величинами неотрицательными;
б) сами условия являются равенствами;
в) матрица условий содержит полную единичную подматрицу.
Если свободные члены отрицательные, то обе части неравенства умножаются на -1, а знак неравенства меняется на противоположный. Для преобразования неравенств в равенства вводятся дополнительные переменные, которые, обычно, обозначают объем недоиспользованных ресурсов. В этом их экономический смысл.
Наконец, если после добавления дополнительных переменных, матрица условий не содержит полную единичную подматрицу, то вводятся искусственные переменные, которые не имеют никакого экономического смысла. Они вводятся исключительно для того, чтобы получить единичную подматрицу и начать процесс решения задачи при помощи симплексного метода.
В оптимальном решении задачи все искусственные переменные (ИП) должны быть равными нулю. Для этого вводят ИП в целевую функцию задачи с большими отрицательными коэффициентами (-М) при решении задачи на max, и с большими положительными коэффициентами (+М), когда задача решается на min. В этом случае даже незначительное ненулевое значение ИП будет резко уменьшать (увеличивать) значение целевой функции. Обычно М в 1000 раз должно быть больше, чем значения коэффициентов при основных переменных.
Второй этап. Строится исходная симплекс-таблица и отыскивается некоторое начальное базисное решение. Множество переменных, образующих единичную подматрицу, принимается за начальное базисное решение. Значения этих переменных равны свободным членам. Все остальные внебазисные переменные равны нулю.
Третий этап. Проверка базисного решения на оптимальность осуществляется при помощи специальных оценок коэффициентов целевой функции. Если все оценки коэффициентов целевой функции отрицательны или равны нулю, то имеющееся базисное решение - оптимальное. Если хотя бы одна оценка коэффициента целевой функции больше нуля, то имеющееся базисное решение не является оптимальным и должно быть улучшено.
Четвертый этап. Переход к новому базисному решению. Очевидно, что в оптимальный план должна быть введена такая переменная, которая в наибольшей степени увеличивает целевую функцию. При решении задач на максимум прибыли в оптимальный план вводится продукция, производство которой наиболее выгодно. Это определяется по максимальному положительному значению оценки коэффициента целевой функции.
Столбец симплексной таблицы с этим номером на данной итерации называется генеральным столбцом.
Далее, если хотя бы один элемент генерального столбца аij0 строго положителен, то отыскивается генеральная строка (в противном случае задача не имеет оптимального решения).
Для отыскания генеральной строки все свободные члены (ресурсы) делятся на соответствующие элементы генерального столбца (норма расхода ресурса на единицу изделия). Из полученных результатов выбирается наименьший. Соответствующая ему строка на данной итерации называется генеральной. Она соответствует ресурсу, который лимитирует производство на данной итерации.
Элемент симплексной таблицы, находящийся на пересечении генеральных столбца и строки, называется генеральным элементом.
Затем все элементы генеральной строки (включая свободный член), делятся на генеральный элемент. В результате этой операции генеральный элемент становится равным единице. Далее необходимо, чтобы все другие элементы генерального столбца стали бы равны нулю, т.е. генеральный столбец должен стать единичным. Все строки (кроме генеральной) преобразуются следующим образом. Полученные элементы новой строки умножаются на соответствующий элемент генерального столбца и полученное произведение вычитается из элементов старой строки.
Значения новых базисных переменных получим в соответствующих ячейках столбца свободных членов.
Пятый этап. Полученное базисное решение проверяется на оптимальность (см. третий этап). Если оно оптимально, то вычисления прекращаются. В противном случае необходимо найти новое базисное решение (четвертый этап) и т. д.

2 Пример решения задачи линейного программирования симплексным методом

Пусть необходимо найти оптимальный план производства двух видов продукции (х1 и х2).
Исходные данные:


Вид продукции
Норма расхода ресурса на единицу прибыли
Прибыль на единицу изделия


А
В


1

5
8
7

2

20
4
3

Объем ресурса
20
36



Построим экономико-математическую модель
13 EMBED Equation.2 1415

13 EMBED Equation.2 1415 - ограничение по ресурсу А;
13 EMBED Equation.2 1415 - ограничение по ресурсу В.
Приведем задачу к приведенной канонической форме. Для этого достаточно ввести дополнительные переменные Х3 и Х4. В результате неравенства преобразуются в строгие равенства.
13 EMBED Equation.2 1415
13 EMBED Equation.2 1415
Построим исходную симплексную таблицу и найдем начальное базисное решение. Им будут дополнительные переменные, т. к. им соответствует единичная подматрица.
x3=20 и x4=36

Базисные
переменные
Свободные
члены (план)
x1
x2
x3
x4

x3
20
5
2
1
0

x4
36
8
4
0
1

Fj - Cj

7
3
0
0


1- я итерация. Находим генеральный столбец и генеральную строку
max (7,3) = 7
13 EMBED Equation.2 1415
Генеральный элемент равняется 5.

Базисные
переменные
Свободные
члены (план)
x1
x2
x3
x4

x1
4
1
0.4
0.2
0

x4
4
0
0.8
-1.6
1

Fj - Cj
28
0
0.2
-1.4
0


2-я итерация. Найденное базисное решение не является оптимальным, т. к. cтрока оценок (Fj-Cj) содержит один положительный элемент. Находим генеральный столбец и генеральную строку:
max (0,0.3,-1.4,0) = 0.2

13 EMBED Equation.2 1415

Базисные
переменные
Свободные
члены (план)
x1
x2
x3
x4

x1
2
1
0
1
-0.5

x2
5
0
1
-2
1.25

Fj - Cj
29
0
0
-1
-0.25



Найденное решение оптимально, так как все специальные оценки целевой функции Fj - Cj равны нулю или отрицательны. F(x)=29 x1=2; x2=5.

3 Задачи для самостоятельного решения

Для приведенных ниже задач составить экономико-математическую модель и решить симплексным методом.
Издательский дом "Садовод" издает два журнала: "Пчеловод" и "Сад и огород", которые печатаются в трех типографиях: "Типография МК", "Полиграф" и "Труд", где общее количество часов, отведенное для печати, и производительность печати одной тысячи экземпляров ограничены и представлены в следующей таблице.
Типография
Время печати 1000 экз.
Ресурс времени, отведенный типографией, час



"Пчеловод"
"Сад и огород"



Типография МК
6
8
80

Полиграф
4
6
120

Труд
4
5
70

Оптовая цена, руб./шт.
22
25


Спрос на журнал "Пчеловод" составляет 12 тыс. экз. а на журнал "Сад и огород" не более 14 тыс. экз. в месяц.
Определите, какое оптимальное количество журналов надо издавать, чтобы обеспечить максимальную выручку от продажи.
2. Молочный комбинат освоил выпуск новых видов сыров "Приятный" и "Смачный", спрос на которые составляет соответственно не более 15 и 12 т в месяц. По причине занятости четырех цехов выпуском традиционных видов молочных продуктов каждый цех может выделить только ограниченный ресурс времени в месяц. В силу специфики технологического оборудования затраты времени на производство сыров разные и представлены в таблице.
Определить оптимальный объем выпуска названных сыров, обеспечивающий максимальную выручку от их продажи.

Номер цеха
Время на производство сыра, час
Время, отведенное цехами на производство, час/мес.



"Приятный "
"Смачный "



1
2
1
66

2
3
5
45

3
2.
4
58

4
1
6
72

Оптовая цена, руб./т
7800
8400




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

Вещества
Содержание питательных веществ
Нормы потребления, г



Яблоки
Ягоды



Р,
3
1
18

Р2
1
2
20

Рз
2
5
40

Р4
0
2
14

Р5
2
4
32

Цена, руб. /кг
30
40


Определите, какое количество фруктов и ягод необходимо купить за сезон, чтобы выполнить предписание врача с минимальными расходами.
4. Торговое предприятие реализует 2 группы товаров А и В. Нормы затрат ресурсов на каждый тип товаров, лимиты ресурсов, а также доход на единицу каждой продукции заданы в таблице. Определить плановый объем продаж и структуру товарооборота так, чтобы доход торгового предприятия был максимален.

Виды ресурсов
Норма затрат ресурсов на 1 ед. товара
Лимит ресурсов



Товары группы А
Товары группы В



Рабочее время продавцов, чел.-час
0,2
3
24

Площадь торговых залов, м2
0,5
0,1
5

Площадь складских помещений, м2
3
1
32

Накладные расходы, руб.
5
4
75

Доход на ед. продукции, руб.
4
3



5. При откорме каждое животное должно получить не менее 12 ед. белков, 9 ед. углеводов и 13 ед. жиров. Для составления рациона используют два вида корма, представленные в следующей таблице.

Питательные вещества
Количество единиц питательных веществ на 1 кг



Корма 1
Корма 2

Белки
3
1

Углеводы
1
2

Жиры
2
5

Стоимость 1 кг корма первого вида 4 ден. ед., второго 6 ден. ед. Составьте дневной рацион питательности, имеющий минимальную стоимость.
6. Фирма изготавливает два вида красок: для внутренних (В) и для наружных (Н) работ. Для их производства используют исходные продукты: пигмент и олифу. Расходы исходных продуктов и максимальные суточные запасы приведены в таблице.
Исходный продукт
Расход исходных продуктов на 1 т краски
Суточный запас, т



Краска Н
Краска В



Пигмент
1
2
14

Олифа
2
1
18

Изучение рынка сбыта показало, что суточный спрос на краску для наружных работ никогда не превышает 4 т в сутки. Цена продажи 1 кг краски для наружных работ 60 руб., а для внутренних работ 90 руб.
Какое количество краски каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным?

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

Станок
Трудоемкость на 1 ед. продукции
Фонд времени, час



I
П



1
3
3
15

2
2
6
18

3
4
0
16

4
1
2
8

Прибыль на ед. продукции
2
3


Составьте план выпуска продукции, обеспечивающий предприятию наибольшую прибыль.
8. Телевизионный завод выпускает 2 вида телевизоров, причем суточное плановое задание составляет не менее 100 телевизоров серии ТВ-1 и 80 телевизоров серии ТВ-2.
Суточные ресурсы фабрики следующие: 800 ед. производственного оборудования, 600 ед. сырья и 480 ед. электроэнергии, расход которых на производство одного телевизора каждого типа представлены в таблице.


Ресурсы
Телевизоры



ТВ-1
ТВ-2

Оборудование
2
4

Сырье
3
2

Электроэнергия
4
1

Себестоимость каждой серии телевизора соответственно равна: ТВ-1 - 6400 руб., ТВ-2 - 8200 руб.
Необходимо определить, сколько телевизоров каждого вида следует выпустить, чтобы общая стоимость выпускаемой продукции была максимальной.
9. Для приобретения оборудования, размещаемого на производственной площади 32 м2, фирма выделяет 24 тыс. руб.
Имеются единицы оборудования двух типов: оборудование типа А стоимостью 3 тыс. руб., требующее производственную площадь 8 м2 и имеющее производительность 4 тыс. единиц продукции за смену, и типа Б стоимостью 6 тыс. руб., занимающее производственную площадь 5 м2 и имеющее производительность 5 тыс. единиц продукции за смену.
Требуется рассчитать оптимальный вариант приобретения оборудования, обеспечивающий максимум производительности участка.
10. Для изготовления двух видов продукции Р1 и Р2 используют следующие ресурсы: 81, 52, 53, 54. Запасы ресурсов и затраты каждого на единицу продукции приведены в таблице.

Ресурс
Запас ресурса
Число ед. ресурсов, затрачиваемых на изготовление ед. продукции





Р,
Р2

51
21
1
3

52
18
2
1

53
6

1

54
15
3
5

Прибыль, получаемая от единицы продукции Р1 и Р2, соответственно 2 и 5 руб.
Составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.
11. Для кормления птицы используется два типа корма, содержащие питательные вещества витамины А, В, С. Содержание числа единиц
витаминов в 1 кг каждого вида корма и необходимый минимум их приведен в таблице (цифры условные).
Витамин
Необходимый минимум витамина
Число ед. витамина в 1 кг корма





1-й корм
2-й корм

А
9
3
1

В
8
1
2

С
12
1
6

Стоимость 1 кг корма 1-го и 2-го типов соответственно 4 и 6 руб.
Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ (витаминов) было бы не менее установленных пределов.
12. Звероферма выращивает черно-бурых лисиц и песцов.На звероферме имеется 10 000 клеток. В одной клетке могут быть либо две лисы, либо 1 песец. По плану на ферме должно быть не менее 3000 лис и 6000 песцов. В одни сутки каждой лисе необходимо выдавать 4 ед. корма, а каждому песцу 5 ед. Ферма ежедневно может иметь не более 200 000 ед. корма. От реализации одной шкурки лисы ферма получает прибыль 10 ден. ед., а от реализации одной шкурки песца 5 ден. ед.
Какое количество лисиц и песцов нужно держать на ферме, чтобы получить наибольшую прибыль?
13. Цех выпускает в смену трансформаторы двух видов. Для их изготовления используются железо и проволока. Общий запас железа 24 т, проволоки 18 т. На один трансформатор первого вида расходуются 3 кг железа и 3 кг проволоки, а на один трансформатор второго вида 4 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 ден. ед., второго 4 ден. ед.
Составьте план выпуска трансформаторов, обеспечивающий заводу максимальную прибыль в смену, если в смену должно выпускаться не менее 4 трансформаторов 1-го вида.
.Фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входят 300 г азотных, 400 г фосфорных и 100 г калийных удобрений, а в улучшенный 200 г азотных, 600 г фосфорных и 200 г калийных удобрений. Известно, что для некоторого газона требуется не менее 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Обычный набор стоит 30 руб., а улучшенный 40 руб. Сколько и каких наборов удобрений надо купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?
15. Фирма производит две модели шкафов А и В. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3 м2 досок, а для изделия модели В 4 м2. Фирма может получать от своих поставщиков до 1700 м2 досок в неделю. Для каждого изделия модели А требуется 12 мин машинного времени, а для изделия модели В 30 мин. В неделю можно использовать 160 ч машинного времени. Сколько изделий каждой модели следует выпускать фирме в неделю, если каждое изделие А приносит 2 руб. прибыли, а каждое изделие модлеи В – 4 руб.?



БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Алесинская Т. В. Экономико-математические методы и модели. Учебное пособие по решению задач по курсу ЭММиМ. – Таганрог, ТГРУ, 2002. – 153 с.
Бережная Е. В., Бережной В. И. Математические методы моделирования экономических систем: Учеб. пособие. – М.: Финансы и статистика, 2001. – 368 с.
Исследование операций в экономике: Учебн. пособие для вузов. / Под ред. Н. Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997. – 407 с.
Невежин В. П., Кружилов С. И. Сборник задач по курсу «Экономико-математическое моделирование». – М.: ОАО «Изд. Дом «Городец», 2005. – 320 с.
Фомин Г. П. Математические методы и модели в коммерческой деятельности: Учебник. – М.: Финансы и статистика, 2001. – 544 с.
Шапкин А. С., Мазаев Н. П. Математические методы и модели исследования операций: Учебник. –М.: «Дашков и Ко», 2004. – 400 с.
Экономико-математические методы и модели: Учеб. пособие для студентов экономических специальностей вузов. /Под ред. А. В. Кузнецова (Н. И. Холод, А. В. Кузнецов, Я. Н. Жихар) – Мн.: БГЭУ, 2000. – 413 с.






















































Лицензия РБ на издательскую деятельность №0261 от 10 апреля 1998 года.
Подписано в печать ___________ 2006 г. Формат 60х84. Бумага типографская. Гарнитура Таймс. Усл. печ. л. _______. Усл. изд. л. _______. Тираж _______экз. Заказ № __________.
Издательство Башкирского государственного аграрного университета.
Кафедра статистики и информационных систем в экономике































13PAGE 15


13PAGE 14615







Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native

Приложенные файлы

  • doc 26308109
    Размер файла: 378 kB Загрузок: 0

Добавить комментарий