Xreferat.com » Рефераты по информатике и программированию » Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

решению линейных задач математического программирования" width="36" height="21" align="BOTTOM" border="0" />0 – 4 – 0 = –4Практикум по решению линейных задач математического программирования0;

(2; 3) Практикум по решению линейных задач математического программирования1 + 3 – 5 = –1Практикум по решению линейных задач математического программирования0;

(2; 4) Практикум по решению линейных задач математического программирования1 + 1 – 8 = –6Практикум по решению линейных задач математического программирования0;

(2; 5) Практикум по решению линейных задач математического программирования1 – 4 – 0 = –4Практикум по решению линейных задач математического программирования0;

(3; 1) Практикум по решению линейных задач математического программирования4 + 1 – 6 = –1Практикум по решению линейных задач математического программирования0;

(3; 2) Практикум по решению линейных задач математического программирования4 + 2 – 8 = –2Практикум по решению линейных задач математического программирования0;

(3; 3) Практикум по решению линейных задач математического программирования4 + 3 – 7 = 0Практикум по решению линейных задач математического программирования0;

(3; 4) Практикум по решению линейных задач математического программирования4 + 1 – 10 = –5Практикум по решению линейных задач математического программирования0;

(4; 1) Практикум по решению линейных задач математического программирования4 + 1 – 5 = 0Практикум по решению линейных задач математического программирования0;

(4; 4) Практикум по решению линейных задач математического программирования4 + 1 – 2 = 3Практикум по решению линейных задач математического программирования0.


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

Осуществим переход к нехудшему опорному плану. Наиболее перспективная для заполнения клетка (4; 4), т. к. ей соответствует наибольшая положительная оценка

Практикум по решению линейных задач математического программирования4 + 1 – 2 = 3.

Найдем цикл перераспределения груза для этой клетки.

Выбранной для заполнения клетке присваиваем знак «+», далее знаки чередуем. Среди вершин со знаком «–» выбираем наименьшую поставку.

Практикум по решению линейных задач математического программирования– объем перепоставки.

Перераспределим поставки по циклу, тем самым перейдем к новому опорному плану.


Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

31 52 17 20 45

Практикум по решению линейных задач математического программирования

35
5
4
3
1
0 0



17 18

40
2
3
5
8
0 –2

31 9



40
6
8
7
10
0 1





40
50
5
6
7
2
0 1


43
2 5

Практикум по решению линейных задач математического программирования

4 5 3 1 –1 Таб.2

Практикум по решению линейных задач математического программированияТранспортные затраты, соответствующие опорному плану:

Практикум по решению линейных задач математического программирования (ден. ед.).

Исследуем опорный план на оптимальность. Найдем значения потенциалов, используя первое условие оптимальности. Для заполненных поставками клеток Практикум по решению линейных задач математического программирования.

Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования.

Проверим выполнение второго условия оптимальности. Для всех пустых клеток должно выполняться неравенство: Практикум по решению линейных задач математического программирования.

Выпишем клетки, в которых условие нарушено:

(1; 2) Практикум по решению линейных задач математического программирования0 + 5 – 4 = 1Практикум по решению линейных задач математического программирования0.

Осуществим переход к нехудшему опорному плану. Наиболее перспективная для заполнения клетка (1; 2), т. к. ей соответствует положительная оценка Практикум по решению линейных задач математического программирования1. Найдем цикл перераспределения груза для этой клетки.

Практикум по решению линейных задач математического программирования– объем перепоставки.

Число заполненных клеток распределительной таблицы 8 равно рангу матрицы задачи r = 8, следовательно, опорный план (таб. 3) является невырожденным.


Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

31 52 17 20 45

Практикум по решению линейных задач математического программирования

35
5
4
3
1
0 0


18 17


40
2
3
5
8
0 –1

31 9



40
6
8
7
10
0 2





40
50
5
6
7
2
0 2


25
20 5

Практикум по решению линейных задач математического программирования

3 4 3 0 –2 Таб.3

Транспортные затраты, соответствующие опорному плану:

Практикум по решению линейных задач математического программирования (ден. ед.).

