Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина»

Решение задачи оптимизации

Методические указания к курсовой работе

по курсу «Информатика»

для студентов дневной формы обучения специальностей

Екатеринбург 2014



Содержание

• Введение
• 1. Одноиндексная модель
• 1.1 Математическая модель задачи
• 1.2 Планирование производства
• 1.2.1 Постановка задачи об оптимальном производстве тортов
• 1.2.2 Математическая формулировка задачи
• 1.2.3 Решение в табличном процессоре Excel
• 1.2 Задача о составлении сплава
• 1.3 Задача составления штатного расписания
• 2. Модель двухиндексной задачи
• 2.1 Построение модели транспортной задачи
• 2.1.1 Математическая модель задачи
• 2.1.2 Сбалансированная транспортная задача
• 2.1.3 Несбалансированная транспортная задача
• 2.2 Построение модели задачи с булевыми переменными (задача о назначениях)
• 3. Варианты задач
• 4. Оформление пояснительной записки
• Литература



Введение

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

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

Постановка задачи начинается с формулировки количественного показателя полезности, именуемого целевой функцией. Для достижения оптимального значения целевой функции приходится расходовать ресурсы: сырье, энергию, труд, время, деньги и пр. Но ресурсы всегда ограничены. Поэтому оптимизация деятельности связана с достижением оптимального значения целевой функции при выполнении ограничений на используемые ресурсы.

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

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

1. Что является переменными задачи?

2. Что является критерием оптимальности решения?

3. Какие условия в отношении переменных и ресурсов задачи должны быть выполнены?

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

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

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



1. Одноиндексная модель

1.1 Математическая модель задачи

К одноиндексным задачам линейного программирования относятся планирование производства и штатного расписания, составление смесей или сплавов. Рассмотрим математическую модель задачи.

1. Целевая функция F(X) представляет собой линейную функцию от переменных X = (x₁, x₂, …, x_n):

F(X) = c₁x₁ + c₂x_{2 + …+} c_nx_n > max (min),

2. Ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств:

? (?, =) b₁,

? (?, =) b₂,

…

? (?, =) b_m,

x₁, x₂,…, x_k ? 0 (k ? n).

3. Оптимальное решение - это совокупность чисел X = (x₁, x₂,…, x_n), для которых целевая функция принимает свое максимальное (минимальное) значение.



1.2 Планирование производства

1.2.1 Постановка задачи об оптимальном производстве тортов

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Кондитерская фабрика вырабатывает и продает торты. Для их изготовления фабрика использует сахар, яйца, муку и сметану (все остальные ингредиенты имеются в избытке и поэтому не рассматриваются). Известны расходы каждого ингредиента на производство 1 кг выпечки и максимально возможные запасы продуктов, которыми фабрика располагает на один день (табл. 1). Прибыль от реализации 1 кг торта «Лиза» составляет 5,5 у. е., а от реализации 1 кг торта «Лайза» - 6 у. е.

Кроме того, установлено, что суточный спрос на торт «Лиза» превышает спрос на торт «Лайза», но не более чем на 30 кг в сутки. Требуется составить дневной план выпуска продукции, при котором фабрика получит наибольшую прибыль.

1.2.2 Математическая формулировка задачи

Переменные. Модель строится для определения объема производства тортов. Поэтому переменными задачи являются суточные объемы производства каждого вида торта:

x₁ - суточный объем производства торта «Лиза», кг /сутки;

x₂ - суточный объем производства торта «Лайза», кг/сутки.

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

F(X) = 5,5 x₁ + 6 x₂ (у. е.) > max.

Ограничения. Возможные объемы производства ограничиваются дневными запасами исходных продуктов.

По сахару: 0,3 x₁ + 0,4 x₂ ? 50, кг.

По яйцам: 5 x₁ + 6 x₂ ? 700, шт.

По муке: 0,36 x₁ + 0,36 x₂ ? 50, кг.

По сметане: 0,35 x₁ + 0,4 x₂ ? 50, кг.

Кроме того, объемы производства не могут быть отрицательными - x₁ и x₂ ? 0. И последнее условие, накладываемое на переменные, связано с требованиями рынка: x₁ - x₂ ? 30.

1.2.3 Решение в табличном процессоре Excel

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/



1. Создание таблицы с исходными данными. Каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка в Excel, рис. 1. Для наглядности таблица представлена в формульном отображении.

Переменным задачи x_i соответствуют ячейки B3:C3. После решения задачи Excel поместит в них оптимальные значения. Коэффициентам целевой функции (значения прибыли на одно изделие) соответствуют ячейки B4:C4. Коэффициентам левых частей ограничений соответствуют ячейки B6:C9. Для правых частей ограничений отведен диапазон E6:E10.

2. Ввод зависимостей из математической модели. Для целевой функции отведена ячейка D4. Зависимости для левых частей ограничений (ячейки D6:D10) получены копированием формулы из целевой ячейки.

