Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

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

АГРАРНЫЙ УНИВЕРСИТЕТ»

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

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

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ЛАБОРАТОРНЫМ ЗАНЯТИЯМ И САМОСТОЯТЕЛЬНОЙ РАБОТЕ СТУДЕНТОВ

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

Специальность: 120301 Землеустройство

120302 Земельный кадастр

120303 Городской кадастр

Уфа 2011

УДК 378.147:004.02

ББК 74.58:32.973-018

М 54

Рекомендовано к изданию методической комиссией экономического факультета (протокол № _ от _________ 2011 г.).

Составитель: доцент Аслаева С.Ш.

Рецензент: профессор кафедры экономической теории, д.э.н Нусратуллин В.К.

Ответственный за выпуск: заведующий кафедрой статистики и информационных систем в экономике, доцент, к.э.н Аблеева А.М.

ОГЛАВЛЕНИЕ

Введение

1. Геометрическая интерпретация и графический метод решения ЗЛП

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

3. Освоение ППП SIMPLEX - пакет линейной оптимизации

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

5. Задачи распределительного типа, решаемые в землеустройстве

6. Освоение ППП PER - пакета экономических расчетов. Решение транспортной задачи

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

ВВЕДЕНИЕ

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

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

Одно из достоинств метода моделирования состоит в возможности построения моделей с “удобной” структурой, что делает исследование модели более легким, чем исследование оригинала.

Цель

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

Задачи

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

1. Геометрическая интерпретация и графический метод решения ЗЛП

ВВЕДЕНИЕ

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

1.1 Цель

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

1.2 Задачи

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

1.3 Алгоритм решения

С учетом системы ограничений строим область допустимых решений

Строим вектор наискорейшего возрастания целевой функции -- вектор градиентного направления.

Проводим произвольную линию уровня

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

Определяем оптимальный план и экстремальное значение целевой функции .

1.4 Пример решения задачи

Гражданин, отделившийся от сельскохозяйственного предприятия, решил заняться фермерским хозяйством, средняя доля по району составила 6 гектар. В долевую собственность вошло две семьи из 13 человек (13*6 = 78) итого в собственность они получили 78 га и решил взять в аренду ещё 290 га. Итого, в общем, площадь составила 368 га.

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

У гражданина имеется в наличии 5 тыс. чел/час трудовых ресурсов, 1100 кг действующего вещества удобрений.

Капуста и морковь характеризуются такими показателями, как:

- затраты труда на обработку 1 га капусты 11 чел/час, моркови - 9 чел/час;

- затраты удобрений на обработку 1 га капусты 4 кг.д.в., моркови - 5 кг.д.в.

- урожайность капусты составляет 260 ц/га, моркови - 196 ц/га.

Выход продукции в рублях: капуста 182000 руб с га, морковь 117600 руб с га.

Урожайность составляет: капуста 260 ц, морковь 196 ц.

С учётом севооборота морковью занять не менее 75 га. Капусту требуется получить по условию контракта не менее 23000 ц. Найти оптимальное сочетание этих двух культур.

Решение

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

Переменные:

Х1 - площадь под капусту, га;

Х2 - площадь под морковь, га.

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

1. По использованию пашни, га: Х1 + Х2 ? 368.

2. По использованию и наличию трудовых ресурсов, чел/час: 11Х1 + 9Х2 ? 5000.

3. По использованию и наличию удобрений, кг.д.в.: 4Х1 + 5Х2 ? 1100.

4. По площади под морковь, га: Х2 ? 75.

5. Ограничения по производству капусты, ц: 260Х1 ? 23000

Условие неотрицательности: Х1 ? 0 и Х2 ? 0.

Целевая функция: Z = 182000Х1 + 117600Х2 => max.

Построение матрицы модели

Таблица 1 Матрица модели

Ограничения	Капуста	Морковь	Объём ограничения
1. По наличию и использованию пашни, га	1	1	? 368
2. По наличию и использованию трудовых ресурсов, чел.-час.	11	9	? 5000
3. По наличию использования удобрений, кг.д.в.	4	5	? 1100
4. По площади моркови, га	-	1	? 75
5. По производству капусты, ц.	260	-	23000
6. Целевая функция, руб.	182000	117600	=> max

В результате получили математическую модель:

Z(x) = 182000X1 + 117600X2 => max.

X1 + X2 ? 368,

11X1 + 9X2 ? 5000,

4X1 + 5X2 ? 1100,

X2 ? 75,

260X1 23000,

X1,X2 ? 0.

Решаем задачу:

1. С учетом системы ограничений строим область допустимых решений .

Строим систему координат Х1ОХ2. Строим прямые

X1 + X2 = 368 11X1 + 9X2 =5000 4X1 + 5X2 = 1100

Х1	0	454
Х2	555	0
Х1	0	368
Х2	368	0
Х1	0	275
Х2	220	0

X2 = 75 260X1 = 23000.

Х1	0	10
Х2	75	75
Х1	88	88
Х2	0	100

Х2

C

В

А С

Х1

Рис.1 Графический метод решения ЗЛП

Полученные прямые делят плоскость на две полуплоскости. Для того чтобы узнать, какая именно из этих полуплоскостей отвечает данным неравенствам, подставляем координаты любой точки в неравенство. Полуплоскость, в которой лежит точка, для которой неравенство верно, соответствует неравенству. Например, координаты т.О (0,0) подставляем в неравенство X1 + X2 ? 368, 0+0 ? 368, следовательно полуплоскость, которой принадлежит т. О соответствует неравенству. Следовательно, эту область заштриховываем (рис.1). Область АВC соответствует всем неравенствам, следовательно это область допустимых решений (в ней пересекаются все штрихи).

2. Строим вектор градиент N (182000, 117600). Начало вектора в т. О(0,0).

3. Z0 линия уровня нуль - проходит через точку О (0;0), Z0 + C.

4. Линию уровня Z двигаем вдоль вектора градиента C (182000, 117600). Функция достигает min в точке А, max в точке С.

