Контрольная работа по "Исследованию операций"

Вопрос 1.

     Для производства двух видов изделий  А и В используются три вида сырья.

На производство единицы изделия А требуется  затратить сырья первого вида 13 кг, второго вида- 32 кг., сырья третьего вида – 58 кг. На производство единицы  изделия В требуется сырья соответственно 24 кг, 32 кг и 29 кг.

     Производство  обеспечено сырьем первого вида в  количестве 312 кг, сырьем второго вида – 480 кг, сырьем третьего вида – 696 кг.

     Прибыль от реализации готового изделия А  составляет 4 усл.ед., а изделия В  – 3 усл.ед.

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

1. Сформулируйте математическую модель задачи линейного программирования по данному условию.
2. Является ли она задачей целочисленного программирования? Почему ?
3. Решите данную задачу графическим методом.
4. Дайте словесный ответна вопрос: «При каком выпуску изделий А и В прибыль предприятия будет наибольшей ?»

Решение.

1. Построение  математической модели.

Составим  таблицу по условию задачи:

 

Ввод  переменных:

Х₁ – количество единиц изделий А;

Х₂ – количество единиц изделий В. 

Тогда по условию задачи можно составить  следующую математическую модель задачи линейного программирования: 

 

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

3. Решение  графическим способом.

Построим  прямые системы ограничений и  затем – многоугольник допустимых решений. Прямые строим по точкам пересечения  с координатными осями.

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

OABCD – многоугольник допустимых решений.

O (0;0), A(0;13), B(4,4;10,6), C(9;6), D(12;0).

Grad F = (3;4).

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

F max = F( C ) = F ( 9 ; 6 ) = 4*9 + 3*6 = 54. 

4. Максимальная прибыль от реализации в размере 54 у.е., достигается при выпуске 9 единиц изделия А и 6 единиц изделия В. 
 
 
 

Вопрос 2.

     Цех-заготовитель поставляет в сборочный цех детали двух видов А и В. По договору между  цехами оговорены ежедневно два  срока поставок этих деталей, причем при поставке в первый срок деталей  А сборочный цех платит заготовительному премию 50 руб. При поставке изделий А во второй срок выплачивается премия 20 руб. При поставлке изделия В в первый срок премия составляет 30 руб., а во второй – 40 руб. Требуется определить оптимальный план поставок и получения деталей.

1. Условно примите цех-заготовитель за игрока А, сборочный цех – за игрока В и составьте матрицу игры.
2. Разрешима ли данная задача в «чистых стратегиях», почему ?
3. Решите данную задачу в смешанных стратегиях.
4. Дайте словесный ответ на вопрос: «Каков оптимальный план поставок деталей и какую гарантированную премию получит заготовительный цех ?»

РЕШЕИЕ.

Составим  платёжную матрицу:

Находим гарантированный  выигрыш, определяемый нижней ценой  игры a = max(ai) = 30, которая указывает на максимальную чистую стратегию A2. 
Верхняя цена игры b = min(bj) = 40. 
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 30 <= y <= 40. Находим решение игры в смешанных стратегиях. 
Математические модели пары двойственных задач линейного программирования можно записать так: 
найти минимум функции F(x) при ограничениях: 
50x₁+30x₂ >= 1 
20x₁+40x₂ >= 1 
F(x) = x₁+x₂ = min 
найти максимум функции Ф(y) при ограничениях: 
50y₁+20y₂ <= 1 
30y₁+40y₂ <= 1 
Ф(y) = y₁+y₂ = max 
Решаем эти системы  
Оптимальный план можно записать так: 
x₁ = ¹/₁₄₀ 
x₂ = ³/₁₄₀ 
F(X) = 1•¹/₁₄₀ + 1•³/₁₄₀ = ¹/₃₅

Оптимальный план двойственной задачи равен: 
y₁ = ¹/₇₀ 
y₂ = ¹/₇₀ 
Z(Y) = ¹/₃₅ 
Цена игры: g = 1 : ¹/₃₅ = 35 
p1 = ¹/₄ 
p2 = ³/₄ 
q1 = ¹/₂ 
q2 = ^½

То есть оптимально цех изготовитель должен с вероятностью 1/4  поставлять детали первого вида в первый срок и с вероятностью ¾  во вторй срок, а детали второго  вида с вероятностью ½ и в первй  и во второй срок. Тогда его гарантированная  премия составит не менее 35 рублей. 
 
 
 

Вопрос 3.

На предприятии  необходимо провести комплекс работ  по улучшению оборудования. Этот процесс  может быть проведен различными путями с различным количеством промежуточных  работ. Условно назовем первоначальное состояние оборудования – А, конечное (то, которого нужно добиться - М). Соответственно – Б, В, Г, Д, Е – промежуточные состояния оборудования. Стоимости перехода предприятия от одного состояния к другому (в усл.ед.) показаны в графе переходов. Используя принцип динамического программирования, найдите оптимальный по затратам путь улучшения оборудования предприятия.

 

РЕШЕНИЕ.

Построим  матрицу смежности вершин графа  D⁽⁰⁾. Веса несуществующих ребер принимаем равными 1000.

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

Результаты  итераций: