Методы оптимальных решений
Задачи линейного программирования и их решение с помощью методов оптимизации. Построение целевой функции и определение ее минимального и максимального значений при заданных условиях-ограничениях. Решение данных задач симплекс-методом и заполнение таблиц.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 06.06.2013 |
| Размер файла | 513,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
«Комсомольский-на-Амуре государственный технический университет»
Факультет экономики и менеджмента Кафедра «Экономика и финансы»
РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ
По теме: Методы оптимальных решений
Студент группы 1ЭКб-1 А.В. Аверина
Преподаватель И.И. Антонова
2013
Задача 1
Прядильная фабрика для производства двух видов пряжи использует три типа сырья - шерсть, капрон и акрил. Количество сырья используемого за год ограниченно: шерсти - 600т, капрона - 850т, акрила - 400т. Норма расхода сырья на 1 тонну пряжи первого вида составляет: 0,5т шерсти, о,2т - капрона и 0,3т акрила, а на второй вид пряжи: 0,2т шерсти, 0,6т капрона и 0,2т акрила. Прибыль с 1т пряжи первого вида составляет 1100р, второго - 900р.
Требуется составить задачу ЛП годового производства пряжи с целью максимизации прибыли.
Решение:
Задача 2
Решить графическим методом следующую задачу ЛП:
Решение
Рисунок 1
А:
+
В:
С:
А:
Ответ: в точке В (1;4) целевая функция минимальна.
Задача 3
Решить графическим методом следующую задачу ЛП:
Собственные средства банка составляют 110млн. долларов. Часть этих средств, но не менее 30млн. долларов должна быть размещена в кредитах. Банки должны иметь ликвидные активы (ценные бумаги, т.к. кредиты не являются ликвидными активами банка). Ликвидное ограничение следующее: ликвидные активы должны составлять не менее 40% средств, размещенных в кредитах и ценных бумагах.
Требуется максимизировать прибыль банка, если доходность кредитных вложений составляет 18%, а ценных бумаг - 12%.
Решение:
Рисунок 2
А:
B:
А:
B:
Ответ: в точке А (30;20) целевая функция минимальна.
Задача 4
Определить максимальное значение целевой функции при следующих условиях-ограничений.
Решение:
Решим задачу симплекс методом.
Таблица 1
|
БП |
Св.члены |
|||||||
|
8 |
1 |
3 |
1 |
0 |
0 |
2,67 |
||
|
6 |
1 |
1 |
0 |
1 |
0 |
6 |
||
|
10 |
2 |
1 |
0 |
0 |
1 |
10 |
||
|
у |
0 |
-3 |
-4 |
0 |
0 |
0 |
Выберем из таблицы 1 ключевой столбец и ключевую строку . Разрешающий коэффициент 3.
Таблица 2
|
БП |
Св.члены |
|||||||
|
8/3 |
1/3 |
1 |
1/3 |
0 |
0 |
8 |
||
|
10/3 |
2/3 |
0 |
-1/3 |
1 |
0 |
5 |
||
|
22/3 |
5/3 |
0 |
-1/3 |
0 |
1 |
4,4 |
||
|
у |
32/3 |
-5/3 |
0 |
4/3 |
0 |
0 |
Выберем из таблицы 2 ключевой столбец и ключевую строку . Разрешающий коэффициент 5/3.
Таблица 3
|
БП |
Св.члены |
||||||
|
54/45 |
0 |
1 |
12/45 |
0 |
-3/15 |
||
|
18/45 |
0 |
0 |
-21/45 |
1 |
-6/15 |
||
|
22/45 |
1 |
0 |
3/15 |
0 |
3/5 |
||
|
у |
810/45 |
0 |
0 |
1 |
0 |
1 |
Задача 5
Найти неотрицательные решения, минимизирующие линейную функцию при следующих условиях-ограничений.
Графическим методом:
Рисунок 3
1)
2)
3)
1)
2)
3)
Симплекс метод:
Таблица 4
|
БП |
Св. члены |
|||||||||
|
10 |
1 |
1 |
-1 |
0 |
0 |
1 |
0 |
0 |
||
|
12 |
1 |
3 |
0 |
-1 |
0 |
0 |
1 |
0 |
||
|
30 |
5 |
1 |
0 |
0 |
-1 |
0 |
0 |
1 |
||
|
y |
0 |
5 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
W |
-52 |
-7 |
-5 |
1 |
1 |
1 |
0 |
0 |
0 |
Выберем из таблицы 4 ключевой столбец и ключевую строку Разрешающий коэффициент 5.
Продолжаем расчеты.
Таблица 5
|
БП |
Св. члены |
||||||||
|
4 |
0 |
4/5 |
-1 |
0 |
1/5 |
1 |
0 |
||
|
6 |
0 |
14/5 |
0 |
-1 |
1/5 |
0 |
1 |
||
|
6 |
1 |
1/5 |
0 |
0 |
-1/5 |
0 |
0 |
||
|
y |
-30 |
0 |
2 |
0 |
0 |
1 |
0 |
0 |
|
|
W |
-10 |
0 |
-18/5 |
1 |
1 |
-2/5 |
0 |
0 |
оптимизация целевая функция симплекс
Выберем из таблицы 5 ключевой столбец и ключевую строку Разрешающий коэффициент 14/5.
Продолжаем расчеты.
Таблица 6
|
БП |
Св. члены |
|||||||
|
32/14 |
0 |
0 |
-1 |
4/14 |
10/70 |
1 |
||
|
30/14 |
0 |
1 |
0 |
-5/14 |
1/14 |
0 |
||
|
78/14 |
1 |
0 |
0 |
1/14 |
-15/70 |
0 |
||
|
y |
-480/14 |
0 |
0 |
0 |
10/14 |
12/14 |
0 |
|
|
W |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Задача 6
Из трех холодильников, вмещающих мороженную рыбу в количествах aiт, необходимо последнюю доставить впять магазинов в количествах biт. Стоимости перевозки 1т рыбы из холодильника Ai в магазинBi заданы в виде матрицы. Написать математическую модель задачи и спланировать перевозки так, чтобы их общая стоимость была минимальной.
а1=320 б1=15 20 23 20 15 24
а2=280 б2=140 29 15 16 19 29
а3=250 б3=110 6 11 10 9 8 б4=230 б5=220
Решение:
Таблица 7
|
Потребители и их спросы |
||||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
||
|
А1 |
20 - |
23 - |
20 - |
15 230 |
24 90 |
|
|
А2 |
29 - |
15 140 |
16 - |
19 - |
29 30 |
|
|
А3 |
6 150 |
11 - |
10 - |
9 - |
8 100 |
|
|
Вi |
150 |
140 |
110 |
230 |
220 |
В каждой строке и в каждом столбце выберем ячейки с минимальной стоимостью. Расставим объёмы перевозок, начиная с самой минимальной стоимости. В результате получим таблицу.
Количество занятых клеток: 5+3-1=7. Найдем потенциалы по формуле для каждой занятой клетки.
Таблица 8
|
Потребители и их спросы |
Потенциалы поставщиков |
||||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
|||
|
А1 |
20 - |
23 - |
20 - |
15 230 |
24 90 |
-5 |
|
|
А2 |
29 - |
15 140 |
16110 |
19 - |
29 30 |
0 |
|
|
А3 |
6 150 |
11 - |
10 - |
9 - |
8 100 |
-21 |
|
|
Потенциалы потребителей |
27 |
15 |
16 |
20 |
29 |
12040 |
Найдем значение целевой функции:
y=15*230+24*90+15*140+16*110+29*30+6*150+8*100=12040
Проверим выполнение условий в каждой незанятой клетке.
Имеется две клетки, в которых следовательно, план не оптимален. Построим цикл перераспределения объёмов перевозки для ячейки (2,4). Объём перераспределения равен min(230, 90, 30) = 30. Перераспределим значения и снова рассчитаем потенциалы.
Таблица 9
|
Потребители и их спросы |
Потенциалы поставщиков |
||||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
|||
|
А1 320 |
20 - |
23 - |
20 - |
15 200 |
24120 |
-4 |
|
|
А2 280 |
29 - |
15 140 |
16110 |
19 30 |
29 - |
0 |
|
|
А3 250 |
6 150 |
11 - |
10 - |
9 - |
8 100 |
-20 |
|
|
Потенциалы потребителей |
26 |
15 |
16 |
19 |
28 |
12010 |
Найдем значение целевой функции:
Имеется одна клетка, в которой следовательно, план не оптимален. Построим цикл перераспределения объёмов перевозки для ячейки (1,1). Объём перераспределения равен min (150, 120, 100) = 100. Перераспределим значения и снова рассчитаем потенциалы.
Таблица 10
|
Потребители и их спросы |
Потенциалы поставщиков |
||||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
|||
|
А1 320 |
20 100 |
23 - |
20 - |
15200 |
2420 |
-4 |
|
|
А2 280 |
29 - |
15 140 |
16110 |
19 30 |
29 - |
0 |
|
|
А3 250 |
6 50 |
11 - |
10 - |
9 - |
8 200 |
-20 |
|
|
Потенциалы потребителей |
26 |
15 |
16 |
19 |
28 |
11810 |
В полученном плане выполняется условие в каждой незанятой клетке.
Найдем значение целевой функции:
Ответ: полученный план является оптимальным.
Размещено на Allbest.ru
Подобные документы
Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.
курсовая работа [219,4 K], добавлен 17.04.2013Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.
курсовая работа [65,3 K], добавлен 30.11.2010Графическое решение задачи линейного программирования. Общая постановка и решение двойственной задачи (как вспомогательной) М-методом, правила ее формирования из условий прямой задачи. Прямая задача в стандартной форме. Построение симплекс таблицы.
задача [165,3 K], добавлен 21.08.2010Линейное программирование как наиболее разработанный и широко применяемый раздел математического программирования. Понятие и содержание симплекс-метода, особенности и сферы его применения, порядок и анализ решения линейных уравнений данным методом.
курсовая работа [197,1 K], добавлен 09.04.2013Поиск оптимальных значений некоторых параметров в процессе решения задачи оптимизации. Сравнение двух альтернативных решений с помощью целевой функции. Теорема Вейерштрасса. Численные методы поиска экстремальных значений функций. Погрешность решения.
презентация [80,6 K], добавлен 18.04.2013Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.
контрольная работа [66,3 K], добавлен 06.04.2012Численные методы поиска безусловного экстремума. Задачи безусловной минимизации. Расчет минимума функции методом покоординатного спуска. Решение задач линейного программирования графическим и симплексным методом. Работа с программой MathCAD.
курсовая работа [517,9 K], добавлен 30.04.2011Основные сведения о симплекс-методе, оценка его роли и значения в линейном программировании. Геометрическая интерпретация и алгебраический смысл. Отыскание максимума и минимума линейной функции, особые случаи. Решение задачи матричным симплекс-методом.
дипломная работа [351,2 K], добавлен 01.06.2015Составление математической модели задачи. Определение всевозможных способов распила 5-метровых бревен на брусья 1,5, 2,4, 3,2 в отношении 1:2:3 так, чтобы минимизировать общую величину отходов. Решение задачи линейного программирования симплекс-методом.
задача [26,1 K], добавлен 27.11.2015Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.
задача [58,6 K], добавлен 16.02.2016
