«Методы оптимальных решений»




Скачать 147.96 Kb.
Название«Методы оптимальных решений»
Дата публикации22.02.2014
Размер147.96 Kb.
ТипКонтрольная работа
skachate.ru > География > Контрольная работа

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ


ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ

ИМЕНИ В.С. ЧЕРНОМЫРДИНА»

(Филиал МГОУ имени В.С. Черномырдина в г. Воскресенске)

Кафедра «Прикладной математики»


«УТВЕРЖДАЮ»

Зав. кафедрой Прикладной математики

филиала МГОУ им. В.С. Черномырдина

в г. Воскресенске

______________________

/ профессор, к.т.н. А.Н. Баринов /

«____» _________________ 2013 г.

^ Контрольная работа
по дисциплине «Методы оптимальных решений»

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

(направление подготовки - 080100 «Экономика»)
Составил:

Ст. преподаватель _____________________ Нидеккер Ирина Анатольевна

г. Воскресенск, 2013 г.

^ Контрольная работа выполняется по варианту, номер которого совпадает с последней цифрой номера в зачетной книжке.
ЗАДАНИЕ 1. «Оптимальное использование ресурсов»
^ Формулировка задачи оптимального использования ресурсов. Предприятие из m видов ресурсов изготавливает n видов продукции. Известны нормы каждого вида ресурса для изготовления единицы продукции, запасы ресурсов на складе и прибыль от реализации единицы продукции.

aij – количество i-го ресурса на единицу j-го продукта;

bi – запас i-го ресурса (i = 1, …, m);

cj – прибыль от реализации единицы j-го продукта (j = 1, …, n)

Обозначим через xjпланируемое количество j-го продукта.

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

Математическая модель:

Найти план производства X = (x1, …, xn), максимизирующий суммарную прибыль



при условии что ресурсы, затраченные на производство продукции, не превышают запасов на складе

, i = 1, …, m

по смыслу задачи .

Данная модель является задачей линейного программирования, решать которую можно симплекс-методом (при n=2 можно использовать графический метод).

Задания:

  1. Составьте математическую модель задачи линейного программирования по исходным данным, где С = (с1, с2) – вектор прибыли, В = (b1, b2, b3)T–вектор запасов ресурсов, А – матрица затрат ресурсов на единицу продукции.

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

  3. Определите статус ресурсов. Для недефицитных ресурсов найдите остатки после выполнения оптимального плана.


Исходные данные по вариантам:

  1. А=, В=, С=.

  2. А=, В=, С=.

  3. А=, В=, С=(48 32).

  4. А=, В=, С=(30 45).

  5. А=, В=, С=(48 29).

  6. А=, В=, С=(28 20).

  7. А=, В=, С=(35 41).

  8. А=, В=, С=(38 28).

  9. А=, В=, С=(60 44).

  10. А=, В=, С=(59 35).

ЗАДАНИЕ 2. «Двойственная задача линейного программирования»
Для исходных данных задачи 1 составьте двойственную и объясните полученную модель.

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

→max

, i = 1, …, m

.

Запишем в матричном виде

Z(X)=C*X→max

AX≤B

X≥0
По исходной задаче составляем двойственную по правилам:

1). Тип экстремума меняется.

2). Каждому ограничению исходной задачи ставится в соответствие переменная двойственной задачи.

3). Свободные члены исходной задачи становятся коэффициентами при переменных в целевой функции двойственной задачи.

4). Каждый столбец коэффициентов в системе ограничений формирует ограничение двойственной задачи, при этом тип неравенства меняется; коэффициенты при переменных в целевой функции исходной задачи становятся свободными членами в соответствующих неравенствах двойственной задачи.

Получаем двойственную задачу:

G(Y)=Y*B→min

Y*A≥C

Y≥0
ЗАДАНИЕ 3. «Транспортная задача»

^ Формулировка транспортной задачи. Однородный продукт, сосредоточенный в mпунктах производства (хранения) в количествах a1,a2, …,amнеобходимо распределить между n пунктами потребления, которым необходимо соответственно b1, b2 , …, bn единиц продукта. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ыйпункт назначения равна Cij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными. Обозначим через xij количество груза, планируемого к перевозке от i-го поставщика j-ому потребителю. При наличии баланса производства и потребления:



математическая модель транспортной задачи будет выглядеть так:

найти план перевозок

X = (xij) i = 1, …, m,

j = 1, …,n


минимизирующий общую стоимость всех перевозок

Z =

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

, i=1,…,m

и спрос всех пунктов потребления удовлетворяется полностью

, j=1,…,n

причем по смыслу задачи

x11 ≥ 0, …, xmn ≥ 0

Для решения транспортной задачи чаще всего применяется метод потенциалов.

Задание:

Составить математическую модель транспортной задачи по исходным данным, где вектор объемов производства А(а1, …, аm), потребления B(b1, …, bn) и матрица транспортных издержек С = (Сij)кратко записаны в виде:





b1

b2



bn

a1

c11

c12



c1n











am

сm1

сm2



сmn


Если полученная модель окажется открытой, то свести ее к закрытой и найти оптимальное решение транспортной задачи методом потенциалов.
Исходные данные по вариантам


Вариант 1

Вариант 2

Вариант 3




45

60

21

24




36

32

40

53




48

75

41

32

50

3

6

3

1

40

2

3

4

1

90

4

1

3

1

70

6

2

1

6

60

4

2

1

2

75

4

1

3

2

40

10

3

5

7

70

2

7

7

1

40

5

2

3

5

Вариант 4

Вариант 5

Вариант 6




30

11

45

36




48

30

29

40




28

44

31

20

50

3

2

6

7

40

3

6

4

3

50

4

2

2

6

70

7

8

3

5

45

2

3

1

3

40

5

3

2

7

30

4

3

4

6

70

6

5

1

4

42

1

4

3

2

Вариант 7

Вариант 8

Вариант 9




35

41

52

32




38

42

28

41




60

32

44

57

70

2

2

3

2

60

3

2

4

3

50

3

2

4

1

80

4

1

5

2

50

5

3

1

4

90

4

6

5

2

47

6

4

6

3

48

4

3

6

1

60

9

4

10

6

Вариант 10










59

27

40

35































45

1

3

2

2































55

3

2

4

3































70

4

2

3

1
































^ Алгоритм решения транспортной задачи.




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

2). Построить начальное базисное решение любым методом, проверить правильность его построения по количеству загруженных клеток (их должно быть N=m+n-1 ).

3). Построить систему потенциалов, соответствующих базисному решению. Для этого решить систему уравненийαij=cijдля загруженных клеток ( xij› 0 ), положив один из потенциалов =0.

4). Проверить выполнение условия оптимальности для свободных клеток таблицы. Для этого вычислить оценки всех свободных клеток по формулам

ij = αij – cij.Найти максимальную оценку, т.е. max(ij)

А) если max(ij) отрицательно, то решение оптимально и единственно, вычислить значение целевой функции и закончить решение задачи;

Б) если max(ij) равно нулю, то решение оптимально, но не единственно; при необходимости можно найти другие оптимальные решения; вычислить значение целевой функции и закончить решение задачи;

В) если max(ij) больше нуля, то решение не оптимально.

5). Перейти к новому базисному решению, на котором значение целевой функции будет меньше. Для этого найти клетку таблицы (l,k) для которой ∆ik=max(ij). Построить цикл для клетки таблицы (l,k) и осуществить сдвиг по циклу(перераспределение груза) на величину Ɵ=min(xij) по разгружаемым клеткам. Клетка, в которой достигается минимум становится пустой. Если минимум достигается в нескольких клетках, то одна из них становится пустой, а в остальных проставляются базисные нули ( т.е. клетка считается загруженной), чтобы число загруженных клеток оставалось равным N.

6). Перейти к пункту 3) данного алгоритма.

Образец титульного листа
^

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ


ФИЛИАЛ ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

^ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ

ИМЕНИ В.С. ЧЕРНОМЫРДИНА»

В Г. ВОСКРЕСЕНСКЕ МОСКОВСКОЙ ОБЛАСТИ

(Филиал МГОУ имени В.С. Черномырдина в г. Воскресенске)


Кафедра «Прикладной математики»


КОНТРОЛЬНАЯ РАБОТА

Дисциплина: «Методы оптимальных решений»
Вариант № 5
Выполнил: студент 2 курса (заочная форма обучения)

Иванов С.П. (шифр 906548)
Направление подготовки: 080100 – «Экономика»
Проверил: ст. преподаватель Нидеккер И.А.

Воскресенск, 2013-2014

Похожие:

«Методы оптимальных решений» iconМетоды оптимальных решений
Теория: Принцип оптимальности, общая задача оптимального программирования. Получение оптимальных решений средствами ms excel
«Методы оптимальных решений» iconМетоды оптимальных решений, Часть 1 Учебно-методический комплекс...
Государственное образовательное учреждение высшего профессионального образования
«Методы оптимальных решений» iconМетодические указания и задания по курсу «методы оптимальных решений»
Методические указания и контрольные задания по курсу “Методы оптимальных решений” для студентов заочного факультетов. – Спб: Изд-во...
«Методы оптимальных решений» iconМетоды оптимальных решений

«Методы оптимальных решений» iconМетоды оптимальных решений
Составить модель расчета оптимальной производственной программы для этой фирмы на
«Методы оптимальных решений» iconКонтрольная работа по дисциплине «Методы оптимальных решений»
Номер варианта выбирается согласно порядковому номеру фамилии студента в списке группы!
«Методы оптимальных решений» iconКонтрольные задания по дисциплине «Методы оптимальных решений»
Вопрос Исходная задача линейного программирования имеет оптимальный план со значением целевой функции
«Методы оптимальных решений» iconМетоды оптимальных решений
Найти экстремум функции двух переменных методом конфигураций Хука-Дживса (критерием остановки алгоритма считать выполнение хотя бы...
«Методы оптимальных решений» iconМетоды оптимальных решений
Найти экстремум функции двух переменных методом деформируемого многогранника Нелдера-Мида (критерием остановки алгоритма считать...
«Методы оптимальных решений» icon«Методы оптимальных решений» Последний срок сдачи 21 час 00 минут 19 мая 2013 г
Цех производит два продукта (А и B), используя простую производственную линию, состоящую из трех машин

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница