- •Федеральное агенство по образованию
- •Введение
- •Общая задача оптимизации
- •1 Методические указания по решению злп в среде Exсel
- •1.1 Максимизация прибыли предприятия Постановка задачи
- •Решение
- •I этап: Составление математической модели
- •II этап: Решение задачи на эвм в среде ms Excel
- •III этап: Анализ решения задачи
- •1.2 Максимизация годового дохода Постановка задачи
- •Решение
- •I этап: Составление математической модели
- •II этап: Решение задачи на эвм в среде ms Excel
- •1.3 Специальные задачи линейного программирования
- •1.3.1 Задача целочисленного программирования
- •1.3.2 Транспортная задача Общая постановка транспортной задачи
- •Математическая модель транспортной задачи
- •1.3.2.1 Закрытая транспортная задача Минимизация стоимости перевозок кирпича
- •Решение
- •I этап: Составление математической модели
- •II этап: Решение задачи на эвм средствами пакета Excel
- •1.3.2.2 Открытая транспортная задача Постановка задачи
- •1.3.3 Задача о назначениях Постановка задачи
- •Решение
- •I этап: Составление математической модели
- •1.3.4 Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений.
- •Задача оптимального использования ресурсов.
- •Решение.
- •I этап: Составление математической модели прямой злп
- •II этап: Решение задачи на эвм в среде ms Excel
- •Ш этап: Составление математической модели двойственной злп
- •Анализ влияния изменения правых частей ограничений на значения целевой функции (чувствительность решения к изменению запасов сырья).
- •2. Вопросы для самоконтроля:
- •3. Варианты заданий для контрольной работы по дисциплине
- •4. Требования к оформлению контрольной работы
1.3 Специальные задачи линейного программирования
1.3.1 Задача целочисленного программирования
Решая Задачу 1.1 мы не учитывали того, что количество единиц продукции должно быть целым. Однако не всякую продукцию можно дробить на части.
Рассмотрим исходные данные Задачи 1.1 с тем условие, что в качестве продукции будут выступать ковры 4 – х видов:
Таблица 8
Тип ресурса |
Нормы затрат ресурса на один ковер |
Наличие ресурсов (ед.) | |||
1 |
2 |
3 |
4 | ||
Сырье |
3 |
5 |
2 |
4 |
60 |
Рабочее время |
22 |
14 |
18 |
30 |
400 |
Оборудование |
10 |
14 |
8 |
16 |
120 |
Прибыль (руб.) |
30 |
25 |
8 |
16 |
|
В данном случае, математическая модель аналогична математической модели Задачи 1, но добавляется новое условие xi – целые числа.
Таблица 9
Неизвестные | |
x1– количество ковров 1 -ого вида, x2 – – количество ковров 2 -ого вида, x3 – количество ковров 3 - его вида, x4 – количество ковров 4 -ого вида. | |
Целевая функция |
Ограничения |
Р=30*x1+25*x2+8*x3+16* x4 (руб.) |
3*x1+5*x2+2*x3+4*x460, 22*x1+14*x2+18*x3+30*x4400, 10*x1+14*x2+8*x3+16*x4120, xi0, i=1,2,3,4, xi – целые числа. |
Данное условие оформляется в окне Поиск решения следующим образом (см. рис. 21):
Рис.21 Добавление ограничения
Примечание: Для задач целочисленной оптимизации не предусмотрено вывода отчета по устойчивости.
1.3.2 Транспортная задача Общая постановка транспортной задачи
Пусть имеется m поставщиков у которых сосредоточен однородный груз в количествеединиц (), который требуется перевезтиn потребителям в количествеединиц (). Известна стоимость перевозки одной единицы груза отi поставщика к j потребителю, она задается матрицей
.
Составить такой план перевозок, при котором стоимость перевозок будет минимальной.
Математическая модель транспортной задачи
Обозначим - количество единиц груза, которое необходимо перевезти отi поставщика к j потребителю, тогда стоимость перевозки составит .
Стоимость перевозки всего плана выражается суммой
. (9)
Так как все грузы должны быть перевезены и все потребности должны быть удовлетворены, то получаем следующие ограничения:
(10)
(11)
(12)
Т.о. математическая модель транспортной задачи имеет следующий вид: требуется найти минимум функции (9) при ограничениях (10)-(12).
Теорема 1: Транспортная задача разрешима тогда и только тогда, когда , т.е. сумма запасов и потребностей совпадают.
В случае, если запасы превышают потребности, т.е. , то вводится фиктивный потребитель, потребность которого описывается формулой.
В случае, если потребности превышают запасы, т.е. , то вводится фиктивный поставщик, запасы которого описывается формулой.
Так как груз от фиктивного поставщика к фиктивному потребителю не перевозится, то стоимость перевозок полагается равной нулю .