3. Решение задачи. Дальнейшие действия произведены в окне Поиск решения (рис. 2). Курсор предварительно устанавливается в целевую ячейку, и этот адрес автоматически появляется в поле Установить целевую ячейку. Переключателем установлено направление оптимизации: максимальному значению. В поле Изменяя ячейки вписаны адреса переменных $B$3:$C$3.

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Каждое ограничение введено с помощью кнопки Добавить. Данная кнопка приводит к появлению окна Добавление ограничения, рис. 3. Ограничение состоит из трех компонентов: ссылки на ячейку (диапазон ячеек), оператора сравнения и значения ограничения. В правой части может задаваться ссылка на диапазон, ссылка на ячейку или константное значение.

Окно Поиск решения после ввода всех необходимых данных задачи представлено на рис. 2.

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

4. Анализ результатов поиска решения. Запуск задачи на решение производится из окна Поиск решения путем нажатия кнопки Выполнить. По окончании поиска решения на экране появляется окно Результаты поиска решения с сообщением об успешном решении задачи или о невозможности получения решения, рис. 4.

Полученные результаты можно оформить в виде трех отчетов: Результаты, Устойчивость и Пределы. Каждый отчет сохраняется на отдельном листе текущей книги, а имена отчетов отображаются на ярлычках.

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



Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Отчет по результатам содержит целевую ячейку, список изменяемых ячеек и ограничений. В этом отчете для каждого ограничения выводятся «статус» и «разница». Разница - это разность между значением, выводимым в ячейке ограничения при получении решения, и числом, заданным в правой части формулы ограничения. Статус может принимать три состояния: «связанное» (ограничение, для которого значение разницы равно 0), «не связанное» (ограничение, которое было выполнено с ненулевым значением разницы) и «не выполненное».

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

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Если оптимальное решение не найдено, в окне Результаты поиска решений выводится соответствующее сообщение. Иногда сообщения свидетельствуют о том, что при вводе условий задачи были допущены ошибки, не позволяющие Excel найти оптимальное решение, которое в действительности существует.

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

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

Например, увеличение количества яиц до 725 штук и уменьшение запаса сахара до 46 кг, а запаса муки до 49 кг увеличивает прибыль с 740 у. е. до 766,1 у. е., а все запасы оказываются полностью выбранными.

1.3 Задача о составлении сплава

Постановка задачи. Имеются три сплава. Первый сплав содержит 70 % олова и 30 % свинца, второй - 80 % олова и 20 % цинка, третий - 50 % олова, 10 % свинца и 40 % цинка. Из них необходимо изготовить новый сплав, содержащий 15% свинца. Какое наибольшее и наименьшее процентное содержание олова может быть в этом сплаве?

Математическая формулировка задачи. Обозначим количество первого, второго и третьего сплава, взятое для изготовления нового сплава, через u, v, w соответственно. Поскольку в сплаве должно быть 15 % свинца, то получаем уравнение:

(0,3u + 0,1w)/(u + v + w)=0,15.

Критерием эффективности является количество олова в новом сплаве:

(0,7u+0,8v+0,5w)/(u+v+w).

Уместно перейти к новым переменным, определяющим долю каждого сплава:

х₁ = u/(u + v + w),

х₂ = v/(u + v + w),

х₃ = w/(u + v + w).

Через эти переменные запишем целевую функцию, для которой нужно найти наибольшее и наименьшее значения:

0,7х₁ + 0,8х₂ + 0,5х₃.

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

К новому сплаву предъявляется требование: содержание свинца должно быть равным 15 %. Следовательно, имеем ограничение: 0,3х₁+0,1х₃ = 0,15. Оно дополняется еще одним: х₁ + х₂ + х₃ = 1.

Решение в Excel. Заполним рабочий лист, рис. 5. На целевую ячейку В12 наложим процентный формат.

В окне Поиск решения зададим ячейку с целевой функцией, изменяемые переменные (В6:В8) и ограничения.

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

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

После нажатия кнопки OK вновь появится окно Результаты поиска решения. В нем необходимо установить переключатель Восстановить исходные значения и закрыть его.

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

Варианты расчета можно просмотреть, выполнив команду Сервис > Сценарии. Далее следует выбрать имя сценария и нажать кнопку Вывести. Для просмотра всех сценариев следует выбрать кнопку Отчет. В переоформленном варианте структура сценария представлена в табл. 3.



1.4 Задача составления штатного расписания

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Постановка задачи. В начале мая в хозяйстве фермера имеется 30 постоянных рабочих с оплатой 20 000 р. Они работают на следующих условиях: оплата 20 000 р. при месячной норме времени 200 час.

С мая по октябрь фермер в соответствии с ежемесячными потребностями в объеме работ (табл. 4) нанимает временных рабочих с испытательным сроком один месяц. На время испытательного срока рабочим назначается оплата 5 000 р. при месячной норме времени 150 час. Установлено, что 10 % из них не выдерживают испытательного срока. Выдержавшим испытательный срок устанавливаются те же самые условия оплаты, что и постоянным рабочим.

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

