Решение задач линейным программированием
Решение задачи расчета структуры и объема товарооборота методом линейного программирования. Формулы ограничений, транспортная задача оптимизации доставки товаров. Решение задачи о назначениях на основе матрицы стоимостей в электронной таблице Excel.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 27.05.2013 |
| Размер файла | 1023,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Размещено на http://www.allbest.ru
Департамент образования города Москвы
Самарский филиал Государственного образовательного учреждения
высшего профессионального образования города Москвы
«Московский городской педагогический университет»
Факультет информатики
Кафедра высшей математики и информатики
Контрольная работа по дисциплине:
Компьютерное моделирование.
Студента 5 курса заочного отделения
Антонов С.Ю.
Проверил: Макарова И.С.
Самара 2012 г.
Задача №1. Решить задачу линейным программированием
Магазин реализует три группы товаров. Затраты ресурсов на тысячу рублей товарооборота даны в таблице.
|
Ресурсы |
Затраты на тысячу рублей товарооборота |
Имеющиеся ресурсы |
|||
|
(х1) 1 |
(х2) 2 |
(х3) 3 |
|||
|
А |
10 |
30 |
25 |
4400 |
|
|
В |
6 |
5 |
8 |
1180 |
|
|
С |
26 |
40 |
32 |
6420 |
|
|
Прибыль на тысячу рублей товарооборота, руб. |
60 |
90 |
80 |
||
Рассчитать структуру и объём товарооборота, обеспечивающих максимальную прибыль.
Составим систему ограничения:
10х1+30х2+25х3? 4400
6х1+5х2+8х3? 1180
26х1+40х2+32х30х8 ? 6420
линейное программирование excel
Составим целевую функцию задачи:
Z=60х1+90х2+80х3 max9
Условия не отрицательности задачи имеют вид: Х1, Х2,х3 ? 0.
Решение задачи в электронной таблице Excel:
Создаем форму и заполняем, вписывая переменные и формулы ограничения:
Заполняем окно поиска решений:
Выполняем команду в поиске решений: найти решение:
Решение найдено.
Задача №2. Решить транспортную задачу
На трёх хлебокомбинатах ежедневно производится 110, 190, и 90 т муки. Эта мука потребляется четырьмя хлебозаводами, ежедневные потребности которых равны соответственно 80, 60, 170, 80 т. Составить такой план доставки муки, при котором общая стоимость перевозок является минимальной, тарифы перевозок 1т муки с хлебокомбинатов к каждому из хлебозаводов задаются матрицей.
С=
Составляем транспортную таблицу:
|
хлебозавод |
I х/з 80 |
II х/з 60 |
III х/з 170 |
IV х/з 80 |
|||||
|
хлебокомбинат |
|||||||||
|
I х/к (110) |
80 |
8 |
30 |
1 |
9 |
7 |
|||
|
II х/к (190) |
4 |
30 |
6 |
160 |
2 |
12 |
|||
|
III х/к (90) |
3 |
5 |
10 |
8 |
80 |
9 |
Составим целевую функцию задачи:
Z=80*8+30*1+30*6+160*2+10*8+80*9=640+30+180+320+80+720=1970 д.е.
Решим транспортную задачу в электронной таблице Excel:
Заполняем окно поиска решений:
Выполняем команду в поиске решений: найти решение:
Решение найдено.
Задача №3. Решить задачу о назначениях
Назначить пятерых рабочих на пять должностей на основе матрицы стоимостей, приведенной ниже.
|
Должности |
|||||||
|
1 |
2 |
3 |
4 |
5 |
|||
|
1 |
14 |
15 |
19 |
18 |
17 |
||
|
Рабочие |
2 |
16 |
14 |
18 |
13 |
15 |
|
|
3 |
17 |
13 |
20 |
18 |
16 |
||
|
4 |
15 |
12 |
15 |
16 |
18 |
||
|
5 |
12 |
17 |
13 |
14 |
19 |
Решим задачу Венгерским методом:
|
должность кандидат |
Д I |
Д II |
Д III |
Д IV |
Д VI |
|
|
К I |
14 |
15 |
19 |
18 |
17 |
|
|
К II |
16 |
14 |
18 |
13 |
15 |
|
|
К III |
17 |
13 |
20 |
18 |
16 |
|
|
К IV |
15 |
12 |
15 |
16 |
18 |
|
|
К VI |
12 |
17 |
13 |
14 |
19 |
I этап (строчки, столбцы).
|
должность кандидат |
Д I |
Д II |
Д III |
Д IV |
Д VI |
|
|
К I |
0 |
1 |
5 |
4 |
3 |
|
|
К II |
3 |
1 |
5 |
0 |
2 |
|
|
К III |
4 |
0 |
7 |
5 |
3 |
|
|
К IV |
3 |
0 |
3 |
4 |
6 |
|
|
К VI |
0 |
5 |
1 |
2 |
7 |
|
должность кандидат |
Д I |
Д II |
Д III |
Д IV |
Д VI |
|
|
К I |
0 |
1 |
4 |
4 |
1 |
|
|
К II |
3 |
1 |
4 |
0 |
0 |
|
|
К III |
4 |
0 |
6 |
5 |
1 |
|
|
К IV |
3 |
0 |
2 |
4 |
4 |
|
|
К VI |
0 |
5 |
0 |
2 |
5 |
II этап. Построение решения.
|
должность кандидат |
Д I |
Д II |
Д III |
Д IV |
Д VI |
|
|
К I |
0 |
1 |
4 |
4 |
1 |
|
|
К II |
3 |
1 |
4 |
0 |
0 |
|
|
К III |
4 |
0 |
6 |
5 |
1 |
|
|
К IV |
3 |
0 |
2 |
4 |
4 |
|
|
К VI |
0 |
5 |
0 |
2 |
5 |
Количество выделенных нулей не совпадает с размерностью таблицы.
Переходим к III этапу.
III этап. Получение дополнительных нулей.
|
должность кандидат |
Д I |
Д II |
Д III |
Д IV |
Д VI |
|
|
К I |
0 |
1 |
4 |
4 |
1 |
|
|
К II |
3 |
1 |
4 |
0 |
0 |
|
|
К III |
4 |
0 |
6 |
5 |
1 |
|
|
К IV |
3 |
0 |
2 |
4 |
4 |
|
|
К VI |
0 |
5 |
0 |
2 |
5 |
Находим минимальное значение среди не зачеркнутых элементов
Min = 1
|
должность кандидат |
Д I |
Д II |
Д III |
Д IV |
Д VI |
|
|
К I |
0 |
2 |
4 |
4 |
1 |
|
|
К II |
3 |
2 |
4 |
0 |
0 |
|
|
К III |
3 |
0 |
5 |
4 |
0 |
|
|
К IV |
2 |
0 |
1 |
3 |
3 |
|
|
К VI |
0 |
6 |
0 |
2 |
5 |
Найденное решение не единственное.
Составим целевую функцию задачи: Z=14+13+16+12+13=68.
Решим задачу о назначениях в электронной таблице Excel:
Создаем форму и заполняем, вписывая переменные и формулы ограничения:
Заполняем окно поиска решений:
Выполняем команду в поиске решений: найти решение:
Задача решена.
Размещено на Allbest.ru
Подобные документы
Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Краткие сведения об электронных таблицах MS Excel. Решение задачи линейного программирования. Решение с помощью средств Microsoft Excel экономической оптимизационной задачи, на примере "транспортной задачи". Особенности оформления документа MS Word.
курсовая работа [1,1 M], добавлен 27.08.2012Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.
контрольная работа [191,1 K], добавлен 05.04.2016Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.
контрольная работа [2,0 M], добавлен 02.05.2012Нахождение минимума целевой функции для системы ограничений, заданной многоугольником. Графическое решение задачи линейного программирования. Решение задачи линейного программирования с использованием таблицы и методом отыскания допустимого решения.
курсовая работа [511,9 K], добавлен 20.07.2012Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.
реферат [157,5 K], добавлен 21.08.2008Расчеты по таблице перевозок грузов между отдельными регионами. Решение задачи управления процессами перевозок в среде Pascal. Решение задачи средствами MS Excel. Исходные данные и итоги по строкам и столбцам. Решение задачи средствами MATHCAD.
курсовая работа [1,8 M], добавлен 25.03.2015