Исследуем опорный план на оптимальность.

Найдем значения потенциалов, используя первое условие оптимальности. Для заполненных поставками клеток Практикум по решению линейных задач математического программирования.

Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования,Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования.

Проверим выполнение второго условия оптимальности. Для всех пустых клеток должно выполняться неравенство: Практикум по решению линейных задач математического программирования.

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

Наименьшие транспортные затраты Практикум по решению линейных задач математического программирования.

Ответ: Практикум по решению линейных задач математического программирования; оптимальный план распределения поставок расположен в таб. 3.

Задания для самостоятельной работы.

Составить план перевозок с минимальными транспортными затратами.


а)

Практикум по решению линейных задач математического программирования


б)

Практикум по решению линейных задач математического программирования


Решение оптимизационных задач с помощью Excel

При решении оптимизационных экономических задач необходимо пройти через следующие этапы:

Составить математическую модель экономической задачи;

Решить полученную экстремальную математическую задачу;

Дать экономическую интерпретацию ответу.

Рассмотрим прохождение этих этапов на примере задачи об использовании ресурсов.

Пример. Для изготовления изделий двух видов А и В на заводе используют сырье четырех типов (І, ІІ, ІІІ, IV). Для выпуска изделия А необходимо 2 единицы сырья І типа; 1 ед. сырья ІІ типа; 2 ед. сырья ІІІ типа; 1 ед. сырья IV типа. Для изготовления изделия В требуется 3 единицы сырья І типа; 1 ед. сырья ІІ типа; 1 ед. сырья ІІІ типа. Запасы сырья составляют: І типа – 21 ед., ІІ типа – 8 ед., ІІІ типа – 12 ед., IV типа – 5 ед. Выпуск одного изделия типа А приносит 3 грн. прибыли, а одного изделия типа В – 2 грн. прибыли. Составить план производства, обеспечивающий наибольшую прибыль.

Решение.

Составление математической модели.

Вопрос задачи, сформулированный в виде «составить план производства, обеспечивающий наибольшую прибыль», означает, что необходимо определить, какое количество изделий А и В нужно производить (для достижения наибольшей прибыли).

Так как необходимо определить количество изделий А и В, то введем следующие обозначения:

Практикум по решению линейных задач математического программирования– количество изделий А, планируемое к выпуску;

Практикум по решению линейных задач математического программирования– количество изделий В, планируемое к выпуску;

Z (целевая функция задачи) по своему экономическому смыслу – это прибыль. (Т.к. из условия задачи мы видим, что слово «наибольшая», связанное с экстремумом, соответствует прибыли).

Получим:


Практикум по решению линейных задач математического программирования – математическая модель задачи.


Решение полученной экстремальной задачи:


Для решения задачи воспользуемся возможностями Microsoft Excel.

Откройте Microsoft Excel.

В ячейки первой строки (в данном случае А1 и В1) введите обозначения имеющихся в задаче переменных Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования (язык и шрифт значения не имеют, т. к. обозначения необходимы для понимания смыслов соответствующих им чисел).

В ячейки второй строки (в данном случае А2 и В2), соответствующие заполненным ячейкам первой, введите произвольные значения переменных (для простоты возьмем значения 1, хотя на самом деле это могут быть любые числа). Тем самым мы присваиваем Практикум по решению линейных задач математического программирования и Практикум по решению линейных задач математического программирования пока значения 1.

В ячейку А4 введите обозначение целевой функции Z=.

В ячейку В4 введите формулу вычисления целевой функции из математической модели задачи

(Практикум по решению линейных задач математического программирования), подставляя вместо Практикум по решению линейных задач математического программирования и Практикум по решению линейных задач математического программирования, соответствующие им значения из ячеек А2 и В2. (Вспомните, что введение формулы начинается со знака =)


После нажатия кнопки Enter на экране монитора должно быть следующее. (Продумайте, как изменится картинка, если ввести иные значения Практикум по решению линейных задач математического программирования и Практикум по решению линейных задач математического программирования, к примеру, не 1, а 2. А теперь поэкспериментируйте. Оправдался ваш прогноз?)