Математическая модель задачи. Переменными задачи являются число вновь принимаемых рабочих каждый месяц x_i (i = 1,..,6). Число работающих в каждом месяце определяется как

y_i = y_i-1 + 0,9x_i, где

y_i - число работающих в текущем месяце (y₀ = 30);

y_i-1 - число работавших в предыдущем месяце.

Ежемесячные расходы фермера на оплату вычисляются по формуле:

q_i =20000 y_i + 5000 x_i, р.

Критерием эффективности являются суммарные затраты, которые должны стремиться к минимуму:

F(X) = > min, р.

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Ограничения. Ежемесячный объем выполняемой работы ограничивается потребностями рабочего времени:

150x_i + 200y_i ? c_i, где c_i - потребности рабочего времени, приведенные в табл. 4.

Кроме того, переменные должны быть целыми и не могут быть отрицательными.

Решение в Excel. Результаты расчета оптимального штата представлены на рис. 6. Из рисунка видно, что в последний месяц фермер не принимает в штат ни одного сотрудника.

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Но если увеличить потребности рабочего времени в октябре до 11000 час вместо 10000, то получим значение x₆, равное 3. Понятно, что при неизменном объеме работ штат фермера не должен увеличиваться. Поэтому оптимальное решение может быть получено при дополнительном ограничении x₆ = 0.



2. Модель двухиндексной задачи

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

2.1 Построение модели транспортной задачи

2.1.1 Математическая модель задачи

Стандартная транспортная задача определяется как задача разработки наиболее экономичного плана перевозки продукции одного вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов F(X) прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции:

F(X) = > min, где

c_ij - стоимость перевозки единицы продукции из пункта отправления в пункт назначения;

x_ij - количество продукции, перевозимой из пункта отправления в пункт назначения (x_ij ? 0);

n - количество пунктов отправления, m - количество пунктов назначения.

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

, i = 1..n, где

a_i - запас продукции в пункте отправления A_i.

Вторая группа ограничений указывает, что суммарные перевозки продукции в некоторый пункт потребления должны полностью удовлетворить спрос на продукцию в этом пункте:

, j = 1..m, где

b_j - спрос на продукцию в пункте назначения B_j.

Из модели следует, что сумма запасов продукции во всех пунктах отправления должна равняться суммарной потребности во всех пунктах потребления:

Если это условие выполняется, то транспортная задача называется сбалансированной, в противном случае - несбалансированной. В случае, когда суммарные запасы превышают суммарные потребности, необходим дополнительный фиктивный пункт потребления, который будет формально потреблять существующий излишек запасов, т.е.

Если суммарные потребности превышают суммарные запасы, то необходим дополнительный фиктивный пункт отправления, формально восполняющий существующий недостаток продукции в пунктах отправления:

Для фиктивных перевозок вводятся фиктивные тарифы c_f, величину которых можно интерпретировать как штраф (c_f ? 0).

Задача о назначениях - частный случай транспортной задачи. Примером типичной задачи о назначениях является распределение работников по различным видам работ.

Переменные задачи о назначениях определяются следующим образом. Если i - рабочий работает на j - станке, то x_ij = 1, в противном случае x_ij = 0. Такие переменные называют булевыми.

2.1.2 Сбалансированная транспортная задача

Постановка задачи. Фирма «Альтаир» имеет 4 склада и 3 магазина продажи автомобилей. Известны: стоимость перевозки автомобилей по железной дороге по каждому из возможных маршрутов, ежедневный запас на складе и величина ежедневного спроса в магазинах, табл. 5.

Определить количество автомобилей, перевозимых с каждого склада в каждый магазин, таким образом, чтобы общие транспортные расходы были минимальны.



Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Математическая модель. Обозначим количество автомобилей, перевозимых из i-го склада в j-й магазин через x_ij.

Проверим равенство суммы запасов продукции (185) и суммарного спроса на автомобили (185). Отсюда следует вывод - задача сбалансирована.

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

Целевая функция. Суммарные затраты на ежедневную перевозку автомобилей определяются по формуле, р.:

F(X) = 2x₁₁ + 9x₁₂ + 7 x₁₃ + x₂₁ + 5x₂₃+ 5x₃₁ + 4x₃₂ + 100 x₃₃ + 2x₄₁ + 3x₄₂ + 6 x₄₃ > min.



Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Ограничения. Возможные объемы перевозок ограничиваются дневными запасами складов и потребностями магазинов. Ограничения по запасам, шт.:

x₁₁ + x₁₂ + x₁₃ = 25 - объем перевозок с первого склада;

x₂₁ + x₂₂ + x₂₃ = 50 - перевозки со второго склада;

x₃₁ + x₃₂ + x₃₃ = 35 - перевозки с третьего склада;

