Размещено на http://www.allbest.ru/

Введение

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

1. Задачи линейного программирования (с помощью средств ПОИСК решения в MS Excel, Mathcad, графический метод решения в Mathcad).

2. Транспортной задачи (с помощью средств ПОИСК решения в MS Excel, Mathcad).

3. Задачи о назначениях (с помощью средств MS Excel).

Задание 1. Задача линейного программирования

Используя «поиск решения» в среде MS Excel решим задачу оптимального использования ресурсов на «минимум» общей стоимости. Ресурсы сырья, норма его расхода на единицу продукции и цена продукции заданы в соответствующей таблице. В задаче требуется определить план выпуска продукции из условия минимизации ее стоимости.

Исходные данные

при ограничениях

Решение задачи в среде Excel

1. Вводим на лист MS Excel исходные данные, выделяем диапазон для искомого плана (ед. продукции 1-го и 2-го вида).

2. Описываем математическую модель задачи на языке формул, используя функцию СУММПРОИЗВ: вводим формулу для целевой функции и левой части неравенств.

Для нахождения искомых переменных (ед. продукции 1-го и 2-го вида) используя надстройку MS Excel Поиск решения (вкладка Данные, группы Анализ) выполняем следующее:

· указываем адрес ячейки целевой функции($C$13);

· устанавливаем переключатель на min(минимальное значение);

· добавляем полученные ограничения согласно исходным данным;

· в поле ввода изменяя ячейки вводим диапазон переменных x1 и x2 ($B$9: $C$9

В параметрах поиска решения устанавливаем checkbox на линейную модель.

Далее Ok, кнопка Выполнить;

Получили результат решения задачи

В результате произведенных вычислений мы нашли искомые переменные x1 и x2(ед. продукции первого и второго вида). Целевая функция при таких ограничениях будет стремиться к минимуму и равна -4.

Приведем отчет по результатам в MS Excel

Решение оптимизационной задачи линейного программирования в Mathcad

Таким образом, мы нашли исходные переменные x1=0, x2=4. Результат совпадает с MS Excel. Построим графическое решение задачи.

Графическое решение.

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

Используя «поиск решения» в среде MS Excel решим задачу оптимального плана перевозок продукции от поставщиков к потребителям на минимальные суммарные транспортные издержки. Мощность поставщиков, емкость потребителей и стоимость перевозки единицы продукции от каждого поставщика к каждому потребителю заданы в соответствующей таблице. В задаче требуется определить план перевозок продукции из условия минимизации суммарных транспортных издержек.

Исходные данные:

Заданы мощности поставщиков a(i), i=1..3, емкости потребителей b(j), j=1..3 и стоимости ni(j), i=1..3, j=1..3, перевозки ед. продукции от каждого поставщика каждому потребителю. Требуется найти план перевозок, обеспечивающий минимальные транспортные издержки. Данные представлены в таблице

Решение.

Проверяем модель на условие закрытости. Для этого находим суммы a(i) и b(j). Так как сумма a(i)=54, b(j)=70, то модель открытая. Вводим фиктивного поставщика, а стоимость поставки единицы груза равна 0

Обозначим через вектор X количество поставляемой продукции потребителю каждым поставщиком

X=(x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12)

Стоимость перевозки первым поставщиком первому потребителю будет равна 9x1. Суммарные транспортные издержки будут составлять функцию:

F(x)=9x1+8x2+4x3+8x4+7x5+3x6+4x7+3x8+2x9+0x10+0x11+0x12 (min);

Подсчитаем объем продукции поставляемый первому потребителю:

x1+x4+x7+x10=18;

При этом необходимо учитывать мощности первого поставщика:

x1+x2+x3<=32;

Окончательно:

x1+x4+x7+x10=18;

x2+x5+x8+x11=40;

x3+x6+x9+x12=12;

x1+x2+x3<=32

x4+x5+x6<=15

x7+x8+x9<=7

x10+x11+x12<=16

x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12 >=0

x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12 - цел.

Решение задачи в MS Excel:

· Вводим на листе MS Excel исходные данные (мощности поставщиков, емкости потребителей, стоимость перевозки ед. продукции от каждого поставщика каждому потребителю);

· Описываем математическую модель задачи на языке формул, используя функцию СУММПРОИЗВ: вводим формулу для целевой функции и левой части неравенства;

Для левой части неравенств в ячейки вводим соответственно формулы:

=СУММ(B9:B12);

=СУММ(C9:C12);

=СУММ(D9:D12);

=СУММ(B9:D9);

=СУММ(B10:D10);

=СУММ(B11:D11);

=СУММ(B12:D12);

Для целевой функции:

=СУММПРОИЗВ(B2:D5;B9:D12)

· Для нахождения оптимального соотношения объема поставки и стоимости поставки используя надстройку MS Excel Поиск решения (вкладка «Данные» группы «Анализ») выполняем следующие действия:

- устанавливаем адрес целевой ячейки ($E$14);

- включаем radiobutton на «минимальное значение»;

- устанавливаем диапазон изменяемых ячеек ($B$9:$D$12)

- вводим ограничения согласно исходным данным (кнопка «Добавить»);

- открываем диалоговое окно «Параметры поиска решения» (кнопка «Параметры»)

оптимальный задача excel решение

- включаем checkbox «Линейная модель» и «Неотрицательные значения»;

Далее OK, кнопка «Выполнить».

Получаем результат решения задачи

Таким образом, мы получили план перевозок следующего вида:

- первый поставщик должен поставить 32 ед. продукции второму потребителю;

- второй поставщик должен поставить 2 ед. продукции первому потребителю, 1 ед. продукции второму потребителю, 12 ед. продукции третьему потребителю;

- третий поставщик должен поставить 7 ед. продукции второму потребителю;

- четвертый поставщик должен поставить 16 ед. продукции первому потребителю;

Полученный план перевозок обеспечит минимальные суммарные транспортные издержки в размере 336 ед. стоимости.

Приведем отчет по результатам

Решение задачи в Mathcad

Следовательно, план перевозок получили следующего вида:

- первый поставщик должен поставить 20 ед. продукции второму потребителю, 12 ед. продукции третьему потребителю;

- второй поставщик должен поставить 15 ед. продукции второму потребителю;

- третий поставщик должен поставить 2 ед. продукции первому потребителю, 5 ед. продукции второму потребителю.

- четвертый поставщик должен поставить 16 ед. продукции первому потребителю;

Задание 3. Задача о назначениях

Имеются n рабочих и m видов работ. Стоимость Сij выполнения i-м рабочим j-й работы приведена в таблице, где рабочему соответствует строка, работе - столбец.

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

Решение.

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

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

Если i-м рабочим выполняется j-ая работа, то обозначим факт выполнения Xij=1 и Xij=0 если работа не выполняется. Тогда математическая модель задачи имеет вид

Задаем ограничения

Для решения задачи с помощью Поиск решения в MS Excel под неизвестные отведем диапазон B14:F18. В ячейку G20 введем значение целевой функции = СУММПРОИЗВ(B4:F8;B14:F18) - вычисляющую стоимость работ. Введем формулы задающие левые части ограничений

Используя надстройку MS Excel «Поиск решения» (инструмент для поиска и решения уравнений и задач оптимизации) на вкладке «Данные» группы «Анализ»

заполняем диалоговое окно

В диалоговом окне параметры Поиска решения включаем checkbox Линейная модель

Далее OK, кнопка Выполнить.

Получаем результат решения задачи

Таким образом, получаем оптимальный план работ где

1-й работник выполняет 4-ую работу;

2-й работник выполняет 5-ую работу;

3-й работник выполняет 1-ую работу;

4-й работник выполняет 2-ую работу;

5-й работник выполняет 3-ую работу;

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

Покажем полученный результат в отчете по результатам MS Excel

Заключение

На основании выполнения контрольной работы были изучены метаматематические модели задач линейного программирования, описаны методы их решения с использованием средств MS Excel и Mathcad.

Список использованных источников

1. Акулич И.Л.Математическое программирование в примерах и задачах. - М: Высш. шк. 1986. - 288 с.

2. Банди Б. Основы линейного программирования, - М.: Радио и связь, 1989

3. Балашевич В.А., Андронов А.М. Экономико-производственное моделирование производственных систем: Учеб. пособие. - Мн. Университетское,1995. - 240с.

4. Гарнаев Ю.А. «Использование MS Excel и VBA в экономике и финансах». Санкт-Петербург, 1999 - 336с.

5. Климович Ф.Ф., Присевок А.Ф. Математическое моделирование производственных задач в машиностроение. Учебно-методическое пособие по лабораторным работам для студентов машиностроительных специальностей высших учебных заведений, 2000 - 87с.

6. Костевич Л.С. Математическое программирование: Учеб. - практ. пособие. МН.: БГЭУ, 2003 - 203 с.

7. Тимковский В.Г. Дискретная математика в мире станков и деталей. М.: Наука, 1992. - 45с.

Размещено на Allbest.ru