Математические методы оптимизации

Размещено на /

Задание 1. Графическое решение задачи распределения ресурсов


Записать стандартную и каноническую формы.

Найти все базисные и допустимые базисные решения. Определить оптимальное базисное решение.

Найти графически оптимальное базисное решение.

Фирма выпускает два вида изделий А и В. Каждое изделие проходит обработку на двух технологических линиях.

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



Изделия А Изделия В Общее время работы линии
Линия 1 60 32 1920
Линия 2 36 60 2160
Цена одного изделия 30 25

РЕШЕНИЕ

Запишем стандартную и каноническую формы

Обозначим:

Математические методы оптимизацииплан выпуска изделия А;

Математические методы оптимизацииплан выпуска изделия В.

Тогда затраты линии 1 и линии 2, необходимые для производства плана Математические методы оптимизации будут равны соответственно:


Математические методы оптимизации


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


Математические методы оптимизации


Целевой функцией служит выручка от реализации допустимого плана Математические методы оптимизации Математические методы оптимизации при ограничениях


Математические методы оптимизации (1.1)


Для канонической формы эти ограничения нужно преобразовать в равенства. Для этого введём две дополнительные переменные

Математические методы оптимизацииостаток от производства на линии 1 (остаток времени обработки)

Математические методы оптимизацииостаток от производства на линии 2 (остаток времени обработки).

Тогда получим каноническую форму задачи:

-найти переменные Математические методы оптимизации, которые дают максимум целевой функции


Математические методы оптимизации при ограничениях

Математические методы оптимизации (1.2)


Найдём все базисные решения.

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

1) Пусть Математические методы оптимизациисвободные переменные. Подставляя значения Математические методы оптимизации (1.2), получаем систему уравнений


Математические методы оптимизации


Следовательно, базисное решение имеет вид


Математические методы оптимизации.


Базисное решение означает, что изделия А и изделия В не производятся. Это базисное решение является допустимым. Выручка от реализации этого плана составит


Математические методы оптимизации.


2) Пусть Математические методы оптимизациисвободные переменные. Подставляя значения Математические методы оптимизации (1.2) получаем систему


Математические методы оптимизации


Следовательно, базисное решение имеет вид


Математические методы оптимизации.


Это базисное решение означает, что изделие А не производится, изделие В производится в количестве 60 ед., время изготовления продукции на линии 1 используется полностью, для производства на линии 2 не хватает 1440 минут работы. Это базисное решение не является допустимым.

3) Пусть Математические методы оптимизациисвободные переменные. Подставляя значения Математические методы оптимизации в (1.2) получаем систему


Математические методы оптимизации


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


Математические методы оптимизации.


Это базисное решение означает, что изделие А не производится, изделие В производится в количестве 36 единиц, время изготовления продукции линии 1 используется не полностью и его остаток составляет 768 минут, а на линии 2 используется полностью. Это базисное решение является допустимым. Выручка от реализации этого плана составит Математические методы оптимизации ден.ед.

4) Пусть Математические методы оптимизациисвободные переменные. Подставляя значения Математические методы оптимизации в (1.2) получаем систему


Математические методы оптимизации

для базисных переменных Математические методы оптимизации. Следовательно, базисное решение имеет вид Математические методы оптимизации. Базисное решение означает, что изделия А производится в количестве 32 ед., изделие В не производится, время изготовления продукции линии 1 используется полностью, а время изготовления линии 2 не полностью используется, его остаток составляет 1008 минут. Это базисное решение является допустимым. Выручка от реализации этого плана составит


Математические методы оптимизации ден. ед.


5) Пусть Математические методы оптимизациисвободные переменные. Подставляя значения Математические методы оптимизации в (1.2) получаем систему


Математические методы оптимизации


для базисных переменных Математические методы оптимизации. Следовательно, базисное решение имеет вид Математические методы оптимизации. Это базисное решение означает, что изделия А производится 60 ед., изделие В не производится, не хватает времени обработки 1680 минут для первой линии, а время обработки второй линии используется полностью. Это базисное решение не является допустимым.

6) Пусть Математические методы оптимизациисвободные переменные. Тогда базисные переменные Математические методы оптимизации и Математические методы оптимизации найдём из системы уравнений


Математические методы оптимизации

Отсюда следует, что базисное решение имеет вид Математические методы оптимизации. Это решение означает, что изделия А производятся в количестве Математические методы оптимизацииед., изделия В производятся в количестве Математические методы оптимизации, время обработки на каждой из линий используется полностью. Это базисное решение является допустимым. Выручка от реализации составит Математические методы оптимизации ден.ед.