x₄₁ + x₄₂ + x₄₃ = 75 - перевозки с четвертого склада.

Ограничения по потребностям, шт:

x₁₁ + x₂₁ + x₃₁ =45 - потребности первого магазина;

x₁₂ + x₂₂ + x₃₂ = 90 - потребности второго магазина;

x₁₂ + x₂₂ + x₃₂ = 50 - потребности третьего магазина.

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Решение в Excel. Заполним рабочий лист исходными данными задачи, рис. 7. Введем формулы, соответствующие целевой функции и левым частям ограничений, табл. 6.

Подключим Поиск решения.

В упрощенном варианте структура отчета представлена в табл. 7.

Оптимальный план поставок продукции и соответствующие ему транспортные расходы предполагают следующие маршруты перевозок: с первого, со второго и третьего складов - только в один магазин; четвертый склад осуществляет перевозки во все три магазина.

2.1.3 Несбалансированная транспортная задача

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

Для установления баланса введем дополнительный фиктивный склад с недостающим запасом автомобилей 25 шт., табл. 8.

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Фиктивные тарифы c_f приравняем к нулю - перевозки в действительности производиться не будут.

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

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Матрица переменных X и значение целевой функции для несбалансированной задачи представлены в табл. 9. Результаты расчета показывают, что для данной модели задачи первый магазин остается без товаров.

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

2.2 Построение модели задачи с булевыми переменными (задача о назначениях)

Постановка задачи. Имеется четыре рабочих и четыре вида работ. Стоимости c_ij выполнения i - м рабочим j - й работы известны, рис. 8. Необходимо составить так план выполнения работ, чтобы все работы были выполнены, каждый рабочий был загружен только на одной работе, а суммарная стоимость работ была минимальной.

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Данная модель сбалансирована, т. е. число работ совпадает с числом рабочих. В противном случае в таблицу нужно ввести недостающее число фиктивных строк или столбцов с достаточно большими штрафными стоимостями работ.

Математическая формулировка задачи. Неизвестными в задаче являются переменные x_ij, . Будем считать, что x_ij = 1, если i - м рабочим выполняется j - я работа, и x_ij = 0, если i - м рабочим не выполняется j - я работа. Таким образом, x_ij принимает только два значения: 0 или 1. Такие переменные называются двоичными или булевыми. Кроме того, неизвестные должны удовлетворять еще одним ограничениям:

, j = 1,..4;, i = 1,..4.

Целевая функция описывается следующим выражением:

F(X) =.



Эту функцию необходимо минимизировать.

Решение в Excel. Все данные о стоимости работ введены в ячейки B3:E6 (рис. 9). Ячейки B8:E11 отведены под неизвестные. Ячейки строки 12 и столбца F заполнены формулами, задающими левые части ограничений на переменные задачи (использована функция автосуммирования).

В целевую ячейку F13 введена формула, вычисляющая общую стоимость работ: =СУММПРОИЗВ(B3:F6;B8:F11).



3. Варианты задач

1. Три совхоза ежедневно доставляют в город 50, 60, 40 центнеров молока для обеспечения пяти магазинов. Стоимость перевозки одного центнера молока и потребности магазинов в молоке указаны в таблице. Определить (и отобразить с помощью диаграммы) оптимальный план поставки молока в каждый магазин так, чтобы суммарные транспортные издержки были минимальными.

Совхозы	Затраты на перевозку одного центнера молока к магазинам	Запас молока (ц)
	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5
Совхоз 1	7	6	8	10	12	50
Совхоз 2	9	5	7	4	6	60
Совхоз 3	6	8	4	9	7	40
Потребности в молоке (ц)	30	20	55	20	25	150

2. Завод выпускает изделия трех моделей. Для их изготовления используются два вида ресурсов, запасы которых составляют 4000 и 6000 единиц. Расходы ресурсов на одно изделие каждой модели указаны в таблице.

Ресурс	Расход ресурсов на одно изделие
	Модель 1	Модель 2	Модель 3
Ресурс 1	4	3	2
Ресурс 2	4	4	5

Анализ условий сбыта показывает, что минимальный спрос на продукцию завода составляет 200, 200 и 150 изделий моделей 1, 2 и 3 соответственно. Однако, соотношение выпуска изделий моделей 1, 2 и 3 должно быть равно 3:2:5. Удельная прибыль от реализации изделий моделей 1, 2 и 3 составляет $30, $20 и $50 соответственно.

Определить программу выпуска изделий, приносящую максимальную общую прибыль, и отобразить эту программу с помощью диаграммы.

3. Фабрика производит два вида лаков: МЛ-0111 и МЛ-0112. Для производства лаков используются наполнитель и растворитель. Максимально возможные суточные запасы этих ингредиентов составляют 600 и 800 кг соответственно. Известны расходы наполнителей и растворителей на 1 кг соответствующих лаков. Изучение рынка сбыта показало, что суточный спрос на лак МЛ-0112 никогда не превышает спроса на лак МЛ-0111 более чем на 100 кг.