В ячейки А5 и В5 введите соответственно слова: А5 – Ограничение, В5 – Правая часть ограничения.

В ячейку А6 введите формулу вычисления левой части первого ограничения Практикум по решению линейных задач математического программирования, подставляя вместо Практикум по решению линейных задач математического программирования и Практикум по решению линейных задач математического программирования, соответствующие им значения из ячеек А2 и В2.

В ячейку В6 введите свободный член первого ограничения – 21. После нажатия кнопки Enter на экране монитора должно быть следующее.

Аналогично в ячейку А7 введите формулу вычисления левой части второго ограничения Практикум по решению линейных задач математического программирования, а в В7 его свободный член – 8; в ячейку А8 введите формулу вычисления левой части третьего ограничения Практикум по решению линейных задач математического программирования, а в В8 его свободный член – 12; в ячейку А9 введите формулу вычисления левой части четвертого ограничения Практикум по решению линейных задач математического программирования, а в В9 его свободный член – 5;

После нажатия кнопки Enter на экране монитора должно быть следующее.

Таким образом, мы ввели все данные условия задачи в компьютер и подготовились к тому, чтобы задачу решить.

В меню Сервис выберите команду Поиск решения (именно она является инструментом для поиска решений задач оптимизации)

В этой команде вам будет предложено установить целевую ячейку. Именно слово «целевую» поможет вам в дальнейшем вспомнить, о чем идет речь. Конечно же, о значении целевой функции. Введите это значение, щелкнув левой кнопкой мышки на ячейке В4 (содержащей в данном случае числовое значение целевой функции). Получите:

Т.к. в данной задаче функция Z исследуется на максимум, то оставляем Равной: • максимальному значению.

Если решаем задачу на минимум, то нужно поставить метку • перед словами минимальному значению.

Далее нажмите на стрелку, расположенную в правой части пространства ячейки Изменяя ячейки:, в результате чего на экране должно появиться следующее

В полученное пространство необходимо ввести диапазон изменяющихся в задаче переменных (т.е. ячейки, содержащие числовые значения Практикум по решению линейных задач математического программирования и Практикум по решению линейных задач математического программирования, т. к. именно Практикум по решению линейных задач математического программирования и Практикум по решению линейных задач математического программирования могут принимать различные числовые значения, среди которых мы и пытаемся отыскать оптимальное решение задачи).

Т.е. заполненная ячейка должна принять вид:

После этого заполняют пространство ячейки Ограничения: Для чего нужно щелкнуть по кнопке Добавить, в результате чего на экране появится новое окно:

В Ссылка на ячейку: введите номер ячейки, содержащей левую часть ограничения (в данном случае для первого ограничения – это ячейка А6).

Выберите знак ограничения в соответствии с математической моделью из предлагаемых вариантов (в данном случае <=, т. к. первое ограничение со знаком Практикум по решению линейных задач математического программирования)

В Ограничение: введите номер ячейки, содержащей свободный член ограничения (в данном случае для первого ограничения – это ячейка В6).

Т.о. перед вами на экране должна быть следующая картинка:

Это вы ввели только первое ограничение, а есть еще и другие, поэтому нажмите кнопку Добавить и аналогичным образом введите второе, третье и четвертое ограничения.

Но после того, как все ограничения системы введены, еще рано нажимать ОК, т. к. в математической модели имеется условие неотрицательности переменных (Практикум по решению линейных задач математического программирования), а в описании задачи для компьютера оно еще не упоминалось.

Поэтому после введения последнего ограничения вновь нажмите кнопку Добавить и в Ссылка на ячейку: введите номер ячейки, содержащей числовое значение Практикум по решению линейных задач математического программирования; выберите знак >=; а в Ограничение: введите 0.

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

Таким образом, компьютер получил все те ограничения, которые есть в условии задачи, поэтому теперь можно нажать ОК. В результате на экране появится следующее:

Появилось? Если ДА, то нажимайте Выполнить.

И согласитесь на то, чтобы Сохранить найденное решение. Т.е. в появившемся окне нажмите ОК.

Обратите внимание на то, какие теперь значения принимают Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: