Исследование операций и методы оптимизации

Дисциплина Исследование операций

Заказчик	station33 ☆ 0 ✍ 1 ♥ 0
Вид работы	Контрольная
ВУЗ	ВлГУ
Срок	07.11.2015
Преподаватель	Ремезова
Вариант	18
Бюджет	1300 ₽

1.	ПОСТАНОВКА, ФОРМАЛИЗАЦИЯ И КЛАССИФИКАЦИЯ ЗАДАЧ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ ЭКОНОМИЧЕСКИМИ СИСТЕМАМИ
Требуется формализовать приведенные ниже задачи и определить их тип.
1.	Найти размеры прямоугольника, имеющего заданный периметр и максимально возможную площадь.
2.	Из всех треугольников данного периметра p найти тот, который имеет наибольшую площадь.
3.	Из проволоки заданной длины l необходимо изготовить равносторонний треугольник и квадрат. Требуется найти размеры этих фигур так, чтобы суммарная площадь их была максимальна.
4.	Малое предприятие изготавливает два вида красок: для внутренних (K1) и наружных (K2) работ. Продукция обоих видов поступает в оптовую продажу. Для производства этих красок используются два исходных продукта (П1 и П2), их максимально возможные суточные запасы составляют 6 и 8 т. соответственно. Расходы продуктов П1 и П2 на изготовление 1 т соответствующих красок известны. Они приведены в табл. 1.2. Изучение рынка сбыта показало, что суточный спрос на краску K1 никогда не превышает спрос на краску K2 более чем на 1 т. Кроме того, спрос на  никогда не превышает 2 т в сутки. Оптовые цены одной тонны красок равны: 3 тыс. у.е. для K1 и 2 тыс. у.е. для K2. Какое количество краски каждого вида должно производить предприятие, чтобы доход от реализации обеих красок был наибольшим? (Решение аналогично примеру 3 из п. 1.1, оно приведено в [32]).

5.	Производственная мощность цеха сборки некоторого изделия составляет 120 шт. типа P1 и 360 шт. типа P2 в смену. Технический контроль может пропустить в сутки не более 200 изделий того и другого типа. Доход от реализации изделий P2 в 4 раза выше, чем от реализации P1. Определить план выпуска изделий, при котором будет обеспечена наибольшая прибыль.
6.	 Предприятие выпускает две модели электронных блоков Б1 и Б2, причем каждая модель производится на отдельной технологической линии. Первая линия может выпускать 60 изделий в сутки, вторая – 75. В производстве обеих моделей используется однотипные узлы, суточный запас которых ограничен: он не может превышать 1000 штук. Причем на один блок 1-й модели расходуется 10 узлов указанного типа, а для 2-й модели – 8 узлов. Прибыль от реализации одного блока 1-й модели равна 30 у.е., а второй – 20 у.е. Определить оптимальные суточные объемы производства.
7.	Фирма имеет возможность рекламировать свою продукцию через радио- и телевизионную сети. Для этих целей из бюджета фирмы выделяется 1000 у.е. в месяц. Каждая минута радиорекламы стоит 5 у.е., а телерекламы – 100 у.е. Опыт показывает, что объем сбыта, который обеспечивает каждая минута телерекламы, в 25 раз больше сбыта, обеспечиваемого одной минутой радиорекламы. Определить оптимальное распределение средств между радио- и телерекламой.
8.	На предприятии изготавливаются изделия двух видов. Процесс изготовления каждого из них осуществляется последовательно в трех цехах. Время обработки и прибыль от продажи одного изделия каждого вида приведены в табл. 1.3. рабочее время составляет 8 ч. в сутки. Найти оптимальные объемы производства изделий каждого вида.