5. Находим координаты точки С из системы уравнений:

Х2 = 75,

4Х1 + 5Х2 =1100.

C (181,25; 75)

Z = 182600 · 181,25 + 117600 · 75 = 32987500 + 8820000 = 41807500

Ответ: Максимальная стоимость продукции составит 41807500 руб., если площадь посева капусты составит 181,25 га и площадь посева моркови 75 га.

1.5 Задачи

1.5.1 Составить экономико-математическую модель и решить графическим методом

Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа - 3 т, проволоки - 18 т. На один трансформатор первого вида расходуются 5 кг железа и 3 кг проволоки, а один трансформатор второго вида расходуются 3 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д. е., второго - 4 д. е.

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

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

Таблица 1.2 Исходные данные

Затраты	Партия из 100 плит	Имеющиеся ресурсы
	обычных	улучшенных
Материал, фунты Время на прессование, часы Время на отделку, часы Средства, доллары	20 4 4 30	40 6 4 50	4000 900 600 6000

Лицей арендует сельскохозяйственные земли на площади 150 гектар и хочет заняться выращиванием такой растениеводческой продукции как сахарная свёкла и картофель.

У гражданина имеется в наличии 4 тыс. чел/час трудовых ресурсов, 1000 кг. д.в. удобрений.

Сахарная свекла и морковь, характеризуются такими показателями как:

- затраты труда на обработку 1 га сахарной свеклы 11 чел/час, картофель - 6 чел/час;

- затраты удобрений на обработку 1 га сахарной свеклы 5 кг.д.в., моркови - 2 гк.д.в.

- урожайность сахарной свеклы составляет 215 ц/га, картофеля - 175 ц/га.

Выход продукции в рублях: сахарной свёклы 95600 руб./ га, картофеля - 85000 руб./ га. С учётом севооборота картофелем занять не менее 55 гектаров. Сахарную свёклу требуется получить по условию контракта не более 13000 центнеров. Найти оптимальное сочетание этих двух культур.

В хозяйстве производится молоко, а также зерно для продажи и на корм скоту. На продажу используется 60% зерна. По условиям содержания животных на ферме хозяйство может содержать не более 110 коров. Общая площадь пашни в севообороте, выделенная для посева зерновых - 1500 га. Трудовые ресурсы хозяйства составляют 12000 чел.-ч. Норма трудозатрат при производстве при производстве зерна - 5 чел.-ч./га, при производстве молока - 50 чел.-ч./гол.. Урожайность пшеницы - 25 ц.к.е./га. Норма кормления коров - 80 ц.к.е./гол., продуктивность молочного стада - 4000 кг./гол. Плановое задание по молоку составляет 400 ц. Доход хозяйства определяется продажей молока и товарного зерна. Чистый доход от продажи одного центнера зерна 10 руб, одного кг молока -0,2 руб. Необходимо определить сочетание двух отраслей хозяйства, обеспечивающее максимум чистого дохода.

Продукция двух видов (краска для внутренних и наружных работ) поступает в оптовую продажу. Для производства красок используется два исходных продукта А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 т., соответственно. Расходы продуктов А и В на 1 т соответствующих красок приведены в таблице.

Таблица 1.3 Исходные данные

Исходный продукт	Расход исходных продуктов на тонну краски, 1 т.	Максимально возможный запас, т.
	краска Е	краска I
А	1	2	6
В	2	1	8

Изучение рынка сбыта показало, что суточный спрос на краску I никогда не превышает спроса на краску Е более чем на 1 т. Кроме того, установлено, что спрос на краску I никогда не превышает 2 т. в сутки. Оптовые цены одной тонны красок равны 3000 ден. Ед. для краски Е и 2000 ден. Ед. для краски I. Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?

Организации, занимающейся перевозкой и продажей продукции, необходимо перевезти партию товара. При этом можно арендовать для перевозки по железной дороге пяти и семи тонные контейнеры. Пятитонных контейнеров имеется в наличии не более 12 штук, а семитонных не более 18 штук. На перевозку всей продукции по смете выделено не более 60000 рублей, причем цена за аренду пятитонного контейнера - 2000 рублей, а семитонного - 3000 рублей. Определить, сколько и каких контейнеров следует арендовать, при условии, что общий объем грузоперевозок должен быть максимальным.

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

Таблица 1.4 Исходные данные

Показатели	Судно
	1	2
Пассажировместимость, чел.	2000	1000
Горючее, т	12000	7000
Экипаж, чел.	250	100

В месяц используется 60000 тонн горючего. Потребность в рабочей силе не превышает 700 человек. Определите количество судов 1 и 2 типа, чтобы обеспечить максимальный доход, который составляет от эксплуатации судов 1 типа 20 млн.руб., а 2 типа-10 млн.руб. в месяц.

Фермерское хозяйство занимается производством и реализацией астениеводческой продукции. На нее имеются следующие ограниченные ресурсы: посевная площадь 600 га, семена пшеницы 400 ц, ячменя 300 ц, удобрений 5000 кг. Найти оптимальное сочетание сельскохозяйственных культур для получения максимальной прибыли.

Таблица 1.5 Исходные данные

Показатели	Пшеница	Ячмень
Норма высева, ц/га	2,5	2,5
Норма внесения удобрения, ц/га	20	15
Затраты на 1 га, руб	4300	3500
Урожайность, ц/га	26	22
Цена реализации 1 ц, руб	250	200

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

=> max (min),

2.2 Z(x) = -2x1 + 5x2 > max (min)

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Z (x) = x1 + 6x2 > max (min)

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

=> max (min)

Z (x) = x1 + x2 > max (min)

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Z (x) = -2x1 + 6x2 > max (min)

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

ВВЕДЕНИЕ

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

Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит:

умение находить начальный опорный план;

наличие признака оптимальности опорного плана;

умение переходить к нехудшему опорному плану.

2.1 Цель