Определим оптимальное базисное решение.

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

В таблице 1.1 приведены все допустимые базисные решения и соответствующие им значения выручки Математические методы оптимизации.

двойственный задача равновесный спрос полезность товар

Таблица 1.1

Базисные переменные Небазисные переменные

Математические методы оптимизации

1

Математические методы оптимизации

Математические методы оптимизации

Математические методы оптимизации

Математические методы оптимизации

Математические методы оптимизации

2

Математические методы оптимизации

Математические методы оптимизации

Математические методы оптимизации

Математические методы оптимизации

Математические методы оптимизации

3

Математические методы оптимизации

Математические методы оптимизации

Математические методы оптимизации

Математические методы оптимизации

Математические методы оптимизации

4

Математические методы оптимизации

Математические методы оптимизации

Математические методы оптимизации

Математические методы оптимизации

Математические методы оптимизации


Максимальное значение выручки достигается на четвёртом базисном решении в этой таблице

Математические методы оптимизации


Следовательно, изделие А производится в количестве Математические методы оптимизации ед., изделие В производится в количестве Математические методы оптимизации ед., время обработки на каждой из линий используется полностью (Математические методы оптимизации).

Графическое решение задачи

Рассмотрим задачу в стандартной форме: найти переменные Математические методы оптимизации, которые обеспечивают максимальное значение функции Математические методы оптимизации


Математические методы оптимизации


при ограничениях


Математические методы оптимизации


На горизонтальной оси прямоугольной системы координат будем откладывать план выпуска продукции Математические методы оптимизации, а на вертикальной – план выпуска второй продукции Математические методы оптимизации.

Рассмотрим первое ограничение Математические методы оптимизации. Множество точек, удовлетворяющих равенству Математические методы оптимизации, образует прямую на плоскости. Построим эту прямую по её точкам пересечения с осями координат. Для определения координат точки А пересечения с осью Математические методы оптимизации в уравнение подставим Математические методы оптимизации. Из него следует Математические методы оптимизации, т.е Математические методы оптимизации. Для определения координат точки В пересечения с осью Математические методы оптимизации в уравнение подставим Математические методы оптимизации. Из него следует Математические методы оптимизации, т.е. Математические методы оптимизации. Неравенству Математические методы оптимизации удовлетворяют все точки одной из полуплоскостей, которые образовала построенная прямая. Для её определения достаточно проверить справедливость неравенства для одной точки. Для начала координат Математические методы оптимизации неравенство выполняется. Следовательно, все точки полуплоскости, содержащей начало координат, будут графическим изображением этого неравенства. Аналогично построим прямую Математические методы оптимизации по её точкам пересечения с осями координат: Математические методы оптимизации. Все точки полуплоскости, содержащей начало координат Математические методы оптимизации будут графическим изображением неравенства Математические методы оптимизации. Учитывая ограничения на знак Математические методы оптимизации, множество точек четырёхугольника Математические методы оптимизации является множеством всех допустимых решений. Все угловые точки (крайние точки) четырёхугольника Математические методы оптимизации соответствуют допустимым базисным решениям:

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


Математические методы оптимизации, Математические методы оптимизации, Математические методы оптимизации;


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


Математические методы оптимизации, Математические методы оптимизации, Математические методы оптимизации, Математические методы оптимизации;


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


Математические методы оптимизации, Математические методы оптимизации, Математические методы оптимизации, Математические методы оптимизации;


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

Математические методы оптимизации


Теперь графически найдём точку четырёхугольника Математические методы оптимизации, которая определит оптимальное решение.

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


Математические методы оптимизации


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


Математические методы оптимизации


является оптимальным решением. Максимальная выручка будет равна Математические методы оптимизации. Уравнение Математические методы оптимизации определяет уравнение максимальной выручки (верхняя розовая линия).


Задание 2. Двойственная задача


Записать двойственную задачу и дать её экономический смысл.

Найти оптимальное решение двойственной задачи.

Определить целесообразность производства продукции С, для которой на изготовление единицы продукции требуется 60 минут и 50 минут времени изготовления на первой и второй линии соответственно. Рыночная цена составляет 120 ден. ед. за единицу продукции.

РЕШЕНИЕ

Запишем двойственную задачу и дадим её экономический смысл.

Правило построения двойственной задачи состоит в следующем. Каждому равенству прямой задачи соответствует двойственная переменная


Математические методы оптимизации


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

Для определения целевой функции Математические методы оптимизации двойственной задачи двойственные переменные Математические методы оптимизации и Математические методы оптимизации умножаются на правые части равенств и складываются:


Математические методы оптимизации.


Каждой

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: