|
Содержание работы или список заданий
|
Работа 1. Решение задачи распределения ресурсов
1. Цель работы
Ознакомление с решением ЗЛП симплес-методом и надстройкой Поиск решения.
2. Основные теоретические положения
Из теорем двойственности следует, что оптимальные решения прямой и двойственной задач должны удовлетворять следующим свойствам:
1) оптимальные решения следует искать среди допустимых базисных решений;
2) все производства, входящие в оптимальный план прямой задачи, должны быть рентабельными, т. е. для всех базисных переменных xj величины Δj =0;
3) все производства, не входящие в оптимальный план, должны быть неприбыльными, т. е. для всех небазисных переменных xj Δj ≥ 0, т. е. допустимый базисный план прямой задачи X – неоптимальный, если хотя бы для одной небазисной переменной xj величина <0;
4) максимальное значение выручки в прямой задаче Z будет равно минимальной стоимости всех ресурсов в теневых ценах W, т. е. max Z = min W;
5) допустимый базисный план прямой задачи X будет оптимальным, если соответствующие ему двойственные переменные будут допустимым решением двойственной задачи (критерий оптимальности).
Эти свойства положены в основу симплекс-метода для решения задач линейного программирования. Нахождение оптимального решения осуществляется итеративно (последовательно): на каждой итерации происходит переход от одного базисного решения к другому базисному решению, в котором значение целевой функции улучшается. Итеративный процесс заканчивается, когда дальнейшее улучшение целевой функции невозможно.
3. Порядок выполнения работы
Задание 1. Найти оптимальное решение задачи распределения ресурсов, используя алгоритм симплекс-метода.
Задание 2. Найти оптимальное решение той же задачи распределения ресурсов, используя надстройку Поиск решения.
Работа 2. Решение транспортной задачи и матричной игры
1. Цель работы
Ознакомление с решением транспортной задачи и матричной игры надстройкой Поиск решения
2. Основные теоретические положения
Транспортная задача
Предположим, что заданы величины a1, a2,…, an, и b1, b2,…, bm, которые определяют максимальные производительности пунктов производства и минимальные потребности пунктов потребления соответственно.
Обозначим:
cij – стоимость перевозок единицы продукции из пункта производства Ai в пункт потребления Bj;
xij – количество продукции, направляемое из пункта производства Ai в пункт потребления Bj. Совокупность чисел {xij} образует план перевозок.
Требуется определить такой план перевозок, который минимизирует транспортные расходы.
Математически в транспортной задаче требуется найти план перевозок {xij}, который минимизирует транспортные расходы
(2.1.1)
при ограничениях
, (2.1.2)
, (2.1.3)
xij ≥ 0. (2.1.4)
Отсюда следует, что транспортная задача является задачей линейного программирования.
Решение матричных игр симплекс – методом
Для определения значения игры v и оптимальных стратегий игрока I p1, p2,…, pn необходимо решить задачу линейного программирования:
найти переменные v, p1, p2,…, pn, которые максимизируют выигрыш v игрока I
max v
при ограничениях
для всех j = 1, 2,…, m
p1 + p2 +…+ pn = 1
pi ≥ 0, v - не имеет ограничения на знак.
Для определения значения игры v и оптимальных стратегий игрока I q1, q2,…, qm необходимо решить задачу линейного программирования:
найти переменные v, pi, которые максимизируют выигрыш v игрока I
max v
при ограничениях
для всех j = 1, 2,…, m
p1 + p2 +…+ pn = 1
pi ≥ 0, v - не имеет ограничения на знак.
Заметим, что задачи определения значения игры и оптимальных стратегий образуют пару двойственных задач линейного программирования.
3. Порядок выполнения работы
Задание 1. Найти оптимальное решение транспортной задачи, используя надстройку Поиск решения.
Задание 2. Найти оптимальное распределение средств инвестора, используя надстройку Поиск решения.
3.1. Выполнение задания 1
Рассмотрим реализацию решения транспортной задачи на примере.
Пример
Рассмотрим транспортную задачу, в которой в трех пунктах производства:
A1, A2, A3
изготавливается однородная продукция в количествах:
a1=30, a2=40, a3=20
соответственно. Эту продукцию требуется доставить в четыре пункта потребления:
B1, B2, B3, B4
в количествах
b1=20, b2=30, b3=30, b4=10
соответственно. Матрица C задает стоимости перевозок единицы продукции cij из пункта производства Ai в пункт потребления Bj:
.
Требуется определить план перевозок, который минимизирует транспорт-ные расходы.
Запишем математическую модель данной транспортной задачи.
Обозначим xij – количество продукции, направляемое из пункта произ-водства Ai в пункт потребления Bj (табл. 2.1.1). Составим матрицу перевозок из величин xij
Таблица 2.1.1
B1 B2 B3 B4
20 30 30 10
A1 30 x11 x12 x13 x14
A2 40 x21 x22 x23 x24
A3 20 x31 x32 x33 x34
Сумма элементов первой строки: x11 + x12 + x13 + x14 определяет количество продукции, вывозимое из пункта производства A1. По условию задачи эта величина не может превосходить максимального количества продукции a1 = 30, производимого в этом пункте, т.е. должно выполняться неравенство:
x11 + x12 + x13 + x14 ≤ 30.
Аналогично сумма элементов второй строки x21 + x22 + x23 + x24 определяет количество продукции, вывозимое из пункта производства A2. По условию задачи эта величина не может превосходить максимального количества продукции a2=40, производимого в этом пункте, т.е. должно выполняться неравенство:
x21 + x22 + x23 + x24 ≤ 40.
Сумма элементов третьей строки x31 + x32 + x33 + x34 определяет количество продукции, вывозимое из пункта производства A3. По условию задачи эта величина не может превосходить максимального количества продукции a3 = 20, производимого в этом пункте, т.е. должно выполняться неравенство
x31 + x32 + x33 + x34 ≤ 20.
Сумма элементов первого столбца x11 + x21 + x31 определяет количество продукции, ввозимое в пункт B1. По условию задачи эта величина не меньше минимального количества продукции b1 = 20, необходимого в этом пункте потребления, т.е. должно выполняться неравенство:
x11 + x21 + x31 ≥ 20.
Аналогично для всех остальных пунктов потребления должны выполняться неравенства:
x12 + x22 + x32 ≥ 30,
x13 + x23 + x33 ≥ 30,
x14 + x24 + x34 ≥ 10.
Математически транспортную задачу можно сформулировать следующим образом:
– найти переменные xij , которые минимизируют транспортные расходы
T = 2x11+3x12+3x13+4x14+3x21+2x22+5x23+x24+4x31+3x32+2x33+6x34 (2.2.1)
– при ограничениях
x11+ x12+x13+x14 ≤ 30,
x21+ x22+x23+x24 ≤ 40, (2.2.2)
x31+ x32+x33+x34 ≤ 20,
x11+ x21+x31 ≥ 20,
x12+ x22+x32 ≥ 30,
x13+ x23+x33 ≥ 30, (2.2.3)
x14+ x24+x34 ≥ 10,
xij ≥ 0.
Вариант 3.
N1 =3 ; N2 =2
Фирма выпускает два вида изделий А и В. Каждое изделие проходит обработку на двух технологических линиях. Известна таблица технологических коэффициентов tij – времени обработки (в минутах) каждого изделия на каждой технологической линии. Кроме этого, известны рыночная цена каждого изделия с1 и с2 и общее время работы каждой линии Т1 и Т2.
Изделия А Изделия В Общее время работы линии
линия I 60 27 1620
линия II 32 60 1920
цена одного изделия 20 15
Задание 1. Графическое решение задачи распределения ресурсов.
• Записать стандартную и каноническую формы
• Найти все базисные и допустимые базисные решения. Определить оптимальное базисное решение.
• Найти графически оптимальное базисное решение.
Задание 2. Двойственная задача.
• Записать двойственную задачу и дать ее экономический смысл.
• Найти оптимальное решение двойственной задачи.
• Определить целесообразность производства продукции 3, для которой на единицу продукции требуется 4 кг. сырья и 0,4 часа времени изготовления. Рыночная цена составляет 120 ден.ед. за единицу продукции.
|