Курсовая работа: Решение задач линейного программирования

Это оптимизационная задача, при которой одновременно с установлением объема производства на отдельных предприятиях определяется и оптимальная схема размещения заказов (т. е. прикрепления поставщиков к потребителям). Она имеет особое значение для так называемых многотоннажных производств, где важен транспортный фактор (например, черные металлы, минеральные удобрения, нефтепереработка).

Такие задачи математически могут быть представлены в двух видах: в сетевой и в матричной постановке. Будучи основанными на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов.

3. Решение задач

3.1. Решение задачи линейного программирования

3.1.1.Постановка задачи

Сформулируем задачу: Определить значения переменных, обеспечивающие минимизацию целевой функции.

Составим целевую функцию и зададим ограничения.

Пусть Х1, Х2, Х3, Х4, Х5 – неизвестные переменные

Целевая функция: L(Х) = 14 х-9 х₂ - х₄ +6,4 х₅ —> min;

Ограничения: g ₁ : 0,9 х + 10 х₂ -28х₄ +5х₅ 245,

g ₂ : 0,8 х+ 1,7х₂ -0,2х₃ -0,5х₄ =9,

g ₃ : 6 х + 4х₃ - 7х₄ + 6,3х₅ 54,

g ₄ : 8 х+6,2х₂ -4,8х₄ +2,9х₅ 17,

3.1.2.Ввод данных

1. Введем на рабочий лист Excel необходимые данные. В ячейке В5 запишем выражение целевой функции, а в ячейках В8:В11– левые части ограничений.

2.Командой Сервис, Поиск решения откройем диалоговое окно ²Поиск решения² (рис. 2) и заполним его данными. В поле Установить целевую ячейку введем адрес целевой функции $В$5, в поле Изменяя ячейки - адреса $B$3:$E$3. Переведите переключатель Равной в положение минимальному значению.

Чтобы ввести ограничения в окне ²Поиск решения² нажмем кнопку Добавить и на экране появится диалоговое окно ²Добавление ограничения² .

3. Начнем с первого ограничения. Установим курсор в поле Ссылка на ячейку и, выделяя на листе (рис.1) ячейку В8, введем ее адрес $B$8 в это поле.

Кнопкой-стрелкой откроем список и выберем в нем знак <=. В поле Ограничение установите курсор и, выделяя на листе ячейку D8, введем ее адрес $ D $8 в это поле и нажмем кнопку Добавить.

4. Повторим действия п.3 и введем остальные ограничения $В$9=$D$9, $В$10<=$D$10, $В$11>=$D$11, реализующие граничные условия. После ввода последнего ограничения $F$11<=$H$11 вместо кнопки Добавить нажмем кнопку ОК.

Таким образом, в окно ²Поиск решения² (рис. 2) будут введены ограничения.

3.1.3. Решение задачи

1. Для задания необходимых параметров оптимизации нажатием кнопки Параметры откроем окно ²Параметры поиска решения² (рис.4).

В этом окне оставьте неизменными установленные по умолчанию Максимальное время: 100 сек, выделяемое на поиск решения (возможно до 9 часов), Предельное число итераций: 100, Относительная погрешность: 0,000001, Допустимое отклонение: 5%, переключатели в положении линейная, прямые, Ньютона.