Файл: Лабораторной.docx

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 26.10.2023

Просмотров: 202

Скачиваний: 3

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Лабораторнаяработа№1Общий вид задач нелинейного программирования. Графический метод решения задач нелинейного программирования. Метод множителей Лагранжа.

    1. Цель работы
Цельюлабораторнойработыявляетсяприобретениестудентамипрактическихнавыковрешениязадачлинейногопрограммированияграфическим методом и использования инструмента Поиск решения средыExcelдлянахожденияоптимальногодопустимогорешения.

    1. Формулировка задачи линейного программирования
Рассмотрим пример с двумя переменными. Компания «Русские краски»производит краску для внутренних и наружных работ из сырья двух типов:М1и М2 (табл.1.1).Таблица1.1–ОсновныеданныедлязадачиОтделмаркетингакомпанииограничилежедневноепроизводствокраски для внутренних работ до 2 тонн, а также поставил условие, чтобыежедневное производство краски для внутренних работ не превышало болеечемнатоннуаналогичныйпоказательпроизводствакраскидлявнешнихработ. Компания хочет определить оптимальное соотношение между видамивыпускаемойпродукциидлямаксимизацииобщегоежедневногодохода.

    1. Математическая модель задачи линейного программирования
Задачалинейногопрограммирования,какилюбаязадачаисследованияопераций,включаеттриосновных элемента.

      1. Переменные, которые следует определить;

      2. Целевая функция, подлежащая оптимизации;

      3. Ограничения, которым должны удовлетворять переменные.
Внашемпримере
необходимоопределитьежедневныеобъемыпроизводствакраскидлявнутреннихинаружныхработ.Обозначимэтиобъемыкакпеременныемодели:x1–ежедневныйобъемпроизводства краскидлянаружных работ;x2–ежедневныйобъем производства краскидля внутренних работ.Используяэтипеременные,далеестроимцелевуюфункциюZ ,каксуммарныйежедневныйдоход,которыйдолжен возрастать.Z5x14x2.Ограничениянасырьеможнозаписатьследующимобразом.

Используемыйобъем



Максимальновозможный



сырьядляпроизводства   ежедневный

 .

расходсырья





обоихвидовкраски
Из таблицы с данными получим используемые объемы в тоннах:

для сырья для сырья

M1  6x1  4x2 ;

M2  1x1  2x2 .

Поскольку ежедневный расход сырья М1 и М2 ограничен соответственно 24 и 6 тоннами, получаем следующие ограничения.



6x1  4x2  24,

1x1  2x2  6.

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

краски для наружных работ более чем на одну тонну, т.е.

x2x1  1. Второе


ограничение максимального ежедневного объема производства краски для

внутренних работ двумя тоннами запишем, как

x2  2 . Учтем условие

неотрицательности переменных:

x1  0, x2  0 .
Окончательнозадачабудетзаписанаследующимобразом:Z5x14x2max,6x14x224,x12x26,  1xx  1, 2 x 2 2, x1 0, x2 0.

    1. Графический способ решения задачи линейного программирования
Графическийспособрешениязадачилинейногопрограммированиясостоитиздвух этапов.

      1. Построение пространства допустимых решений, удовлетворяющих всем ограничениям модели.

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

значения переменной

x1, а на вертикальной –

x2 (рис. 1.1). Условия

неотрицательности переменных:

x1  0, x2  0

показывают, что пространство

допустимых решений будет лежать в первом квадранте (т.е. выше оси

x1 и

правее оси

x2 ).


Учтем оставшиеся ограничения, заменив неравенства на равенства и

получив уравнения прямых. Например, неравенство

6x1  4x2  24

заменяется уравнением прямой

6x1  4x2  24 . Найдем две различные точки,

лежащие на этой прямой. При

x1  0, x2  6 . Аналогично для

x2  0, x1  4 .


Проведем искомую прямую через найденные точки (линия 1 на рис. 1.1).

Теперь рассмотрим, как графически интерпретируются неравенства. Точки плоскости, расположенные по одну сторону прямой, удовлетворяют неравенству (допустимое полупространство), а точки, лежащие по другую
сторону,–нет."Тестовой"точкой,можетслужитьточка0,0.Например,эта

точка удовлетворяет первому неравенству

6x1  4x2  24 . Это означает, что

точки полупространства, содержащего начальную точку 0, 0, удовлетворяют этому неравенству. На рис. 1.1 допустимые полупространства показаны стрелочками.



Рисунок 1.1 – Пространство допустимых решений модели

Если точка 0, 0

не удовлетворяет неравенству, допустимым


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

Этап 2. Поиск оптимального решения.

Точки пространства допустимых решений, показанного на рис. 1.1, удовлетворяют одновременно всем ограничениям. Это пространство ограничено отрезками прямых, которые соединяются в угловых точках А, В, С, D, Е и F. Любая точка, расположенная внутри или на границе области, ограниченной ломаной АВСDЕF, является допустимым решением, т.е. удовлетворяет всем ограничениям. Поскольку пространство допустимых
решенийсодержитбесконечноечислоточек,необходиманекаяпроцедурапоискаоптимальногорешения.Рисунок1.2–ОптимальноезначениемоделиДлятогочтобынайтиоптимальноерешение,необходимоопределить

направление возрастания целевой функции

Z 5x1  4x2 . Мы можем


приравнять Zк нескольким возрастающим значениям, например 10 и 15.

Получаем уравнения прямых

5x1  4x2  10 и

5x1  4x2  15 . На рис. 1.2 эти


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

Оптимальное решение соответствует точке С. Ее координаты

Смотрите также файлы