Задача для самостоятельного решения
Необходимо организовать в хозяйстве производство картофеля и ячменя. Картофеля должно быть произведено не более 20000 ц. Наличие ресурсов и их затраты на производство 1 ц картофеля и ячменя приведены в таблице.
Таблица Исходные данные
Производственные ресурсы | Картофель | Ячмень | Объем ресурсов |
Пашня, га Затраты труда , чел.-дн Затраты труда механизаторов, тракторо-смен | 0,01 0,2 0,021 | 0,05 0,1 0,03 | 1000 8000 900 |
Закупочная цена 1 ц, руб | 3 | 5 |
Исходя из заданного объема производственных ресурсов добиться максимума валовой продукции в денежном выражении.
Освоение ППП 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» и посвящено методическое указание.
Цель
Усвоить алгоритм решения задач линейного программирования на «Simplex».
Задачи
Составить математическую модель задачи, матрицу модели, ввести условие задачи в «Simplex», решить задачу в «Simplex», создать отчет по результатам решения в «Simplex», провести анализ решения.
Основное меню комплекса «Simplex»
Состоит из:
1- МОДЕЛИ 2- ВВОД 3- РЕШЕНИЕ 4- ОТЧЕТЫ 5- ВЫХОД
Пункты 1, 2 и 4 этого основного меню имеют подменю.
Подменю п.1: 1- Новая модель
2- Загрузка модели
3- DOS
4- Выход
Подменю п.2: 1- Ввод моделей
2- Ввод названий ограничений и переменных
Подменю п.4: 1- Исходные данные
2- Результаты (полная форма)
3- Результаты (сокращенная форма)
|
|
4- Правильность решения
Все программы комплекса имеют встроенную диалоговую подсказку по всем режимам работы. Подсказка всегда соответствует специфике именно той части программы, с которой вы в данный момент работаете. Вызов подсказки - клавиша <F1>.
Рассмотрение простейшего примера решения задач в «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 мах.
Ввод исходной информации
Ввод исходной информации осуществляется,выбрав первый пункт основного меню - «Модели». Для создания новой модели необходимо выбрать первую строку подменю «МОДЕЛИ» «Новая модель». На экране появляется диалоговое окно, в котором запрашивается имя файла, в который будет записываться создаваемая модель. Здесь необходимо ввести имя своего файла (латинскими буквами, до 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> - завершение ввода.
РЕШЕНИЕ ЗАДАЧИ
Для вывода исходной информации необходимо выбрать строку “Исходные данные” подменю “ОТЧЕТЫ”. Как только осуществляется выбор этого режима, на экране появляется сообщение о формировании файла с исходными данными, записанными в табличном виде. После того, как этот файл сформирован, программа вновь очищает экран и предлагает просмотреть модель. Отчет об исходных данных содержится в файле с именем текущей модели и с расширением “ . ISN”.
Для того, чтобы начать решение введенной задачи, нужно выбрать пункт “РЕШЕНИЕ” основного меню. После этого экран очищается, и поочередно появляются (пробегают) сообщения о действиях программного комплекса. Запись результатов решения производится в файл “SOL . TMP”. Если необходимо ввести результаты решения задачи, после решения надо выбрать строку “Вывод результатов (полная форма)” из подменю “ОТЧЕТЫ”. При этом на экране появляются сообщение: “Запись отчета на диск”. Завершив формирование этого файла, программа вновь очищает экран и выдает запрос: “Укажите количество столбов для вывода ( 1 -15 )”. Здесь 4 – это количество столбцов, предлагаемых программой по умолчанию, вместо этой цифры можно ввести ту, которая Вам нужна. Файл результатов решения (полной матрицы) всегда записывается на диск с именем текущей модели и расширением .RES. Первая часть выходной формы этого файла представляет собой полную матрицу решения задачи. В нее входят произведения коэффициентов исходной модели и полученных о ходе решения значений соответствующих переменных. Запись этой части производится листами по 4 -15 столбцов на каждом листе.
Вторая часть формы – это характеристика ограничений. Эта часть представляет собой таблицу, имеющую столько строк, сколько ограничений имеет модель пользователя. Столбцами этой таблицы являются:
1. Столбец номеров ограничений;
2. Столбец знаков ограничений;
3. Столбец свободных членов ограничений;
4. Столбец сумм ограничений (каждый элемент столбца – это сумма произведений коэффициентов исходной модели данной строки и значений соответствующих им переменных, полученных в ходе решения);
5. Столбец отклонений ограничений ( отклонение свободных членов ограничений от сумм ограничений );
6. Столбец двойственных оценок ограничений
В самом начале формы записываются сообщение об исходе решения. Вариантов этого сообщения может быть три:
1. Система ограничений несовместности;
2. Функционал линейно не ограничен;
3. Решение оптимальное.
Анализ результатов решения
На рисунке 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 Полный отчет
Анализ решения задачи, полученного с использованием ППП Simplex:
Для получения max прибыли 1 продукции необходимо изготовить 95 ц, 2 продукции 210 ц, а 3 и 4 продукции не изготовлять. При этом на изготовление 1 продукции необходимо затратить 95 ц 1 типа сырья и 380 ц 3 типа сырья; на изготовление 2 продукции необходимо затратить 210 ц 2 типа сырья и 420 ц 3 типа сырья. Max прибыли при изготовлении 1 продукции составит 855 рублей, 2 продукции – 1260 рублей. 1 тип сырья используется не полностью, а 85 ц, 2 и 3 тип сырья используются в процессе изготовления полностью. Если использование 1 типа сырья увеличить на 1 ц, то прибыль не увеличится; если использование 2 типа сырья увеличить на 1 ц, то прибыль увеличится на 1,5 рубля; если использование 3 типа сырья увеличить на 1 ц, то прибыль в стоимостном выражении увеличится на 2,25 рублей. Max прибыли составит 2115 рублей.
Дата добавления: 2018-04-04; просмотров: 485; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!