Усвоить алгоритм решения задач линейного программирования симплексным методом, М-метод.

2.2 Задачи

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

2.3 Алгоритм решения

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

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

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

2. Проверяем нельзя ли за счет одной из переменных приравненной к нулю (небазисной), улучшить значение целевой функции, придавая ей отличные от нуля значения. Если это, возможно, перейдем к третьему этапу, в противном случае прекратим вычисления.

3. Найдем предельное значение переменной, за счет которой можно улучшить значение целевой функции. Увеличение значения этой переменной допустимо до тех пор, пока одна из m переменных, вошедших в пробное решение не обратится в нуль.

4. Разрешим систему из n уравнений относительно переменной, вошедшей в новое пробное решение. Вернемся ко второму этапу.

2.4 Пример решения задачи

Найти оптимальное сочетание посевов пшеницы и сахарной свеклы, обеспечивающий максимум прибыли. Под эти культуры хозяйство выделило ресурсы 1000 га пашни, 18000 чел.- дней труда, 3000 ц минеральных удобрений. В таблице 2.1 представлены исходные показатели.

Таблица 2.1 Исходные показатели

Показатели	Пшеница	Сахарная свекла
Труд, чел.-дней Минеральное удобрение, ц Прибыль, тыс.руб.	7 2 150	40 9 300

Решение.

Переменные:

Х1 - площадь под пшеницу, га;

Х2 - площадь под сахарную свеклу, га.

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

1. По площади пашни, га

X1 +Х2 ? 1000,

2. По затратам труда, чел.-дней

7Х1 +40Х2 ? 18000;

3. По использованию минеральных удобрений, ц

2Х1 +9Х2 ? 3000;

Z (мах прибыли, руб.) =150Х1 +300Х2 > max.

Решение задачи

Предварительный шаг. Приведем к каноническому виду:

7х1 +40х2 +х3 =18000,

2х1 +9х2 +х4 =3000,

х1 +х2+х5 =1000.

Х1 , Х2 0,

Z =150х1 +300х2+ 0х3 +0х4 +0х5 > max.

Интерация 1.

Шаг1. Выписываем исходное допустимое базисное решение и соответствующее ему значение целевой функции.

х3, х4, х5 - базисные переменные.

х1 х2 х3 х4 х5

Х = 0 0 18000 3000 1000

Z = 150·0+300·0+0·18000+0·300+0·1000 = 0.

Шаг2. Проверяем оптимальность полученного решения. Если решение не оптимально, то переходим к шагу 3. В противном случае записываем ответ.

Пусть ? х1 =1, тогда ? х3 =-7, ? х4 =-2, ? Х5 =-1

?Z=150·1+300·0+0·(-7)+0·(-2)+0·(-1)=150. Так как ?Z 0, то переменную х1 целесообразно ввести в базис.

Шаг3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.

х3 0 х3 =18000 - 7х1, 18000 - 7х1 0, х1 257,1,

х4 0 х4 =300 - 2х1, 300-2х1 0, х1 1500,

х5 0 х5 =100 - х1, 100 - х1 0, х1 100.

Решением системы неравенств является третье неравенство, поэтому из базиса выводим переменную х5.

Шаг 4. Пересчитываем систему уравнений задачи с учетом нового состава базисных переменных.

3 уравнение х1 +х2+х5 =1000,

1 уравнение _7х1 +40х2 +х3 =18000

7х1 +7х2+7х5 =7000

33х2 +х3 - 7х5 =11000,

2 уравнение _2х1 +9х2 +х4 =3000

2х1 +2х2+2х5 =2000

7х2+х4 - 2х5 = 1000.

В результате имеем следующую систему уравнений:

33х2 +х3 - 7х5 = 11000,

7х2+х4 - 2х5 = 1000,

х1 +х2+х5 =1000.

Итерация 2.

Шаг1. Выписываем исходное допустимое базисное решение.

х3, х4, х1 - базисные переменные.

х1 х2 х3 х4 х5

Х = 1000 0 11000 1000 0

Z=150·1000+300·0+0·11000+0·1000+0·0=150000

Шаг2. Проверяем оптимальность полученного решения.

Пусть ? х2 =1, тогда ? х3 =-33, ? х4 = -7, ? Х5 = -1

?Z=150·(-1)+300·1+0·(-33)+0·(-7)+0·0=150. Так как ?Z 0, то переменную х2 целесообразно ввести в базис.

Шаг 3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.

х3 0 х3 =11000 - 33х2, 11000 - 33х2 0, х2 333,3,

х4 0 х4 =1000 - 7х2, 1000 -7х2 0, х2 142,9,

х1 0 х1 =1000 - х2, 1000 - х2 0, х2 1000.

Переменную х4 выводим из базиса.

Шаг4. Пересчитываем систему уравнений задачи с учетом нового состава базисных переменных.

2 уравнение 7х2+х4 - 2х5 = 1000,

х2+1/7х4 - 2/7х5 = 1000/7,

3 уравнение _х1 +х2+х5 =1000

х2+1/7х4 - 2/7х5 = 1000/7

х1- 1/7х4 +9/7х5 = 857,4,

1 уравнение _33х2 +х3 - 7х5 = 11000

33х2+33/7х4 - 66/7х5 = 33000/7

х3 - 67,15х4 + 2,42х5 = 6285,7.

В результате имеем следующую систему уравнений:

х3 - 67,15х4 + 2,42х5 = 1571,5,

х2+1/7х4 - 2/7х5 = 1000/7,

х1- 1/7х4 +9/7х5 = 6285,7.

Итерация 3.

Шаг1. Выписываем исходное допустимое базисное решение.

х3, х2, х1 - базисные переменные.

х1 х2 х3 х4 х5

Х = 857,4 142,9 6285,7 0 0

Z=150·857,4+300·142,9+0·6285,7+0·0+0·0 = 171429.

Шаг2. Проверяем оптимальность полученного решения.

Пусть ? х4 =1, тогда ? х3 = 67,15, ? х2 = -1/7, ? Х1 = -1/7.

?Z=150·(-1/7)+300·(-1/7)+0·67,15+0·1+0·0 = -64,3. Так как ?Z ? 0, то переменную х4 нецелесообразно вводить в базис.

Пусть ? х5 =1, тогда ? х3 = -66/7, ? х2 = 2/7, ? Х5 = -9/7.

?Z=150·(-9/7)+300·(2/7)+0·66/7+0·0+0·1= -107,4. Так как ?Z ? 0, то переменную х5 нецелесообразно вводить в базис.

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

Ответ: Прибыль будет равна 171429 руб., если посевная площадь под пшеницу составит 857,4 га и сахарную свеклу 142,9 га.

2.5 Задачи

2.5.1 Составить экономико-математическую модель и решить симплекс-методом

Фермерское хозяйство занимается производством зерновых и молока. Имеет следующие ресурсы: пашня - 750 га, труд - 25000 чел-час., удобрения - 6000 кг д.в., денежные средства - 200 тыс. руб. Зерновые в расчете на 1 га посевов характеризуются следующими показателями: затраты труда, 20 чел-час., затраты удобрений 50 кг д.в., урожайность 20 ц/га, затраты денежных средств 250 руб. Затраты на 1 корову: труда 110 чел-час., денежных средств 800 руб., пашни 3 га. Годовой надой на 1 корову 2000 кг. Ожидаемая прибыль от 1 ц зерновых 50 руб., от 1 ц молока 25 руб.

Найти оптимальное сочетание отраслей в хозяйстве. Критерий оптимальности - максимум прибыли.

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

Таблица 2.2 Исходные данные

Производственные ресурсы	Картофель	Ячмень	Объем ресурсов
Пашня, га Затраты труда , чел.-дн Затраты труда механизаторов, тракторо-смен	0,01 0,2 0,021	0,05 0,1 0,03	1000 8000 900
Закупочная цена 1 ц, руб	3	5

Исходя из заданного объема производственных ресурсов добиться максимума валовой продукции в денежном выражении.

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

Таблица 2.4 Исходные данные

Станки	Время работы на станках	Время обработки детали А1	Время обработки детали А2	Время обработки детали А3
1	16	1	2	2
2	28	2	3	2
3	30	3	3	2
Прибыль		4	3	2

Хозяйство занимается такими зерновыми культурами, как пшеница, овес и ячмень. Общая площадь пашни составляет 34 га, выделено трудовых ресурсов 25 чел-час, минеральных удобрений 35 кг.д.в. Пшеница и ячмень характеризуются такими показателями, как затраты труда на 1 га пшеницы 5 чел-час. , овса - 4 чел.-час., ячменя - 3 чел.-час; затраты удобрений на 1 га пшеницы 2кг д.в., на 1 га ячменя 5 кг дв. Выход продукции пшеницы 20000 руб, овса 1400 ячменя 15000 руб. с 1 га. Найти максимальный выход продукции.

2.6 Решить задачу симплекс-методом

2.1 8Х1 + 7Х2 ? 34,

5Х1 + 3Х2 ? 25,

2Х1+ 5Х2 ? 35,

Хi ? 0, i = 1,2

f = 15X1+ 20X2> max.

2.2 Х1 + 3Х2 + Х4 ? 4,

2Х1 + Х2 ? 3,

Х1+ 4Х3 + Х4 ? 3,

Хi ? 0, i = 1,2,3

f = 2X1+ 4X2+ Х3+ Х4 > max.

2.3 X1+2X2 ? 10,

X1+2X2 ? 2,

2X1+X2 ?10,

X1, X2 ? 0,

Z=X1+X2=>min,

2. 4 Z=2X1+X2=>min,

X1-2X2 ? 1,

2X1-X2 ? 1,

4X1-3X2 ? 6,

X1,2 ? 0.

2.5 Z (x) = x1 + x2 > max (min),

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

3. Освоение ППП SIMPLEX - пакет линейной оптимизации

ВВЕДЕНИЕ

Алгоритмы задач принятия решений настолько сложны, что без применения компьютера реализовать их практически невозможно. Компьютер с помощью программного обеспечения реализует алгоритмы поиска оптимального решения, которые преобразуют исходные данные в результат. Комплекс программ «Simplex» предназначен для решения задач линейного программирования на максимум целевой функции в диалоговом режиме. Программный комплекс «Линейная оптимизация» (LO) включает в себя следующие файлы: lo.bat, fr.exe, lo4.exe, lohelp.exe, lpmxverf.exe, vm.exe, vn.exe, lo4.hlp, vm.hlp,lo.doc.

Назначение некоторых из них: lo.bat - основная, управляющая программа комплекса, vn.exe- ввод названий ограничений и переменных, fr.exe- просмотр моделей, lpmxverf.exe- решение математической модели, vm.exe- экранный редактор числовых матриц.

Поиск оптимального решения производится по алгоритму двойственного комплекс- метода с мультипликативным представлением базисной матрицы. Поиску оптимальных решений задач линейного программирования с помощью «Simplex» и посвящено методическое указание.

3.1 Цель

Усвоить алгоритм решения задач линейного программирования на «Simplex».

3.2 Задачи

Составить математическую модель задачи, матрицу модели, ввести условие задачи в «Simplex», решить задачу в «Simplex», создать отчет по результатам решения в «Simplex», провести анализ решения.

3.3 Основное меню комплекса «Simplex»

Состоит из:

1- МОДЕЛИ 2- ВВОД 3- РЕШЕНИЕ 4- ОТЧЕТЫ 5- ВЫХОД

Пункты 1, 2 и 4 этого основного меню имеют подменю.

Подменю п.1: 1- Новая модель

2- Загрузка модели

3- DOS

4- Выход

Подменю п.2: 1- Ввод моделей

2- Ввод названий ограничений и переменных

Подменю п.4: 1- Исходные данные

