 ПОЗНАВАТЕЛЬНОЕ Сила воли ведет к действию, а позитивные действия формируют позитивное отношение Как определить диапазон голоса - ваш вокал Игровые автоматы с быстрым выводом Как самому избавиться от обидчивости Противоречивые взгляды на качества, присущие мужчинам Вкуснейший "Салат из свеклы с чесноком" Натюрморт и его изобразительные возможности Применение, как принимать мумие? Мумие для волос, лица, при переломах, при кровотечении и т.д. Как научиться брать на себя ответственность Зачем нужны границы в отношениях с детьми? Световозвращающие элементы на детской одежде Как победить свой возраст? Восемь уникальных способов, которые помогут достичь долголетия Классификация ожирения по ИМТ (ВОЗ) Глава 3. Завет мужчины с женщиной
Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.
| Практическое занятие 5. Моделирование задач линейного программирования.
1. Цель и порядок выполнения работы Цель работы - овладеть приемами моделирования задач линейного программирования (ЛП) и научиться работать с программой решения задач ЛП. Порядок выполнения работы: · ознакомиться с описанием работы; · выполнить работу по указанному варианту; · оформить отчет. 2. Общие сведения 2.1.Формулировка общей задачи и суть симплексного метода. Задача ЛП в общем виде формулируется следующим образом. Найти экстремум (максимум или минимум функции),
при ограничениях
Xj=0, j=1,n ,
где Xj - искомые переменные; Cj - нормы показателя эффективности; Aij - коэффициенты затрат-выпуска; Bi - обьемы ресурсов или производства; j - номер переменной; i - номер ресурса или продукции Решение задач производится симплексным методом, суть которого состоит в том, что: а) находят опорное, т.е. базисное решение; б) исследуют его на оптимальность; в) в случае, если решение не оптимально, находят улучшенное решение и т.д. пока полученное решение не удовлетворит условиям оптимальности. 3. Подготовка задачи ЛП к решению в приложении EXCEL. Для того, чтобы решить задачу ЛП средствами EXCEL, ее модель должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений. После этого создается форма в приложении EXCEL и с помощью средства EXCEL ²поиск решения² с учетом ограничений находят решение задачи. Например, требуется определить площади посевов двух зерновых культур А и В, при которых максимизируется прибыль от реализации урожая. При этом введены ограничения на производство: 1) суммарная площадь посевов культур А и В не должна превышать 500 га.; 2) расход трудовых ресурсов не должен превысить 36000 чел-час; Затраты труда на 1 га культуры А составляют 60 чел-час, а культуры В - 80 чел-час. Прибыль, получаемая с одного га площади культуры А, составляет 100 тыс.руб, а культуры В - 120 тыс.руб. Модель этой задачи в соответствии с указанными двумя ограничениями на производство и критерием оптимизации (максимум прибыли) запишется следующим образом: X1+X2 <= 500 (ограничение по площади); 60X1+80X2 <= 36000 (ограничение по труду); Z = 100X1+ 120X2 --> max (функция прибыли). где X1 - искомая площадь посевов культуры А; X2 -искомая площадь посевов культуры В. Для приведения неравенства к уравнению, необходимо в него ввести дополнительную переменную со знаком "+" , если неравенство типа "<=", и со знаком "-", если ">=". Таким образом , в первое ограничение вводим дополнительную переменную X3 , обозначающую недоиспользованную площадь, во второе - X4 , обозначающую недоиспользованный фонд труда. При этом, во всех уравнениях системы (включая целевую функцию - функцию прибыли) должны присутствовать все переменные системы. Это достигается тем, что в уравнение, где данная переменная отсутствует, она вводится с нулевым коэффициентом. Учитывая вышеизложенное, получим модель задачи в канонической форме: 1 X1 + 1 X2 + 1 X3 + 0 X4 <= 500 60X1 + 80X2 + 0 X3 + 1 X4 <=36000
Z = 100 X1+120 X2 + 0 X3 + 0 X4
4. Анализ полученного решения После получения решения на ЭВМ , необходимо дать его описание и анализ. Например, для вышеполученного решения, учитывая, что оно является базисным (т.е. небазисные переменные всегда равны нулю), можно заключить следующее: Площадь посевов культуры А составляет 200 га (Х1 =200), а культуры В - 300 га (Х2 = 300). При этом достигается максимально возможная прибыль Z = 56000 тыс.руб. Недоиспользованных ресурсов нет, т.к. Х3 = 0, Х4 = 0.
5. Варианты заданий
ВАРИАНТ 1 Есть три вида станков: А1,А2,А3. На этих станках последовательно обрабатываются детали четырех видов:В1,В2,В3,В4. Известно сколько часов каждая деталь изготавливается на каждом станке, сколько может проработать каждый станок и какая прибыль может быть получена при продаже одной детали каждого типа. Данные сведены в табл. 1. Требуется найти оптимальный план работы станков, т.е. установить, сколько деталей и каких видов надо выпустить, чтобы получить максимальную прибыль.
ТАБЛИЦА 1
Повторите решение, уменьшив фонд времени станка А3 до 24 часов. Сравните с 1-м решением и объясните полученное различие.
ВАРИАНТ 2 Задача та же, что в варианте 1, но с дополнительными условиями: а)изделий В1 должно быть не менее изделий В2; б)изделий В3 должно быть не менее, чем в два раза больше изделий В2.
ВАРИАНТ 3
Составить питательную смесь из трех видов продуктов В1, В2, В3, причем в смеси должно быть не менее заданных величин содержания питательных веществ А1,А2,А3. Задана цена за единицу каждого вида продуктов. Данные сведены в табл.3. Требуется найти оптимальный состав питательной смеси, т.е. в каком количестве должны входить в смесь заданные продукты, чтобы стоимость смеси была минимальной.
ТАБЛИЦА 3
Повторите решение, увеличив цену за ед. продукта В3 до 6 руб. Сравните с первым решением и объясните полученное различие.
ВАРИАНТ 4
Составить оптимальную питательную смесь из продуктов В1, В2, В3, в которую должны входить вещества А1, А2, А3, А4 в заданных ограничениях, и миниминизирующую их стоимость.
Данные приведены в таблице 4
ТАБЛИЦА 4
Повторите решение, заменив в табл. 4 нули на цифру 5. Сравните с первым решением и объясните полученное различие.
ВАРИАНТ 5
На станции формируются пассажирские и скорые поезда. Они отличаются по количеству вагонов разных типов, в которых разное количество мест. Количество вагонов разного типа ограничено. Требуется найти такое количество пассажирских и скорых поездов, чтобы общее число мест в них было максимальным.
Данные сведены в табл.5.
ТАБЛИЦА 5
Повторите решение, увеличив количество мягких вагонов на станции до 40 шт. Сравните полученный результат с предыдущим и объясните различие. ВАРИАНТ 6
Составить план жилищного строительства. Задана потребность в квартирах по типам. Предназначенные к сооружению типы домов различаются по стоимости и по количеству квартир разного типа. Требуется определить, сколько домов и каких типов надо возвести, чтобы удовлетворить заданную потребность в квартирах с минимальными затратами.
Данные в табл.6. ТАБЛИЦА 6
Повторите решение, увеличив потребность в квартирах А4 в 2 раза. Сравните с предыдущим решением и объясните отличие.
ВАРИАНТ 7 Фирма производит два продукта А и В. Каждый продукт должен быть обработан каждой из машин I,II,III. Время обработки, фонд времени машин в неделю и прибыль от изделий А и В приведены в табл.7. Надо определить недельные нормы выпуска изделий А и В, максимизирующие прибыль.
ТАБЛИЦА 7
Повторите решение, увеличив норму прибыли продукта В до 5 тыс.р. Сравните полученное решение с предыдущим и объясните различие.
ВАРИАНТ 8 Предприятию требуется уголь с содержание фосфора не более 0,03 % и с долей зольных примесей не более 3,25 %.Можно приобрести три сорта угля А,В,С с показателями, сведенными в табл.8. Как их смешивать, чтобы получить минимальную цену и удовлетворить ограничениям на содержание примесей. ТАБЛИЦА 8
Повторите решение, увеличив допустимое содержание фосфора в смеси до 0,06 %. Сравните с предыдущим решением и объясните результат сравнения. ВАРИАНТ 9 Требуется составить питательную смесь из трех продуктов А1,А2,А3 с содержанием вещества В1 не менее 10% и вещества В2 не более 0,5% .Содержание этих веществ в продуктах и их цена указаны в табл.9. Как составить смесь, чтобы получить минимальную цену и удовлетворить ограничениям на содержание веществ? ТАБЛИЦА 9
Повторите решение, увеличив содержание вещества В1 в продукте А2 до 12%. Сравните с предыдущим решением и объясните различие.
6.Контрольные вопросы
6.1. Сформулируйте общую задачу ЛП. 6.2. Что такое основные, дополнительные, базисные переменные ? 6.3. Что такое базисное решение ? 6.4. В чем суть алгоритма симплексного метода ? 6.5. Как привести систему ограничений к каноническому виду ? 6.6. В чем состоит анализ решения задачи ? |