Кроме того, установлено, что спрос на лак МЛ-0112 никогда не превышает 200 кг в сутки. Оптовые цены одного килограмма лака равны: 3000 р. для МЛ-0111; 2000 р. для МЛ-0112.

Ингредиенты	Расход ингредиентов, кг ингр./кг краски	Запас, кг ингр./сутки
	МЛ-0111	МЛ-0112
Наполнитель	1	2	6
Растворитель	2	1	8

Определить программу выпуска лаков, приносящую максимальную общую прибыль и отобразить эту программу с помощью диаграммы.

4. Компания «Жажда» осуществляет производство прохладительных напитков на двух заводах -- А и В. Поставкой бутылок на каждый из заводов занимаются две фирмы - Р и Q. На ноябрь заводу А требуется 5000 бутылок, а заводу В - 3500 бутылок. Фирма Р может поставить максимум 7500 бутылок, а фирма Q - 4000 бутылок. Стоимость перевозки одной бутылки от каждого поставщика каждому заводу приведена в таблице.



Поставщик	Стоимость одной бутылки перевозки на завод, р.	Максимальный объем поставки
	Завод А	Завод В
Фирма Р	43	40	7500
Фирма Q	44	20	4000
Спрос на бутылки	5000	3500

Как следует организовать доставку бутылок на заводы, чтобы общая стоимость перевозки была минимальной? Отобразить результаты расчета с помощью диаграммы.

5. Авиакомпания «Небесный груз» располагает 8 самолетами типа 1, 15 самолетами типа 2, 12 самолетами типа 3, которые она может использовать для перевозки грузов в течение ближайших суток.

Грузоподъемность (в тысячах тонн) известна: 45 для самолетов типа 1, семь для самолетов типа 2, четыре для самолетов типа 3. Авиакомпания обслуживает города А и В. Городу А требуется тоннаж в 200000 т, а городу В - в 300000 т. Избыточный тоннаж не оплачивается, каждый самолет в течение дня может выполнить только один рейс. Расходы, связанные с перелетом самолетов по маршруту «центральный аэродром - пункт назначения», указаны в таблице.

Расходы, р	Тип 1	Тип 2	Тип 3
Город А	23000	5000	1400
Город В	58000	10000	3800

Определить оптимальный план грузоперевозок и отобразить его с помощью диаграммы.

6. Авиакомпании «Ночной полет» необходимо решить, какое количество топлива для реактивных самолетов следует закупить у трех фирм-поставщиков в четырех аэропортах.

Нефтяные компании констатируют следующие возможности поставки топлива в течение ближайшего месяца:

а) 2500000 л.- нефтяная компания 1;

б) 5000000 л. - нефтяная компания 2;

в) 6000000 л. - нефтяная компания 3.

Авиакомпании требуется следующее количество топлива:

а) 1000000 л. в аэропорту 1;

б) 2000000 л. в аэропорту 2;

в) 3000000 л. в аэропорту 3;

г) 4000000 л. в аэропорту 4;

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

Стоимость, р	Компания 1	Компания 2	Компания 3
Аэропорт 1	120	90	100
Аэропорт 2	100	110	140
Аэропорт 3	80	110	130
Аэропорт 4	110	130	90

Определить оптимальный вариант закупки топлива и отобразить его с помощью диаграммы.

7. Фирма, обслуживающая туристов прибывающих на отдых, должна разместить их в 4 отелях: «Морской», «Солнечный», «Слава» и «Уютный», в которых забронировано соответственно 5, 15, 15 и 10 мест. Пятнадцать туристов прибывают по железной дороге, двадцать пять прилетают очередным рейсом в аэропорт, а пять человек прибудут на теплоходе на морской вокзал. Транспортные расходы при перевозке из пунктов прибытия в отели приведены в таблице.

Исходный пункт	Пункт назначения (отели)
	Морской	Солнечный	Слава	Уютный
	1	2	3	4
Железнодорожный вокзал	1	10	0	20	11
Аэропорт	2	12	7	9	20
Морской вокзал	3	0	14	16	18

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

8. Сухогруз может принять на борт не более 1000 т груза, общий объем которого не должен превосходить 500 у. е. На причале находится груз 8 наименований (различные механизмы и нестандартное оборудование). Вес, объем и цена груза каждого наименования приведены в таблице.

Показатели	Номер груза
	1	2	3	4	5	6	7	8
Вес, т.	50	100	70	91	60	75	89	67
Объем, у. е.	45	31	25	44	37	40	29	35
Цена, тыс. р.	2,5	2,1	1,6	1,8	1,4	1,9	2,0	2,1

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

9. На двух складах имеется запас картофеля в количестве соответственно 150 и 90 т. Этот картофель необходимо доставить в три магазина, потребности которых составляют соответственно 60, 70 и 110 т. Стоимость перевозки 1 т картофеля от первого склада до первого магазина равна 6 руб., до второго магазина - 10 руб. и до третьего магазина - 4 руб. Стоимость перевозки 1 т. картофеля со второго склада до первого магазина составляет 12 руб., до второго магазина - 2 руб., до третьего магазина - 8 руб.

Необходимо составить план перевозок, при котором суммарная стоимость перевозок минимальна. Отобразить данные расчета с помощью диаграммы.

10. Небольшая семейная фирма производит два безалкогольных напитка - «Pink Fizz» и «Mint Pop». Объем производства ограничен количеством основного ингредиента и производственной мощностью имеющегося оборудования.

Для производства 1 л «Pink Fizz» требуется 0,02 ч работы оборудования, а для производства 1 л «Mint Pop» - 0,04 ч. Расход специального ингредиента составляет 0,01 кг и 0,04 кг на 1 л «Pink Fizz» и «Mint Pop» соответственно. Ежедневно в распоряжении фирмы имеется 24 ч времени работы оборудования и 16 кг специального ингредиента. Доход фирмы составляет 0,10 ф. ст. за 1 л «Pink Fizz» и 0,30 ф. ст. за 1 л «Mint Pop».

Кроме того, установлено, что суточный спрос на напиток «Mint Pop» составляет 300 л в сутки. Сколько продукции каждого вида следует производить ежедневно, если цель фирмы состоит в максимизации ежедневного дохода? Отобразить результаты расчета с помощью диаграммы.

11. Завод по производству электронного оборудования выпускает персональные компьютеры четырех моделей: «Юпитер», «Венера», «Марс» и «Сатурн».

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

Показатели	Время на единицу продукции, час.	Производственная мощность, ч/мес.
	«Юпитер»	«Венера»	«Марс»	«Сатурн»
Цех узловой сборки	5	8	20	25	1800
Цех сборочный	2	3	8	14	900
Цех испытательный	0,1	0,2	2	4	150
Максимальное значение спроса за месяц	100	45	25	20
Доход, ф. ст.	15	30	120	130

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

12. Три торговых склада Р, Q, R могут поставлять некоторое изделие в три магазина розничной торговли, находящихся в пунктах А, В и С. Количестве изделий, спрос на него и единичные издержки транспортировки приведены в таблице.

Поставщик	Транспортные издержки, ф. ст. за единицу	Общий объем предложения, шт.
	Магазин A	Магазин B	Магазин С
Торговый склад P	10	20	5	9
Торговый склад Q	2	10	8	4
Торговый склад R	1	20	7	8
Общий объем спроса, шт.	5	9	7

Какова минимальная стоимость транспортировки изделий от поставщиков потребителям? Отобразить результаты расчета с помощью диаграммы.

13. Фирма «Русский чайный дом» производит и продает две марки чая - «Боярский» и «Купеческий». Для их изготовления используются одни и те же сорта чая в разных пропорциях, указанных в таблице. В этой же таблице указаны дневные запасы ингредиентов.

Составить дневной план выпуска продукции, при котором прибыль фирмы будет максимальной, если прибыль от реализации 1 кг «Боярского» чая составляет 18 р, а от реализации «Купеческого» - 14 р. Учесть, что спрос на чай «Боярский» в два раза выше, чем на чай «Купеческий». Отобразить результаты расчета с помощью диаграммы.

Ингредиент (чай)	Сорт	Запас на день, кг
	«Боярский»	«Купеческий»
Цейлонский	0,6	0,3	60
Индийский	0,3	0,2	40
Грузинский	0,1	0,5	30

14. Для приготовления сэндвичей требуется горчица, кетчуп, мясо, и сыр в пропорциях, которые указаны в таблице. Для обеспечения ассортимента сэндвичей каждого вида необходимо изготавливать не менее 15 шт. в час.

Ингредиент	Чизбургер	Гамбургер	Запас ресурсов на 1 ч
Горчица	0,6 мл	0,6 мл	27 мл
Кетчуп	8 мл	5 мл	300 мл
Мясо	40 г	65 г	2600 г
Сыр	15 г	0	450 г

Прибыль от реализации одного чизбургера составляет 20 р, а от реализации гамбургера - 15 р. Какое количество сэндвичей каждого вида нужно изготавливать в час, чтобы прибыль ресторана была максимальной? Отобразить результаты расчета с помощью диаграммы.

15. Фармацевтическая фирма для изготовления двух видов сердечных препаратов использует три полуфабриката: фенотерол, динатрий, эналаприл. Их дневной запас составляет 400, 1500 и 900 кг соответственно. В результате смешивания этих трех компонентов в пропорции 1:3:1 получают сердечный препарат «энап», а при смешивании в пропорции 1:5:3 - сердечный препарат «энвас».

Прибыль от реализации 1 кг энапа составляет 300 р, а от реализации 1 кг энваса - 400 р. Определить дневной план выпуска продукции, при котором фирма получит максимальную прибыль. Отобразить результаты расчета с помощью диаграммы.

16. Комбинат по переработке фруктово-ягодной продукции производит мармелад и фруктовый концентрат. Для изготовления каждого вида продукции необходимы вода, сахар и фрукты. Пропорции, в которых они используются, указаны в таблице. Прибыль от реализации одной тонны мармелада равна 700 р, а от реализации одной тонны фруктового концентрата - 1000 р.

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

Пропорции	Дневной запас ресурса, т
Ресурсы	Мармелад, т	Фруктовый концентрат, т
Вода	0,5	1	6
Сахар	1	1	8
Фрукты	2	1	14

17. Завод выпускает два сорта пива - «Пиво 1» и «Пиво 2». Для производства пива требуются солод, хмель и вода. При этом прибыль от реализации 1 л пива сорта «Пиво 1» составляет 10 р, а от реализации 1 л пива сорта «Пиво 2» ? 12 р. Анализ рынка сбыта показывает, что спрос на «Пиво 2» в полтора раза превышает спрос на «Пиво 1».

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

Пропорции	Дневной запас ресурса, л
Ресурсы	«Пиво 1»	«Пиво 2»
Солод	0,3	0,4	800
Хмель	0,1	0,2	400
Вода	0,6	0,4	1000

18. Лаборатория «Эвента» начала выпуск и продажу опытной партии образцов - крема для ногтей и крема для тела. Для изготовления каждого крема используются активные вещества - гиалурон, карбопол и аллантоин (остальные ингредиенты имеются в избытке).

Затраты каждого ресурса на изготовление одного флакона крема и количество ресурсов, которыми лаборатория располагает на один день, приведены в таблице. Прогнозируемая прибыль от продажи одного флакона крема для тела составляет 6 р, а от продажи одного флакона крема для ногтей - 5 р.

Пропорции	Дневной запас ресурса, г
Ресурс	Крем для тела, г	Крем для ногтей, г
Гиалурон	1	1	50
Карбопол	3	2	120
Аллантоин	5	1	150

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

19. На конезаводе разводят две породы лошадей - верховая и тракененская. Лошади должны получать в день определенное количество кормов, указанное в таблице. Также в таблице указано общее количество корма каждого вида, которым конезавод располагает на день.

Прибыль от реализации лошади породы «верховая» составляет 1600 р, а от реализации лошади породы «тракененская» - 1200 р. Анализ рынка сбыта показывает, что спрос на лошади породы «верховая» в два раза превышает спрос на лошади породы «тракененская».

Корма	Верховая, кг	Тракененская, кг	Дневной запас корма, кг
Сено	2	3	180
Овес	4	1	240
Ячмень	6	7	426

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

20. Заводы некоторой автомобильной фирмы расположены в городах А, В и С. Основные центры распределения продукции сосредоточены в городах D и E. Объемы производства указанных трех заводов равняются 1000, 1300 и 1200 автомобилей ежеквартально. Величины квартального спроса в центрах распределения составляют 2300 и 1400 автомобилей соответственно. Стоимости перевозки автомобилей по железной дороге по каждому из возможных маршрутов приведены в таблице.

Стоимость перевозок, р/шт.	Центр D	Центр E
Город А	80	215
Город В	100	108
Город С	102	68

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

21. Фирмой "Супертранзистор" выпускаются радиоприемники трех различных моделей: модель А, модель В и модель С. Каждое изделие указанных моделей приносит доход в размере 8, 15 и 25 у. е. Необходимо, чтобы фирма выпускала за неделю не менее 100 приемников модели А, 150 приемников модели В и 75 приемников модели С.

Каждая модель характеризуется определенным временем, необходимым для изготовления соответствующих деталей, сборки изделия и его упаковки. В расчете на 10 приемников модели А требуется 3 часа для изготовления соответствующих деталей, 4 часа на сборку и 1 час на упаковку. Соответствующие показатели в расчете на 10 приемников модели В равняются 3,5 часам, 5 часам и 1,5 часа, а на 10 приемников модели С - 5 часам, 8 часам и 3 часам. В течение ближайшей недели фирма может израсходовать на производство радиодеталей 150 часов, на сборку 200 часов и на упаковку 60 часов.

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

22. Цех мебельного комбината выпускает трельяжи, трюмо и тумбочки под телевизоры. Норма расхода материала в расчете на одно изделие, плановая себестоимость, оптовая цена предприятия, плановый (месячный) ассортимент и трудоемкость единицы продукции приведены в таблице.

Показатели	Трельяжи	Трюмо	Тумбочки
Норма расхода материалов: древесностружечные плиты доски еловые доски березовые	0,032 0,020 0,005	0,031 0,020 0,005	0,038 0,008 0,006
Трудоемкость, чел-ч	10.2	7.5	5.8
Плановая себестоимость, р.	88.81	63.98	29.60
Оптовая цена предприятия, р.	93.00	67.00	30.00
Плановый ассортимент, шт	350	290	1200



Запас древесностружечных плит, досок еловых и березовых 90, 30 и 14 штук соответственно. Плановый фонд рабочего времени 16800 человеко-часов.

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

23. Полицейская служба «Участок 17» имеет следующие минимальные потребности в количестве полицейских в различное время суток:

Время суток часы	Порядковый номер периода	Минимальное число полицейских, требуемое в указанный период
2-6	1	20
6-10	2	50
10-14	3	80
14-18	4	100
18-22	5	40
22-2	6	30

При этом нужно иметь в виду, что период 1 следует сразу же за периодом 6.

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

24. Авиакомпании «Полет» требуется определить, сколько стюардесс следует принять на работу в течение шести месяцев при условии, если каждая из них должна пройти стажировку. Потребности в количестве стюардесс-часов (с.-ч.) летного времени известны: в январе требуется 8000 c.-ч., в феврале - 9000, в марте - 8000, в апреле - 10000, в мае -9000, в июне - 12000 с .-ч. Стажировка занимает один месяц. Следовательно, прием стюардессу на работу должен, по крайней мере, на один месяц опережать ввод стюардессы в штат обученных. Кроме того, каждая стюардесса за стажировку должна налетать 100 часов. Т.е. за счет каждой обучаемой стюардессы в течение месяца освобождается 100 час. рабочего времени, отведенного для уже обученных стюардесс.

Каждая обученная стюардесса может иметь налет до I50 час. в месяц. В январе уже имеется 60 опытных стюардесс. Установлено также, что примерно 10% обученных стюардесс увольняются по собственному желанию и другим причинам. Опытная стюардесса обходится авиакомпании 800 р., а обучаемая - в 400 р. в месяц.

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

25. Фабрика выпускает кожаные брюки, куртки и пальто специального назначения в ассортименте, заданном отношением 2:1:3. В процессе изготовления изделия проходят три производственных участка - дубильный, раскройный и пошивочный.

Время обработки изделий на каждом участке, их плановая себестоимость, оптовая цена предприятия приведены в таблице.

Показатели	Брюки	Куртки	Пальто
Норма времени на участках, чел-ч дубильном раскройном пошивочном	0.3 0.4 0.5	0.4 0.4 0.4	0.6 0.7 0.8
Полная себестоимость, р	15	40.5	97.8
Оптовая цена предприятия, р.	17.5	42	100

Ограничения на фонд времени для дубильного, раскройного и пошивочного участков составляют соответственно 3360, 2688 и 5040 час.

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

26. На приобретение оборудования для нового производственного участка выделено 300 тыс. р. Его предполагается разместить на площади 45 кв. м. Участок может быть оснащен оборудованием трех видов: машинами стоимостью 6 тыс. р. (здесь и далее все показатели приводятся на единицу оборудования), размещающимися на площади 9 кв. м., производительностью 8 тыс. ед. продукции за смену; машинами стоимостью 3 тыс. р. занимающими площадь 4 кв. м., производительностью 4 тыс. ед. продукции за смену; машинами стоимостью 2 тыс. р., занимающими площадь 3 кв. м., производительностью 3 тыс. единиц продукции в смену.

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

27. В плановом году строительные организации города переходят к сооружению домов типа Д-1, Д-2, Д-3 и Д-4. Данные о количестве квартир разного типа в каждом из указанных типов домов, их плановая себестоимость приведены в таблице:

Показатели	Д-1	Д-2	Д-3	Д-4
Типы квартир однокомнатные:	10	18	20	15
двухкомнатные: смежные	40	-	20	-
несмежные	-	20	-	60
трехкомнатные	60	90	10	-
четырехкомнатные	20	10	-	5
Плановая себестоимость,тыс. р	830	835	360	450

Годовой план ввода жилой площади составляет 800, 1000, 900, 2000 и 7000 квартир указанных типов. На жилищное строительство утвержден объем капиталовложений в размере 40 млн. р.

Требуется составить план (и отобразить с помощью диаграммы), при котором себестоимость всех вводимых домов будет минимальна.

28. Четыре растворных узла стройуправления потребляют в сутки 170, 175, 220 и 190 т песка, который производят три фабрики. Суточная производительность их соответственно 380, 340 и 300 т.

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

Показатели	Номер фабрики
	1	2	3
Стоимость перевозки 1т песка, р. к 1- ому узлу,	0,9	1,5	0,6
ко 2- ому узлу,	1	0,8	0,9
к 3- ому узлу,	0,7	0,4	1,2
к 4- ому узлу,	0,5	1	1,3
Цена 1т. песка, р.	3	2,9	2,2
Суточная стоимость погрузки, р.	19	25	15

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



4. Оформление пояснительной записки

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

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