2- Результаты (полная форма)

3- Результаты (сокращенная форма)

4- Правильность решения

Все программы комплекса имеют встроенную диалоговую подсказку по всем режимам работы. Подсказка всегда соответствует специфике именно той части программы, с которой вы в данный момент работаете. Вызов подсказки - клавиша <F1>.

компьютерный задача линейный программирование

3.4 Рассмотрение простейшего примера решения задач в «Simplex»

В хозяйстве производится молоко, а также зерно для продажи и на корм скоту. По условиям содержания животных на ферме хозяйство может содержать не более 100 коров. Общая площадь пашни в севообороте, выделенная для посева зерновых - 2000 га. Трудовых ресурсов в хозяйстве имеется в наличии 10000 чел.- час. Норма трудозатрат при производстве зерна - 5 чел.-час/га, при производстве молока - 50 чел.- час/гол. Урожайность пшеницы 20 ц.к.е/га, норма кормления коров - 80 ц.к.е./гол. Продуктивность молочного стада - 4000 кг/гол. Плановое задание по молоку составляет 400 ц. Доход хозяйства определяется продажей молока и товарного зерна. Чистый доход от продажи 1 ц зерна 20 руб., 1 кг молока - 0,2 руб. Необходимо определить сочетание 2-х отраслей хозяйства, обеспечивающее максимум дохода.

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

Переменные:

Х1 - площадь под зерновые, га,

Х2 - поголовье коров, гол.

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

1. По площади пашни для посева зерновых, га: Х1 ? 2000.

2. По поголовью коров, гол.: Х2 ?100.

3. По наличию и использованию трудовых ресурсов, чел./час: 5Х1 + 50Х2 ? 10000.

4. По плановому заданию по производству молока, ц: 40Х2 ? 400.

5. Условие неотрицательности: Х1, Х2 ? 0.

Целевая функция (мах чистого дохода, руб.)

Z = 400Х1 +800Х2 мах.

3.4.2 Ввод исходной информации

Ввод исходной информации осуществляется, выбрав первый пункт основного меню - «Модели». Для создания новой модели необходимо выбрать первую строку подменю «МОДЕЛИ» «Новая модель». На экране появляется диалоговое окно, в котором запрашивается имя файла, в который будет записываться создаваемая модель. Здесь необходимо ввести имя своего файла (латинскими буквами, до 8 символов), например model. Вы снова попадаете в подменю. Программа автоматически добавляет к имени файла расширение .ZMP.

Для загрузки уже существовавшей модели (чтения ее с диска) следует выбрать вторую строку из подменю «Модели». Так же, как и при выборе первой строки, на экране появляется небольшое окно, где запрашивается имя файла с вашей моделью. Если вместо конкретного имени модели пользователь вводит символ «», то программа предоставляет возможность выбрать из предоставленного ему списка существующих моделей. Выполнив загрузку модели, программа возвращается в подменю «МОДЕЛИ».

Наши предыдущие действия зарезервировали для модели место на диске и дали ей имя. Теперь, чтобы ввести числовые данные, надо выбрать подменю «ВВОД» основного меню и нажать ENTER. Внизу экрана появится запрос: «Введите через пробел число ограничений и переменных». Мы водим: 4 2 и нажимаем на ENTER.

Команды ввода и редактирования задаются нажатием одной - двух клавиш. Переход по матрице осуществляется с помощью клавиш <Курсор влево>; <Курсор вправо> или пробел; <Курсор вверх>; <Курсор вниз> или <ENTER>.

Для того, чтобы переместится к верхней, нижней, левой или правой границе матрицы, надо нажать клавишу <M> и стрелку с направлением перемещения. Для того, чтобы сместится на одну страницу вверх, вниз, влево, вправо надо нажать клавишу <N> и соответствующую стрелку. <INS><R>- вставка строк. После подачи этой команде программа спрашивает, сколько строк вставить, и вставляет их под ту строку, в которой находился курсор в момент подачи команды. <INS><C>- вставка столбцов. Команда аналогична команде вставки строк. Столбцы вставляются справа от текущего столбца. <DEL><R> - удаление указанного числа строк. Удаляются текущая строка и последующие за ней. <DEL> <C>- удаление указанного числа столбцов. Удаляются текущий столбец и столбцы, стоящие справа от него. Если вместо ввода количества строк (столбцов) после подачи последних четырех команд нажать клавишу <ESC>, выполнение команды будет отменено. <ESC> <Y> - завершение работы и сохранение всех внесенных изменений в файле с заданным вами именем. Если вы нажали на него <ESC> случайно, после повторного нажатия программа вернется в экранный режим.

Вместо знаков ограничений вводятся верхняя и (или) нижняя границы диапазона изменения ограничения в два КРАЙНИХ СПРАВА столбца изображенной на экране матрицы модели. Если ограничение имеет тип «меньше либо равно», свободный член его вводится в столбец верхних границ ограничения («Не более»), а в столбец нижних границ («Не менее») следует ввести знак <->, имеющий в этом случае смысл прочерка. Для ограничения типа «больше либо равно», свободный член помещают в столбец «Не менее», а в столбец «Не более»- минус. Чтобы ввести ограничение типа «равно», следует его свободный член поместить в каждый из упомянутых столбцов. Можно вводить двусторонние ограничения, указав каждую границу в соответствующем столбце.

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

	Х1	Х2	Не менее	Не более
1	1		--	2000
2		1	--	100
3	5	50	--	10000
4		40	400	--
Мах	400	800
Вверх	--	--	--	--
Нижн	0	0	0	0

Рисунок 2 Форма ввода

Для ввода названий ограничений переменных модели выберите вторую строку подменю “ВВОД”. Экран очищается. В верхней его части появляются название переменных текущей модели, а в левой названия ограничений. Каждое название переменной или ограничения представляет собой упорядоченную последовательность символов, состоящую не более, чем четырех строк. На экране название выглядит в виде небольшого окна, внутри которого можно передвигаться, изменяя его содержимое, по правилам экранного редактора.

При вводе названий используются следующие клавиши:

<F2> - переход от редактирования названий переменных к редактированию названий ограничений наоборот;

<СТРЕЛКИ> - перемещение внутри редактируемого названия;

<CTRL>< ENTER> - вставка новой строки в название;

<ENTER> - переход на новую строку без вставки;

<STRL>< Y> - удаление текущей строки без вставки;

<TAB> - переход к следующему столбцу (строке);

<SHIFT><TAB> - переход к предыдущему столбцу (столбу);

<PgUp>< PgDn> - перемещение на страницу вверх (или вниз);

<CTRL>< PgUp> - перемещение к первому столбцу (строке);

< CTRL>< PgDp> - перемещение к последнему столбцу (строке);

<ESC> - завершение ввода.

3.4.3 РЕШЕНИЕ ЗАДАЧИ

Для вывода исходной информации необходимо выбрать строку “Исходные данные” подменю “ОТЧЕТЫ”. Как только осуществляется выбор этого режима, на экране появляется сообщение о формировании файла с исходными данными, записанными в табличном виде. После того, как этот файл сформирован, программа вновь очищает экран и предлагает просмотреть модель. Отчет об исходных данных содержится в файле с именем текущей модели и с расширением “ . ISN”.

Для того, чтобы начать решение введенной задачи, нужно выбрать пункт “РЕШЕНИЕ” основного меню. После этого экран очищается, и поочередно появляются (пробегают) сообщения о действиях программного комплекса. Запись результатов решения производится в файл “SOL . TMP”. Если необходимо ввести результаты решения задачи, после решения надо выбрать строку “Вывод результатов (полная форма)” из подменю “ОТЧЕТЫ”. При этом на экране появляются сообщение: “Запись отчета на диск”. Завершив формирование этого файла, программа вновь очищает экран и выдает запрос: “Укажите количество столбов для вывода ( 1 -15 )”. Здесь 4 - это количество столбцов, предлагаемых программой по умолчанию, вместо этой цифры можно ввести ту, которая Вам нужна. Файл результатов решения (полной матрицы) всегда записывается на диск с именем текущей модели и расширением .RES. Первая часть выходной формы этого файла представляет собой полную матрицу решения задачи. В нее входят произведения коэффициентов исходной модели и полученных о ходе решения значений соответствующих переменных. Запись этой части производится листами по 4 -15 столбцов на каждом листе.

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

1. Столбец номеров ограничений;

2. Столбец знаков ограничений;

3. Столбец свободных членов ограничений;

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

5. Столбец отклонений ограничений ( отклонение свободных членов ограничений от сумм ограничений );

6. Столбец двойственных оценок ограничений

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

1. Система ограничений несовместности;

2. Функционал линейно не ограничен;

3. Решение оптимальное.

3.4.4 Анализ результатов решения

На рисунке 3 представлен полный отчет.

Максимальный чистый доход составит 168000 руб., при этом чистый доход от зерновых составит 760000 руб, от молока 8000 руб. Если в хозяйстве площадь под зерновые составит 1900 га, поголовье коров составит 10 гол. При этом будет затрачено трудовых ресурсов 9500 чел.-час. на обработку пашни под зерновые и 500 чел-час на содержание коров.

В хозяйстве останется неиспользованным 100 га пашни. План по молоку выполняется, молока будет произведено 400 ц. Трудовые ресурсы используются полностью, если количество трудовых ресурсов увеличить на 1 чел-час., то чистый доход увеличится на 80 руб.

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

Решение оптимальное. Z= 768000

1. Матpица pешения.

ЛИСТ 1===============================================

ПЕРЕМЕННЫЕ : X 1 : X 2 : ## :

ЗНАЧЕНИЯ : 1900: 10: :

-------------------------------:-----------:-----------:----:

:площадь под: поголовье :ОГРА:

:зерновые,га: коров,гол :НИЧЕ:

ОГРАНИЧЕНИЯ : : :НИЯ :

: : : :

=====================================================

1 <:по площади пашни для : : : 1:

:посева зерновых,га : 1900: -- : :

2 <:по поголовью коров,гол : -- : 10: 2:

3 <:по трудовым ресурсам,ч/ч : 9500: 500: 3:

4 >:по плановому заданию по : : : 4:

:молоку,ц : -- : 400: :

-------------------------------:-----------:-----------:----:

MAX. :максимальный доход : 760000: 8000: :

-------------------------------:-----------:-----------:----:

ВЕРХ : : -- : -- : :

НИЖН : : 0: 0: :

==================================================

2. Хаpактеpистика огpаничений

======================================================

ОГРАНИЧЕНИЕ :НИЖ.ГРАНИЦА :ВЕР.ГРАНИЦА:СУММА :ОТКЛОНЕНИЕ : ОЦЕНКА ====================================

1 по площади пашни

для посева зерновых,га -- : 2000: 1900 : 100: 0:

2 по поголовью коров,гол -- : 100: 10 : 90: 0:

3 по трудовым ресурсам,ч/ч-- : 10000: 10000: 0: 80:

4 по плановому заданию по

молоку,ц 400: -- : 400: 0: -80: :=============================

Рисунок 3 Полный отчет

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

ВВЕДЕНИЕ

Алгоритмы задач принятия решений настолько сложны, что без применения компьютера реализовать их практически невозможно. Компьютер с помощью программного обеспечения реализует алгоритмы поиска оптимального решения, которые преобразуют исходные данные в результат. Таким программным обеспечением, выполняющим поиск оптимальных решений, является Excel7.0 для Windows95 (и более поздние версии Excel), а также и ППП Simplex. Поиску оптимальных решений задач линейного программирования с помощью Excel7.0 и посвящено методическое указание.

4.1 Цель

Усвоить алгоритм решения задач линейного программирования на Excel.

4.2 Задачи

Составить математическую модель задачи, матрицу модели, ввести условие задачи в Excel, решить задачу в Excel, создать отчет по результатам решения в Excel, провести анализ решения.

4.3 Образец решения задачи

Рассмотрим простейший пример решения задач в Excel.

Условие задачи: В хозяйстве имеется 200 га неиспользуемых земель, пригодных для освоения под пашню и сенокос. Затраты труда на освоение 1 га земель под пашню составляют 37 чел.-ч., в сенокос 1 чел.-ч. Для вовлечения земель в сельскохозяйственный оборот предприятие может затратить не более 1200 чел.-ч. механизированного труда. Стоимость продукции, получаемой с 1 га пашни, составляет 16000 руб., с 1 га сенокосов -2000 руб. В задание на проектирование установлено, что площадь земель осваиваемых под пашню не должна превышать 50 % площади сенокосов. Требуется определить, какую площадь нужно освоить под пашню и сенокосы, чтобы получить максимальное количество продукции в стоимостном выражении.

4.3.1 Построим математическую модель задачи

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

Х1 - площадь земель трансформируемая в пашню, га,

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

Запишем ограничения

1) По площади неиспользуемых земель, пригодных для освоения под пашню и сенокосы, га

Х1 + Х2 ? 200

2) По затратам труда, чел - ч.

37Х1 +Х2 ? 1200

3) По соотношению площадей земель осваиваемых под пашню и под сенокосы, га

Х1 ? 0,5Х2

Наложим условие неотрицательности на переменные

Х1? 0, Х2?0.

Запишем целевую функцию (критерий оптимальности - максимальный выход продукции, рублей)

Z= 16000Х1 +2000Х2 > max

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

4.3.2 Построим матрицу модели

Таблица 4.1 Матрица модели

Ограничения	Площадь под пашню, га, Х1	Площадь под сенокосы, га, Х2	Тип ограничения	Объем ограничения
1. 1. Общая площадь, га 2.Трудовые ресурсы, чел.-ч 2. 3.Соотношение площадей, га Цф (max выход продукции)	1 37 1 1600	1 1 -0,5 2000	<= <= <= =>	200 1200 0 max

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

3 Решим задачу в Excel

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

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

Примечания: 1) Если в меню Сервис отсутствует команда Поиск решения, значит, необходимо загрузить эту надстройку. Для этого выберите команду Сервиса Надстройки и активизируйте надстройку Поиск решения.

2) Если же этой надстройки нет в диалоговом окне Надстройки, то необходимо обратиться к панели управления Windows, щелкнуть по пиктограмме Установка и удаление программ и с помощью программы установки Excel (или Office) установить надстройку Поиск решения.

4.3.3 Последовательность решения задачи

1) Создать форму для ввода условий задачи.

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

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

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

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

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

2) Введем исходные данные в созданную форму.

Получим результат, который представлен на рисунке 3.



Рисунок 3 Форма с введенными исходными данными

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

* Курсор подводим к ячейке, в которой будет находиться значение целевой функции D4; М1 (Обозначим через М1 следующее действие - «один щелчок левой кнопкой мыши»).

* Курсор на кнопку Мастер функции; М1.

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

* Курсор в окно Категория на категорию Математические; Ml.

* Курсор в окно Функции на СУММПРОИЗВ; Ml.

Появится диалоговое окно СУММПРОИЗВ, которое представлено на рисунке 4.

Рисунок 4 Диалоговое окно СУММПРОИЗВ

* В массив 1 диалогового окна СУММПРОИЗВ вводим адреса ячеек В$3:C$3, в которых находятся значения переменных . (Адреса ячеек во все диалоговые окна удобно вводить не с клавиатуры, а протаскивая мышь по ячейкам, чьи адреса следует ввести).

* В массив 2 вводим адреса ячеек В4:C4, в которых находятся коэффициенты целевой функции В4:C4.

* Готово. На экране в D4 введена формула для вычисления целевой функции.

4. Введем зависимость для левых частей ограничений:

* Курсор в D4; M1; Копировать в буфер.

* В ячейку D7 вводим левую часть ограничения Х1+Х 2 формулой СУММПРОИЗВ(В3:C3;B6:C6) для этого подводим курсор в ячейку D7; M1; Вставить из буфера.. Аналогично вводим зависимость в ячейки D8, D9. На этом ввод зависимостей закончен.

В результате значения в ячейках D4, D7, D8, D9 равны нулю. На рисунке 5 представлена форма с введенными формулами в данные ячейки.

Переменные
Имя	x1	x2
Значение			ЦФ	напр
коэфф в ЦФ	16000	2000	=СУММПРОИЗВ(B$3:C$3;B4:C4)	макс
Ограничения
Вид			левая часть	знак	правая часть
Общая площадь, га	1	1	=СУММПРОИЗВ(B$3:C$3;B7:C7)	<=	200
Трудовые рес, чел.-ч	37	1	=СУММПРОИЗВ(B$3:C$3;B8:C8)	<=	1200
Соотношение пл., га	1	-0,5	=СУММПРОИЗВ(B$3:C$3;B9:C9)	<=	0

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

4.3.3 Запуск на решение задачи

1) Запустить Поиск решения.

2) Указать назначение целевой функции (установить целевую ячейку).

3) Установить изменяемые ячейки.

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

5) Ввести параметры для решения задачи линейного программирования (ЗЛП).

1) Запустим Поиск решения.

- в главном меню выбрать команду Сервис,

- из раскрывшего меню выбрать команду Поиск решения,

- появится диалоговое окно Поиск решения.

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

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

* Курсор в поле «Установить целевую ячейку».

* Ввести адрес ячейки $D$4, в котором будет находиться значение целевой функции.

* Ввести направление целевой функции: максимальное значение.

3) Ввести адреса искомых переменных.

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

* Курсор в поле «Изменяя ячейки».

* Ввести адреса ячеек В$3:С$3, в котором будут находиться значения переменных..

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

Рисунок 5 Диалоговое окно Поиск решения