9.	Формализовать задачу об оптимальном составе смеси. В ней требуется определить такие концентрации веществ в смеси, чтобы стоимость смеси была минимальна, а показатели, оценивающие ее свойства (плотность, прочность, теплоемкость и т.п.), были не меньше заданных значений. Примером такой задачи может служить задача об оптимальной диете (рационе). При откормке животных каждое из них ежедневно должно получить не менее 60 ед. питательного вещества А, не менее 50 ед. вещества В и не менее 12 ед. вещества С. Использоваться могут три вида корма. Содержание питательных веществ в каждом из них задается в табл. 1.4.
Составить дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах, если цена кормов 1-го, 2-го и 3-го видов составляет соответственно 9, 12 и 10 у.е..
10.	Для производства чугунного литья используется n различных исходных шихтовых материалов (чугун различных марок, стальной лом, феррофосфор и др.). Химический состав чугунного литья определяется содержанием в нем химических элементов (кремния, марганца, фосфора и др.). Готовый чугун должен иметь строго определенный химический состав, который задается величинами Hj, представляющими собой доли (в %) j-го химического элемента в готовом продукте. При этом известны величины: hij - содержание (%) j-го химического элемента в i-м исходном шихтовом материале; ci - цена единицы каждого i-го шихтового материала. Определить состав шихты, обеспечивающей получение литья заданного качества при минимальной общей стоимости используемых шихтовых материалов.
11.	Имеются заготовки в виде листов материала определенного размера. Из них нужно накроить детали четырех видов: А – 6 шт., Б - 15 шт., В – 25 шт., Г – 10 шт. Известны три способа раскроя заготовки. Количество деталей каждого вида, получаемых при этих способах раскроя, приведено в табл. 1.5.
Найти оптимальный план раскроя заготовки, т.е. количество заготовок, при котором должно быть получено заданное количество деталей  каждого вида из минимального количества заготовок.
12.	Имеется n = 2 предприятий A1 и A2, в которых производится однородная продукция. Количество ежедневно производимой продукции в каждом из них задано: a1 = 120 и a2 = 90. Эту продукцию нужно доставить в  m = 4 пунктов  потребления: B1, B2, B3 и B4. Их ежедневные объемы потребления заданы: в1=40, в2=20, в3=80, в4=70. Требуется найти оптимальный план перевозок, определяющий количество продукции, перевозимой из пункта Ai в пункт Bj (i = 1,2;   j =  1,..., 4). Этот план должен обеспечивать минимальные общие затраты  на перевозки. При этом стоимость cij перевозки единицы продукции из пункта Ai в пункт Bj задается табл. 1.6.
13.	Задача  о  назначениях  (о  распределении работ). В цехе имеется 
n= 2 участков A1 и A2 по контролю и настройке производимой электронной аппаратуры, имеющей  m= 4 разновидностей: B1,..,B4. Известно, что оборудование участков и квалификация работающих там специалистов таковы, что на участке Ai на наладку одного изделия вида Bj требуется время Cij (ч.) (табл. 1.7).
Поступило задание: провести настройку 7 изделий вида B1, 10 изд. – B2, 14 изд. – B3 и 9 изд. – B4. Как распределить эти изделия по участкам, чтобы общие затраты времени на их настройку были минимальны?

2.	РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Найти графическим методом решение следующих задач ЛП.
Преобразовать следующие задачи ЛП к канонической форме и решить их симплекс-методом.

3.	ТРАНСПОРТНАЯ ЗАДАЧАЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Дана классическая транспортная задача с тремя ПО Ai и четырьмя ПН Bj. Информация о запасах перевозимого груза в ПО, заявках на него в ПН и удельных стоимостях перевозок представлена в приведенных ниже транспортных таблицах. Для соответствующего варианта найти оптимальный план перевозок. 

4.	ЗАДАЧИ ОПТИМИЗАЦИИ, ПРЕДСТАВЛЯЕМЫЕ НА ГРАФАХ
4.8.1 Задача о кратчайших путях в графе
Неориентированный граф с десятью вершинами x1…x10 задан верхней треугольной «половиной» матрицы весов. При этом отсутствие элемента c(I,j) в матрице указывает на отсутствие в графе ребра, связывающего вершины xi и xj.
Необходимо найти кратчайший путь из истока в каждую из остальных вершин графа. 

4.8.2 Задача о графе минимальной длины

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

4.8.3 Задача о критическом пути в графе
Дан ориентированный граф, в котором отсутствуют контуры и каждой дуге которого приписан вес c(i,j)>0. Структура графа определяется следующим условием: он имеет дугу, связывающую вершину xi с  вершиной xj, если в исходных условиях задан вес c(i,j).
Необходимо найти путь от заданной начальной вершины (истока) к заданной конечной вершине (стоку), имеющий наибольшую длину, равную сумме весов дуг, входящих в этот путь. 

4.8.4задача об оптимальном распределении заданного потока в транспортной сети
Транспортная сеть задана матрицей пропускных способностей c(i,j).
Необходимо найти распределение заданного потока P0<Pmax  по этой сети, при котором общая стоимость прохождения потока через сеть была бы минимальной. Величину потока P0, подлежащую распределению по сети, принять равной Pmax-dP, dP - величина, задаваемая преподавателем для каждой учебной группы.
Ниже приведены матрицы удельных стоимостей , которые следует взять для расчетов по соответствующему варианту.