Курсовая на тему Курсовая работа 120323-03

Содержание


Задание 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