4) Введем ограничения.

* Курсор в поле «Добавить». Появится диалоговое окно Добавление ограничения.

* В поле «Ссылка на ячейку» ввести адрес $D$7.

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

* Курсор в правое окно.

* Ввести адрес $F$7 (рисунок 6).

Рисунок 6 Диалоговое окно Добавление ограничений

* Добавить. На экране опять диалоговое окно Добавление ограничения.

* Ввести остальные ограничения

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

Рисунок 6 Диалоговое окно Поиск решения с введенными данными

5) Ввод параметров для решения ЗЛП.

* Открыть окно Параметры поиска решения.

* Установить флажок Линейная модель, что обеспечивает применение симплекс-метода.

* Установить флажок Неотрицательные значения. После чего нажимаем на клавишу ОК.

* Нажимаем на клавишу Выполнить в диалоговом окне Поиск решения.

Рисунок 7 Решение найдено

Получено оптимальное решение (рисунок 6). То есть, определена площадь неиспользуемых земель, трансформируемая в пашню 27,7778 га, в сенокосы 172,2222 га. Максимальное количество продукции в стоимостном выражении составит 788888,89 рубля. Вся площадь неиспользуемых земель вовлечена в сельскохозяйственный оборот, трудовые ресурсы используются полностью, задание на проектирование выполнено: площадь неиспользуемой земли, трансформируемая в пашню меньше половины площади трансформируемой в сенокосы на 58,3333 га.

4.4 Создание отчета по результатам поиска решения

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

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

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

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

Для этого в появившемся диалоговом окне Результаты поиска решения выбираем тип отчета и нажимаем на клавишу ОК.

При выборе типа отчета «Результаты» появится лист Отчет по результатам1, который представлен на рисунке 8.

Microsoft Excel 10.0 Отчет по результатам
Рабочий лист: [ЭММ.xls]Лист1
Целевая ячейка (Максимум)
	Ячейка	Имя	Исходное значение	Результат
	$D$4	ЦФ	0	788888,889
Изменяемые ячейки
	Ячейка	Имя	Исходное значение	Результат
	$B$3	значение X1, S под пашню, га	0	27,7777778
	$C$3	значение X2, S под сенокосы, га	0	172,222222
Ограничения
	Ячейка	Имя	Значение	Формула	Статус	Разница
	$D$7	общая площадь, га левая часть	200	$D$7<=$F$7	связанное	0
	$D$8	трудовые рес., чел.-ч. левая часть	1200	$D$8<=$F$8	связанное	0
	$D$9	соотношение пл., га левая часть	-58,33333333	$D$9<=$F$9	не связан.	58,333

Рисунок 8 Лист «Отчет по результатам 1»

Отчет по результатам состоит из 3 таблиц:

Таблица 1 приводит сведения о целевой функции: адрес ячейки, в которой находится значение целевой функции, имя, значение - 788888,89 рубля. В столбце Исходное значение приведены значения целевой функции до начала вычислений 0 .

Таблица 2 приводит сведения об искомых переменных Х1 и Х2: адрес ячеек, в которых находятся значения переменных, названия, значения полученные в результате решения задачи, которые соответственно равны 27,7778 и 172,2222. В столбце Исходное значение приведены значения переменных до начала вычислений 0 .

Таблица 3 показывает результаты оптимального решения для ограничений. Для ограничений в графе Ячейка приведены адреса ячеек, в которых находятся, значение левой части ограничения, в графе Имя названия ограничений, в графе Формула приведены зависимости, которые были введены в диалоговое окно Поиск решения; в графе Значение приведены величины использованного ресурса: общей площади 200 га, трудовых ресурсов 1200 чел.-ч., разница между площадью земель осваиваемых под пашню и 50% земель осваиваемых под сенокосы - 58,3333 га; в графе Разница показано количество неиспользованного ресурса: площадь земли 0 га, трудовых ресурсов 0 чел.- ч., площадь, трансформируемая под пашню меньше 50% площади, трансформируемой в сенокосы на 58,3333 га. Если ресурс используется полностью, то в графе Статус указывается связанное; при неполном использование ресурса в этой графе указывается, не связан.

При выборе типа отчета «Устойчивость» появится лист «Отчет по устойчивости 1», который представлен на рисунке 11.

Отчет по устойчивости состоит из 2 таблиц.

В таблице 1 приведены следующие значения для переменных:

- результат решения задачи: площадь земли, трансформируемой под пашню 27,7778 га и под сенокосы 172,2222 га;

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

Примечание: если стоимость ресурсов, затраченных на производство одного изделия, больше его цены, то это изделие не войдет в оптимальный план из-за его убыточности;

- коэффициенты целевой функции при переменной Х1 16000 и при переменной Х2 2000;

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

целевой функции, при которых не меняется оптимальный план исходной задачи. Если увеличить коэффициенты целевой функции при переменной Х1 не более, чем на 58000 и при переменной Х2 не более чем на 14000 оптимальный план не изменится. В графе Допустимое уменьшение содержится информация о допустимом уменьшении коэффициентов целевой функции, при которых не меняется оптимальный план исходной задачи. Если уменьшить коэффициенты целевой функции при переменной Х1 не более чем на 14000 и при переменной Х2 не более чем на 1567,5675 оптимальный план не изменится.

В таблице 2 приводятся аналогичные значения для ограничений:

- величина использованных ресурсов;

-теневая цена, т.е. двойственные оценки, которые показывают, как изменится целевая функция при изменении ресурсов на единицу. Ресурсы земля и труд имеют отличные от нуля оценки 1611,1111 и 308,8889 - эти ресурсы полностью используются в оптимальном плане, являются дефицитными сдерживающими рост целевой функции. Нулевая оценка ресурса свидетельствует о его недефицитности, он не препятствует и дальше максимизировать целевую функцию. Соотношение между площадью земель трансформируемых в пашню и в сенокосы имеет нулевую оценку.