Содержание
Задание 1. Линейная производственная задача 3
1. Последовательное улучшение производственной программы 4
2. Графическое решение задачи 15
3. Решение задачи с помощью ЭВМ. 18
Задание 2. Двойственная задача 23
Задание 3. Задача о «расшивке узких мест производства» 26
Задание 4. Транспортная задача 32
1. Решение задачи методом потенциалов. 33
2. Проверка решения задачи с помощью ЭВМ 42
Задание 5. Динамическое программирование. Распределение капитальных вложений. 46
Задание 7. Матричная игра как модель конкуренции и сотрудничества. 54
Список используемой литературы 69
Задание 1. Линейная производственная задача
Составить модель линейной производственной задачи. Преобразовать данную задачу к виду основной задачи линейного программирования, решить ее методом направленного перебора базисных допустимых решений, обосновывая каждый шаг процесса, найти оптимальную производственную программу, максимальную прибыль, остатки ресурсов различных видов и указать «узкие места» производства. В последней симплексной таблице указать обращенный базис Q-1, соответствующий оптимальному набору базисных неизвесных.
Проверить, что обращенный базис исходную симплекс-таблицу переводит в последнюю.
Если по оптимальной производственной программе какие-то два вида продукции не должны выпускаться, то в таблице исходных данных вычеркнуть соответствующие два столбца, составить математическую модель задачи оптимизации производственной программы с двумя оставшимися переменными, сохранив прежнюю нумерацию переменных и решить эту задачу графически. Проверить решение исходной задачи симплексным методом с помощью ЭВМ.
Исходные данные:
А - технологическая матрица затрат различных видов ресурсов на единицу каждой продукции
B – вектор объемов ресурсов
C – вектор удельной прибыли
Решение.
Последовательное улучшение производственной программы
Математическая модель задачи:
Найти производственную программу
Максимизирующую прибыль
(1)
При ограничениях по ресурсам:
(2)
Где по смыслу задачи
т.е. (3)
Получили задачу на условный экстремум. Для ее решения систему неравенств (2) при помощи дополнительных неотрицательных неизвестных x5, x6, x7 заменим системой линейных алгебраических уравнений:
(4)
Где дополнительные переменные имеют смысл остатков соответствующих ресурсов. Среди всех решений системы (4), удовлетворяющих условию неотрицательности:
(5)
Надо найти то решение, при котором функция (1) примет наибольшее значение.
Воспользуемся тем, что правые части всех уравнений системы (4) неотрицательны, а система имеет предпочитаемый вид – дополнительные переменные являются базисными. Приравняв к нулю свободные переменные x1, x2, x3, x4, получаем базисное неотрицательное решение:
(6)
Первые четыре компонента определяют производственную программу:
(7)
по которой мы пока ничего не производим.
Дальнейший ход решения представим в виде симплексных таблиц. Для того, чтобы составить первую симплекс-таблицу, составим вспомогательную систему уравнений. Для этого представим соотношение (1) в виде уравнения:
(8)
И припишем его к системе (4). Получим:
(9)
Шаг 1.
В качестве разрешающей переменной выберем x1, так как этой переменной соответствует наименьший коэффициент в последнем уравнении системы (9) ?1= - 42.
Выберем разрешающую строку:
(10)
Разрешающей будет строка 1.
Разрешающий элемент стоит на пересечении разрешающей строки и разрешающего столбца и равен:
Исключаем неизвестную x1 из всех уравнений систему, кроме первого, используя преобразования Гаусса-Жордана.
Разделим элементы строки 1 на 5.
От элементов строки 2 отнимает соответствующие элементы строки 1, умноженные на 3.
От элементов строки 3 отнимает соответствующие элементы строки 1, умноженные на 4.
От элементов строки 4 отнимает соответствующие элементы строки 1, умноженные на -42.
После преобразований система уравнений (9) примет вид:
(11)
Составим таблицу 1, которая соответствует расширеной матрице вспомогательной системы (9). В столбце ?? запишем отношения:
Таблица 1.
Базис
H
x1
x2
x3
x4
x5
x6
x7
??
x5
132
5
2
4
1
1
0
0
x6
124
3
4
0
6
0
1
0
x7
117
4
2
5
4
0
0
1
P
0
-42
-28
-17
-19
0
0
0
После преобразований таблица примет вид, представленный в таблице 2.
Таблица 2.
Базис
H
x1
x2
x3
x4
x5
x6
x7
??
x1
0
0
x6
0
1
0
x7
0
0
1
P
0
0
0
Полученное решение не является оптимальным, так как существуют отрицательные коэффициенты ?j при переменных в последнем уравнении системы (и, соответственно, в последней строке таблицы). Будем продолжать процесс улучшения дальше.
Шаг 2.
Перепшем систему (11):
В качестве разрешающей переменной выберем x2, так как этой переменной соответствует наименьший коэффициент в последнем уравнении системы (11)
Выберем разрешающую строку:
(10)
Разрешающей будет строка 2.
Разрешающий элемент стоит на пересечении разрешающей строки и разрешающего столбца и равен:
Исключаем неизвестную x2 из всех уравнений систему, кроме первого, используя преобразования Гаусса-Жордана.
Разделим элементы строки 2 на
От элементов строки 1 отнимает соответствующие элементы строки 2, умноженные на .
От элементов строки 3 отнимает соответствующие элементы строки 2, умноженные на .
От элементов строки L отнимает соответствующие элементы строки 2, умноженные на .
После преобразований система уравнений (11) примет вид:
(12)
Представим преобразования в виде симплекс-таблиц. Таблица 3 соответствует системе (11).
Таблица 3.
Базис
H
x1
x2
x3
x4
x5
x6
x7
??
x1
0
0
66
x6
0