Линейное программирование
Министерство
образования и науки Российской Федерации
Федеральное
государственное бюджетное образовательное учреждение
высшего
образования
«САМАРСКИЙ
ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Кафедра
«Экономика промышленности и производственный менеджмент»
Контрольная
работа
по
дисциплине
«Методы
исследования и моделирования экономики»
Раздел
«Линейное программирование»
Вариант
VIII
задача линейный транспортный оптимальный
Выполнил
студент
III-ЗФ-ХIБайбикова К.И.
Проверил
доцент Уманский
М.И.
Самара
2016
Оглавление
1. Задача 1.
Решение задачи линейного программирования
.1 Формы записи
общей задачи линейного программирования
.1.1 Исходные
данные
.1.2 Стандартная
форма записи ОЗЛП
.1.3 Каноническая
форма записи ОЗЛ
.2 Решение
задачи средствами MS Excel
.2.1 Порядок
решения задачи
.2.2 Запись
задачи на листе MS Excel
.2.3 Результаты
решения задачи
.
Задача 2. Решение транспортной задачи
.1
Математическая модель транспортной задачи
.1.1
Исходные данные
.1.2
Анализ условия задачи
.2
Решение транспортной задачи средствами MS Excel
Библиографический
список
1. Задача 1. Решение задачи линейного
программирования
В наиболее общей форме задачу линейного
программирования формулируют следующим образом:
Коэффициенты ai,j, bi, cj, j = 1, 2, ... , n, i
=1, 2, ... , m - любые действительные числа (возможно 0).
Решения, удовлетворяющие системе ограничений
(1.1) условий задачи и требованиям неотрицательности (1.2), называются
допустимыми, а решения, удовлетворяющие одновременно и требованиям минимизации
(максимизации) (1.3) целевой функции, - оптимальными.
.1 Формы записи общей задачи линейного
программирования
Одна и та же может быть сформулирована в
различных эквивалентных формах. Наиболее важными формами задачи линейного
программирования являются каноническая и стандартная.
В стандартной форме задача линейного
программирования является задачей на максимум (минимум) линейной целевой
функции. Система ограничений ее состоит из одних линейных неравенств типа «
<= » или « >= ». Все переменные задачи неотрицательны.
В канонической форме задача является задачей на
максимум (минимум) некоторой линейной функции F, ее система ограничений состоит
только из равенств (уравнений). При этом переменные задачи х1, х2, ..., хn
являются неотрицательными:
К канонической форме можно преобразовать любую
задачу линейного программирования.
.1.1 Исходные данные
Задача. Для изготовления трех видов продукции
предприятие использует два типа технологического оборудования и два вида сырья.
Нормы затрат сырья и времени на изготовление одного изделия каждого вида
приведены в таблице. В ней же указаны общий фонд рабочего времени каждой из
групп технологического оборудования, объемы имеющегося сырья каждого вида, а
также цена одного изделия данного вида.
|
Ресурсы
|
Нормы
затрат на 1 изделие вида
|
Общее
количество ресурсов
|
|
И1
|
И2
|
И3
|
|
|
Производительность
оборудования (норм/ч)
|
|
|
|
|
|
I
типа
|
2
|
-
|
4
|
200
|
|
II
типа
|
4
|
3
|
1
|
500
|
|
Сырье
(кг):
|
|
|
|
|
|
1
вида
|
10
|
15
|
20
|
1495
|
|
2
вида
|
20
|
25
|
4500
|
|
Цена
одного изделия (у. е.)
|
10
|
15
|
20
|
|
Составить такой план производства продукции,
согласно которому общая стоимость всей изготовляемой продукции будет максимальна.
Решение:
План выпуска продукции:- количество продукции 1
вида;- количество продукции 2 вида.- количество продукции 3 вида.
Выручка:
F(x1;
x2; x3)=10x1+15x2+20x3
max.;
Математическая модель производства продукции с
учетом ограничений:
.1.2 Стандартная форма записи ОЗЛП
Математическая модель задачи
записана в стандартной форме:
.1.3 Каноническая форма записи ОЗЛ
Математическая модель задачи может
быть записана в канонической форме:
.2 Решение задачи средствами MS
Excel
.2.1 Порядок решения задачи
На листе MS Excel необходимо
записать условия задачи, выделяя блоки ячеек с коэффициентами модели,
переменными модели, целевой функцией, ограничениями задачи;
необходимо вызвать надстройку Поиск
решения, в диалоговом окне указать адреса ячеек переменных, адрес целевой
функции и направление поиска (максимум/минимум), ввести ограничения задачи и
метод (!) ее решения;
при необходимости на вкладке
Параметры установить опцию Показывать результаты итераций;
задать команду Выполнить, команду
Сохранить найденное решение;
при необходимости выбрать тип
отчета. Ознакомиться с результатами решения.
.2.2 Запись задачи на листе MSExcel
На рисунке 1.1 показана форма
таблицы для записи исходных данных и выполнения вычислений в табличном
процессоре. На рисунке 1.2.приведено диалоговом окно настройки параметров окна
табличного процессора для отображения в ячейках всех формул.На рисунке
1.3показана копия окна с расчетными формулами в ячейках таблицы.
Рисунок 1.1
Рисунок 1.2
Рисунок 1.3
В диалоговом окне надстройки Поиск
решения(рисунок 1.4) необходимо указать:
адрес целевой ячейки (ячейки, в которой записано
выражение целевой функции);
условие поиска решения (Установить максимальное
значение);
диапазон ячеек переменных задачи;
ограничения в соответствии с математической
моделью задачи;
метод решения задачи.
Рисунок 1.4
По команде Выполнить будет найдено решение
задачи (рисунок 1.5), которое следует сохранить. Кроме того, можно выбрать тип
отчета (например, Результаты).
Рисунок 1.5
.2.3 Результаты решения задачи
На рисунке 1.6 приведены результаты решения
задачи.
Рисунок 1.6
Задача 2. Решение транспортной задачи
.1 Математическая модель транспортной задачи
Частным случаем задачи линейного
программирования является транспортная задача.
Транспортная задача в общем виде состоит в
определении оптимального плана перевозок некоторого однородного груза из m
пунктов отправления А1 , А2 , ..., Аm в n пунктов назначения B1 , B2 , ..., Bn.
В качестве критерия оптимальности можно взять минимальную стоимость перевозок
всего груза, либо минимальное время его доставки.
Рассмотрим задачу с первым критерием, обозначив
через сn тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт
назначения, через ai - запасы груза в пункте Аi,через bj - потребности в грузе
пункта Bj , xij - количество единиц груза, перевозимого из i-го пункта в j-й
пункт.
Составим математическую модель задачи с учетом
необходимости перевозки от i-гo поставщика к j-му потребителю xij единиц груза
(таблица рисунка 2.1).
|
Поставщики
|
Потребители
|
Запасы
|
|
B1
|
B2
|
...
|
Bn
|
|
|
А1
|
C11
X11
|
C12
X12
|
...
|
C1n
X1n
|
|
А2
|
C21
X21
|
C22
X22
|
...
|
C2n
X2n
|
a2
|
|
...
|
...
|
...
|
...
|
...
|
...
|
|
Аm
|
Cm1
Xm1
|
Cm2
Xm2
|
...
|
Cmn
Xmn
|
am
|
|
Потребности
|
b1
|
b2
|
...
|
bn
|
∑ai=∑bj
|
Таблица 2.1
Необходимо найти решение, обеспечивающее минимум
целевой функции
|
|
(2.1)
|
при ограничениях
|
|
(i
= l, ..., m),
|
(2.2)
|
|
|
(j
= 1, ..., n),
|
(2.3)
|
|
xij
≥ 0
|
(i
= l, ..., m; j = l, ..., n).
|
(2.4)
|
Если общее количество груза в пунктах
отправления и общая потребность в нем в пунктах назначения совпадают, т.е.
|
|
(2.5)
|
то модель ТЗ называется закрытой
(сбалансированной). В противном случае необходимо ввести дополнительные условия
- фиктивных поставщиков или фиктивных потребителей с параметрами, обеспечивающими
выполнение (2.5).
.1.1 Исходные данные
На складах 3 поставщиков А1,А2,А3 хранится
110,140,100 единиц одного и того же груза. Этот груз следует продать 4
потребителям В1,В2,В3,В4 заказы которых составляют 90,80,120,90ед. Стоимость
перевозок ед. груза указаны в таблице.
|
Поставщик
|
Потребитель
|
Запас
|
|
B1
|
B2
|
B3
|
B4
|
|
|
A1
|
7
|
5
|
4
|
3
|
110
|
|
A2
|
12
|
9
|
3
|
5
|
140
|
|
A3
|
4
|
6
|
3
|
2
|
100
|
|
Потребность
|
80
|
120
|
90
|
|
Составить такой план перевозок груза, при
котором общая стоимость перевозок груза была бы минимальной.
.1.2 Анализ условия задачи
Имеется три поставщика и три потребителя. Сумма
всех запасов
+80+120+90=380
не равна сумме всех заказов (потребностей)
+140+100=350
Условие (2.5) не выполняется. Необходимо
дополнить данные задачи фиктивным поставщиком с объемом запасов (380-350)=30
(ед.), соответствующие тарифы на перевозку следует полагать равными 0.
Фиктивного поставщика надо будет учесть в выражении целевой функции.
.2 Решение транспортной задачи средствами MS
Excel
На рисунке 2.2 приведена таблица исходных данных
для записи в табличном процессоре. (Где А4-Ф) - Фиктивный поставщик.
Рисунок 2.2
Таблица исходных данных и таблица, в которой
будут проведены вычисления, показаны на рисунке 2.3. Создать вычислительную
таблицу проще всего копированием / вставкой / редактированием таблицы исходных
данных.
Рисунок 2.3
В вычислительной таблице записаны необходимые
расчетные соотношения в соответствии с математической моделью транспортной задачи
(рисунок 2.4).
Рисунок 2.4
Для большей наглядности ячейкам (диапазонам
ячеек) присвоены содержательные имена. В диалоговом окне надстройки Поиск
решения установлены требуемые значения ссылок и записаны заданные моделью
ограничения (рисунок 2.5).
Рисунок 2.5
Необходимо указать метод решения задачи,
учитывая, что транспортная задача - частный случай задачи линейного
программирования.
По команде Выполнить будет найдено решение задачи
(рисунок 2.6), которое следует сохранить (рисунок 2.7). Кроме того, можно
выбрать тип отчета (например, Результаты).
Рисунок 2.6
Рисунок 2.7
На рисунке 2.8 показаны результаты решения
задачи в MSE xcel: таблица исходных данных и таблица результатов вычислений,
которые включают объемы перевозок от каждого из поставщиков потребителям и
суммарные затраты на перевозку.
Рисунок 2.8
Библиографический список
Попова
Н.В. Математические методы: Электронный
учебник.-http://matmetod-popova.narod.ru/Index.htm
АлесинскаяТ.В.
Учебное пособие по решению задач по курсу"Экономико-математические методы
и модели". Таганрог: Изд-во ТРТУ, 2002,153 с.<http://www.aup.ru/books/m84/>
Самаров
К.Л. Математика. Учебно-методическое пособие по курсу «Линейное
программирование». ООО «Резольвента», 2009. - www.resolventa.ru
Самаров
К.Л. Математика. Учебно-методическое пособие по курсу «Транспортная задача».
ООО «Резольвента», 2009. - www.resolventa.ru <http://www.resolventa.ru>