Контрольная работа методы оптимальных решений Вариант 7 (5 задач) Фабрика выпускает два вида каш для завтрака Gruncy и Ghewy.

Задание 1. Графический метод решения задач линейного программирования

1. Составить математическую модель по условию задачи.

2. Решить задачу геометрическим способом.

3. Сделать выводы.

Условие задачи:

Фабрика выпускает два вида каш для завтрака Gruncy и Ghewy. Используемые для производства обоих продуктов ингредиенты в основном одинаковы и, как правило, не являются дефицитными. Основным ограничением, накладываемым на объём выпуска, является наличие фонда рабочего времени в каждом из трёх цехов фабрики. Управляющему производством необходимо разработать план производства в месяц. В приведённой ниже таблице указаны общий фонд рабочего времени и число человеко-часов, требуемое для производства 1 т. продукта.

Цех Необходимый фонд рабочего времени(чел.-ч./т) Общий фонд рабочего времени

²Gruncy² ²Ghewy² (чел.-ч. в месяц)

А. Производство 10 4 1000

В. Добавка приправ 3 2 360

С. Упаковка 2 5 600

Доход от производства 1т. Gruncy составляет 150 у.е., а от производства Ghewy75 у.е. На настоящий момент нет никаких ограничений на возможные объёмы продаж. Имеется возможность продать всю произведённую продукцию. Требуется определить объёмы производства каш Gruncy и Ghewy, максимизирующие общий доход фабрики за месяц.

Задание 2. Симплексный метод решения задач линейного программирования

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

1. Составить математическую модель задачи (сформировать систему ограничений и целевую функцию);

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

3. Построить симплексную таблицу и заполнить её первоначальным опорным планом;

4. Пользуясь алгоритмом симплексного метода, найти оптимальное решение задачи;

5. Сделать выводы.

6. Составить двойственную задачу, решить ее на основе теорем двойственности.

Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта

Ресурсы Нормы затрат ресурсов на единицу продукции Запасы

I вид II вид III вид

Труд 3 6 4 2000

Сырье 10 15 20 2400

Оборудование 0 3 5 1500

Цена 6 10 9

Задание 3. Транспортная задача

В m заводах имеется однородный груз продукции в количествах . Этот груз нужно перевести n потребителям, потребности которых равны . Стоимость перевозки единицы груза из i – го завода j – ому потребителю равна (таблица 5). Требуется составить план перевозки груза с заводов потребителям, при котором суммарные расходы на перевозку будут минимальными.

Исходные данные для варианта 7

а1 200

а2 600

а3 500

b1 150

b2 400

b3 200

b4 550

c11 5

c12 4

c13 2

c14 8

c21 3

c22 2

c23 5

c24 9

c31 6

c32 2

c33 5

c34 7

План решения задачи:

1. Выбрать из таблиц исходные данные своего варианта.

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

3. Записать в матрицу транспортной задачи первый опорный план, пользуясь одним из известных вам способов построения опорного плана (способ северо-западного угла, наименьшей стоимости, двойного предпочтения).

4. Проверить построенный опорный план на вырожденность. Если надо, принять меры для преодоления вырожденности опорного плана.

5. Рассчитать значение целевой функции для опорного плана.

6. По правилам метода потенциалов рассчитать потенциалы строк и столбцов.

7. Используя найденные потенциалы, проверить построенный опорный план на оптимальность.

8. Если решение оптимальное перейти к пункту 12.

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

10. Выполнить перемещение ресурсов по вершинам цикла, не нарушая баланса по строкам и столбцам матрицы тарифов.

11. Перейти к пункту 5-7.

12. Выписать оптимальное решение и провести его экономический анализ.

Задание 4. Теория игр

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

3 2

4 -1

5 3

2 4

Задание 5. Сетевые графики

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

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

Исходные данные представлены по вариантам. Постройте график с временными характеристиками. Сделайте выводы.

Время выполнения работ (Вариант 7)

Дуги (0;1) (0;2) (1;3) (1;4) (2;4) (2;5) (3;6) (4;6) (5;6)

tij 2 3 2 3 8 1 7 5 4

Содержание

Задание 1. Графический метод решения задач линейного программирования 3

Задание 2. Симплексный метод решения задач линейного программирования 8

Задание 3. Транспортная задача 16

Задание 4. Теория игр 22

Задание 5. Сетевые графики 25

Список использованной литературы 31