Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Топ:
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Дисциплины:
 2018-01-05 |
 306 |
из
5.00
|
Заказать работу |
|
|
|
|
Пусть задана стандартная математическая модель задачи с двумя неизвестными:
(1.7)
(1.8)
Нахождение решения этой модели на основе ее геометрической интерпретации включает следующие этапы.
1. В плоскости х 1 0 х 2 строят прямые, уравнения которых получаются в результате замены в ограничениях (1.7) модели знаков неравенств на знаки точных равенств.
2. Находят полуплоскости, определенные каждым неравенством системы.
3. Находят выпуклый многоугольник решений всей системы (1.7).
4. Строят нормальный вектор целевой функции 
, причем, начало вектора совмещают с началом координат и строят прямую 
.
5. Передвигают эту прямую в направлении вектора 
, в результате либо находят вершину или отрезок, в которой целевая функция принимает наибольшее значение, либо устанавливают неограниченность сверху этой функции на множестве допустимых решений.
6. Если функция ограничена, то определяют 
и вычисляют значение функции в этой точке 
.
При геометрической интерпретации задач ЛП могут встретиться случаи, изображенные на рис. 2.1. - 2.4.
Рис. 2.1. задача ЛП имеет единственное решение 
.
Рис. 2.2. задача ЛП имеет бесчисленное множество решений, т.к. целевая функция достигает максимума на отрезке [ М; N ].
Рис. 2.3. задача ЛП не имеет решения, т.к. функция неограниченна сверху.
Рис. 2.4. задача ЛП не имеет решения, т.к. система (1.7) несовместна.
 |
Рис. 2.1. Рис. 2.2.
Рис. 2.3. Рис. 2.4.
Пример. Для производства двух видов изделий А и В предприятие использует три вида сырья S 1, S 2, S 3. Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в таблице 2.1.
Прибыль от реализации одного изделия каждого вида равна с 1и с 2 , а общее количество сырья вида 
равно 
, 
. Считая, что изделия А и В могут производиться в любых соотношениях (сбыт обеспечен), требуется составить такой план их выпуска, при котором прибыль предприятия от реализации всех изделий будет максимальной.
|
|
| Сырье | А | В | Запасы |
| S 1 | а 11 = 12 | а 12 = 4 | в 1 = 300 |
| S 2 | а 21 = 4 | а 22 = 4 | в 2 = 120 |
| S 3 | а 31 = 3 | а 32 = 12 | в 3 = 252 |
| Прибыль | с 1 = 30 | с 2 = 40 |
Решение. Обозначим через х 1 и х 2количествоизделий первого и второго вида в плане предприятия. Поскольку производство продукции ограничено только сырьем каждого типа Si, то получим условия:
12 х 1 + 4 х 2 £ 300,
4 х 1 + 4 х 2 £ 120, (1)
3 х 1 + 12 х 2 £ 252,
Переменные х 1 и х 2 не могут быть отрицательными по смыслу задачи.
Вычислим прибыль от реализации продукции и получим:
 |
Итак, мы получили стандартную модель с двумя переменными.
Решим задачу линейного программирования геометрически, придерживаясь плана, приведенного ранее.
1. Строим прямые l 1, l 2, l 3:
l 1: 12 х 1 + 4 х 2 = 300, по двум точкам А 1 (25, 0) и В 1 (0; 75);
l 2 : 4 х 1 + 4 х 2 = 120, по двум точкам А 2 (30; 0)и В 2 (0, 30);
l 3 : 3 х 1 + 12 х 2 = 252, по двум точкам А 3 (84, 0)и В 3 (0, 21).
Обратимся к неравенствам (1). Отметим те полуплоскости, которые им удовлетворяют. Учтем на чертеже и неотрицательность переменных х 1 и х 2,и получим многоугольник ОВ 3 ЕСА 1 решений данной системы неравенств (см. рис. 2.5).
2. Построим нормальный вектор 
и прямую (l): 30 х 1 + 40 х 2 = 0.
3. Передвигая прямую в направлении вектора 
, получим, что в точке Е (12, 18) целевая функция будет иметь наибольшее значение. Координаты этой точки находим как координаты точки пересечения прямых 
и 
, решая систему уравнений:
4. Запишем окончательный ответ:
 |
Наибольшая прибыль будет равна 1080 (у.е).
|
|
|
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!