Расчет стоимости транспортных перевозок

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

1. Решение задач транспортного типа

Ситуация №1

Компанией разрабатывается план обеспечения потребителей горюче-смазочными материалами. Исходные данные о запасах ГСМ в хранилищах, заявках на ГСМ в центрах распределения и стоимости перевозки 1 т ГСМ от хранилищ к центрам распределения представлены в нижеследующей таблице:

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

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

Данная задача является сбалансированной, т.к. суммарный объем производства равен суммарному объему потребления:

где m - количество хранилищ;

n - количество центров распределения;

a_i - количество (объем ) груза в i-м исходном пункте

b_j - количество (объем) груза, которое должно быть завезено в j-й пункт назначения.

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

где x_ij - искомые переменные задачи - количество (объем) груза, которое должно быть перевезено с i-го исходного пункта в j-й пункт назначения.

Так как количество перевозимого груза не может принимать отрицательные значения, то в рассматриваемой задаче имеет место условие неотрицательности, т. е.: x_ij ? 0

Целевая функция имеет вид:

где c_ij - стоимость перевозки 1 т ГСМ с i -го исходного пункта в j-ый пункт назначения.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.



Вывод: рассчитанный план перевозок является оптимальным. При данном решении стоимость перевозки является минимальной и равно 4250 у.е.

Ситуация №2

Увеличим потребности в ГСМ у первого центра до 500 тонн, а у второго центра до 650 тонн.

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



остается без изменения, т.е. все запасы будут вывезены, а вот

изменится на

т.е. потребности будут удовлетворены не в полном объеме.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

Вывод: таким образом мы видим, что все запасы из всех хранилищ вывезены, и Центр1, Центр4, Центр5 удовлетворены в ГСМ в полном объеме, а в Центр2 и Центр3 ГСМ недопоставлены в размере 250 и 50 тонн соответственно.



Ситуация №3

Поступило указание обеспечить Центр2 в полном объеме.

Для этого необходимо изменить знак “?” Центра2 на знак “=” и ввести дополнительное ограничение (уравнять левую и правую части) Центра2.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

Вывод: таким образом, в Центр3 ГСМ вообще не доставляются, а Центр2 удовлетворен в полном объеме.

Ситуация №4

Поступило указание обеспечить Центр3 не менее чем на 85% от его потребностей. В математической интерпретации это указание запишется как b₃ ? 212,5.

С учетом ранее имеющегося ограничения на потребность ГСМ в Центре3 будем иметь, что 212,5 ? b₃ ? 250.

И добавим ограничение: b₃ ? 212,5.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

Вывод: таким образом Центр3 обеспечен не мене, чем на 85% от его потребностей. все запасы из всех хранилищ вывезены и Центр2, Центр4 и Центр5 удовлетворены в ГСМ в полном объеме.

Ситуация №5

Необходимо заблокировать перевозку по маршруту Хранилище2 - Центр3.

В математической интерпретации это запишется в виде ограничения х₂₃ = 0. Либо “искусственным” способом задания блокировки является назначение большой стоимости перевозки блокируемому маршруту, например, c₃₁ = 1000.

Используем первый способ для блокировки маршрута Хранилище2 - Центр3, для чего в диалоговом окне Поиск решения введем ограничение D13=0. Второй способ используем для блокирования маршрута Хранилище3 - Центр1, для чего в ячейку В5 введем относительно большое число, например, 1000.

Решение представлено в следующей таблице:



Ситуация №6

Между Хранилищем4 и Центром1 заключен договор на поставку 300 т ГСМ, а между Хранилищем1 и Центром4 - на поставку 100 т ГСМ.

Для этого в ограничениях нужно добавить : В15 = 300, Е12 = 100.

Решение представлено в следующей таблице:

Ситуация №7

Рассмотрим схему “справедливой” недопоставки в условиях дефицита, для чего обратимся к модели, представленной ниже:

Как видим, недопоставка коснулась только двух центров - Центра2 и Центра3. Самым простым решением в этом случае является равномерная недопоставка ГСМ во все пять центров. При дефиците в 400 т (400 = 1750-1350) она будет составлять 80 тонн ГСМ для каждого центра. Однако такое решение будет несправедливым.

Существует подход к пропорциональному распределению ресурсов:

рассчитаем коэффициент обеспеченности:

корректировка потребностей осуществляется в соответствии с формулой

,

где - новое значение спроса в j-м центре;

- старое значение спроса в j-м центре.

Рассчитаем новые значения. При этом заметим, что задача из несбалансированной вновь превращается в сбалансированную.

После внесения необходимых изменений на рабочем листе и в диалоговом окне Поиск решения запускаем процедуру поиска. Решение задачи представлено ниже:

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

Ситуация №8

Наряду с “дефицитной” постановкой задачи возможна и противоположная ей “избыточная” постановка, т.е. когда выполняется условие

Исходные данные для такой задачи представлены ниже:



Как видим

т.е. наблюдается избыток запасов ГСМ -

В данной ситуации потребности центров будут удовлетворены в полном объеме, т.е. имеет место ограничение

В то же время запасы ГСМ будут вывезены их хранилищ не в полном объеме, т.е. имеет место ограничение

Решение задачи представлено ниже:

Вывод: как видим, наблюдается избыток запасов ГМС. В данной ситуации потребности центров будут удовлетворены в полном объеме, в тоже время запасы их хранилищ будут вывезены не в полном объеме.

Ситуация №9

Предположим, что поступила следующая информация:

а) Хранилище З ликвидируется, поэтому запасы ГСМ должны быть вывезены из него в полном объеме;

Решение задачи представлено ниже:

Вывод: таким образом, из Хранилища 3 будет вывезен полный объем запасов. Минимальная сумма перевозки составит 5300,00 ден.ед.

б) мост по дороге от Хранилища2 к ЦентруЗ закрыт на реконструкцию, поэтому необходимо запретить перевозку по указанному маршруту.

Для этого в Поиске решения клетку пересечения Хранилища 2 и Центра 3 приравняем к 0.

Решение задачи представлено ниже:



Вывод: получаем, что перевозка от Хранилища 2 к Центру 3 будет запрещена. Минимальная стоимость перевозки составит 6300 ден.ед.

Ситуация №10

Предположим, что неприкосновенный (неснижаемый запас) в Хранилише2 составляет 300 тонн. Тогда при емкости в 400 тонн из него в пределе может быть вывезено 100 тонн ГСМ.

Решение задачи представлено ниже:

Вывод: таким образом, из Хранилища 2 возможно вывести максимальную массу это 100 тонн. Минимальная стоимость перевозки составит 6450 ден.ед.

Вариант №7

Разрабатывается план обеспечения потребителей горюче-смазочными материалами. Предложите такой план доставки ГСМ от складов к центрам распределения, чтобы общая стоимость перевозок была минимальной.

Исходные данные для решения задачи:

Склады ГСМ	Центры распределения	Запасы ГСМ на складах, т
	Центр1	Центр2	Центр3	Центр4	Центр5
Склад1	4	6	7	9	1	150
Склад2	6	4	1	2	2	200
Склад3	5	8	7	4	9	450
Склад4	2	3	8	5	7	350
Потребность в ГСМ, т	500	400	250	100	250		1500
						1150

коэффициент формула перевозка стоимость

Вам поступила информация:

что Центр №3 и Центр №1 должны быть обеспечены ГСМ в полном объеме;

что дорога между Складом №3 и Центром №3 перекрыта на время ликвидации стихийного бедствия (запретите перевозку по указанному маршруту).

Целевая функция:

где х_i,j - объем груза, которое должно быть перевезено с i-ого исходного пункта в j-ый пункт назначения;

с_i,j - стоимость перевозки одной единицы грузов.

В данной задаче m=4, n=5.

Получим несбалансированную задачу, т.е. спрос превышает предложение. Следовательно возникает ситуация дефицита.

Составляем ограничения на удовлетворение потребностей на всех пунктах потребления:

и ограничения на возможности вывоза запасов со всех пунктов производства:

т.к. Центр №3 и Центр №1 должен быть обеспечен ГСМ в полном объеме, то левую часть(завезено) приравниваем к правой части;

дорога между Складом №3 и Центром №3 перекрыта на время ликвидации стихийного бедствия, то запрещаем перевозку по указанному маршруту, добавляя в ограничения D18=0.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.



Вывод: Таким образом, Центр1 и Центр3 удовлетворен в потребностях в полном объеме и перевозка по дороге от Склада №3 к Центру №3 запрещена, при этом все запасы вывезены со складов в полном объеме. Минимальная стоимость перевозок составляет 3650 ден. ед.

2) Вам поступило указание обеспечить горюче-смазочными материалами Центр №2 не менее чем на 60% от потребностей. . Задайте требуемые ограничения любым известным Вам способом, но при этом ограничения от прежних условий остаются.

Рассчитываем 60% от потребностей Центра2.

Для Центра2: 400*0,6 = 240

В систему ограничений добавляем: С20 ? 240.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.



Вывод: таким образом,Центр2 обеспечен горюче-смазочными материалами не менее чем на 60% от их потребностей. Минимальная стоимость перевозок при этом составляет 3780 ден. ед.

3) Обеспечьте пропорциональное распределение ГСМ между Центром №2, Центром №4 и Центром №5, для чего недостающий объем ГСМ недопоставьте в указанные центры в соответствии с их долями в суммарном объеме их потребностей. Модифицируйте модель задачи и измените соответствующие значения потребностей в графе «Прав. часть (потребн.)», но при этом ограничения от первой ситуации задачи остаются прежними.



Получили несбалансированную задачу, т.е. спрос превышает предложение. Следовательно возникает ситуация дефицита.

Рассчитали недостаток в ячейке I10(1500-1150=350).

В ячейке H11 рассчитана суммарная потребность Центров 2,4 и 5, равная 750.

В ячейке J10 рассчитана разность между суммарной потребностью Центров 2,4,5 и недостатком, т.е. J10 = H11-I10 = 400.

В ячейках C11,E11 и F11 рассчитаны коэффициенты как отношения потребностей каждого Центра 2,4,5 к суммарной потребности Центров 2,4 и 5.

Ячейки C22,E22 и F22 рассчитаны как произведение ячейки J10 (разность между суммарной потребностью Центров 2,4,5) на соответствующие коэффициенты центров 2,4,5.

Вывод: таким образом мы обеспечили пропорциональное распределение ГСМ между Центром №2, Центром №4 и Центром 5 для чего недостающий объем ГСМ недопоставили в указанные центры в соответствии с их долями в суммарном объеме их потребностей. Центр №1 и Центр№3 удовлетворены в потребностях в полном объеме из предыдущих условий задачи. Минимальная стоимость перевозок при этом составляет 3760 ден. ед.

Задача № 1763 ( из задачника)

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

На двух складах А и В находится по 90 т горючего. Перевозка одной тонны горючего со склада А в пункты 1, 2, 3 соответственно стоит 1, 3, и 5 ден. ед., а перевозка одной тонны со склада В в те же пункты - соответственно 2, 5 и 4 ден. ед. В каждый пункт нужно доставить по одинаковому количеству тонн горючего. Составить такой план перевозки горючего, при котором транспортные расходы будут наименьшими.

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

Целевая функция:

где х_i,j - объем груза, которое должно быть перевезено с i-ого исходного пункта в j-ый пункт назначения;

с_i,j - стоимость перевозки одной единицы грузов.

В данной задаче m=2, n=3.

Составляем ограничения на удовлетворение потребностей на всех пунктах потребления:

и ограничения на возможности вывоза запасов со всех пунктов производства:

Данная задача является сбалансированной, т.к. суммарный объем производства равен суммарному объему потребления:

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

Вывод: таким образом в каждый пункт доставлено по одинаковому количеству тонн горючего: 90 т из цеха А на склады № 1 и № 2, 90 т - из цеха В на склады № 1 и № 3. Минимальная стоимость перевозок составила 510 ден. ед.



Задача № 1764 ( из задачника)

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

В резерве трех железнодорожных станций А, В и С находятся соответственно 60, 80 и 100 вагонов. Составить оптимальный план перегона этих вагонов к четырем пунктам погрузки хлеба, если пункту №1 необходимо 40 вагонов, №2 - 60 вагонов, №3 - 80 вагонов и №4 - 60 вагонов. Стоимости перегонов одного вагона со станции А в указанные пункты соответственно равны 1, 2, 3, 4 ден. ед., со станции В - 4, 3, 2, 0 ден.ед. и со станции С - 0, 2, 2, 1 ден. ед.

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

Целевая функция:

где х_i,j - число вагонов, которое должно быть перевезено с i-ого исходного пункта в j-ый пункт назначения;

с_i,j - стоимость перевозки одной единицы грузов.

В данной задаче m=3, n=4.

Составляем ограничения на удовлетворение потребностей на всех пунктах потребления:

и ограничения на возможности вывоза запасов со всех пунктов производства:

Данная задача является сбалансированной, т.к. суммарный объем производства равен суммарному объему потребления:

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

Вывод: таким образом оптимальное решение задачи предполагает перевозку 60 вагонов со станции А в пункт погрузки хлеба № 2, 80 вагонов - со станции В в пункт погрузки хлеба № 3 и № 4 и 100 вагонов - со станции С в пункт погрузки хлеба №1 и № 3. Минимальная стоимость перевозок составляет 280 ден. ед.



Задача № 1766 ( из задачника)

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

На трех складах А, В, С находится сортовое зерно соответственно 10, 15, 25 т, которое надо доставить в 4 пункта: пункту №1 - 5 т, №2 - 10 т, №3 - 20 т и №4 - 15 т. Стоимость доставки одной тонны со склада А в указанные пункты соответственно равны 8, 3, 5, 2 ден. ед.; со склада В - 4, 1, 6, 7 ден. ед.; и со склада С - 1, 9, 4, 3 ден. ед. Составить оптимальный план перевозки зерна в четыре пункта, минимизирующий стоимость перевозок.

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

Целевая функция:

где х_i,j - количество тонн, которое должно быть перевезено с i-ого исходного пункта в j-ый пункт назначения;

с_i,j - стоимость перевозки одной тонны зерна

В данной задаче m=3, n=4.

Составляем ограничения на удовлетворение потребностей на всех пунктах потребления:



и ограничения на возможности вывоза запасов со всех пунктов производства:

Данная задача является сбалансированной, т.к. суммарный объем производства равен суммарному объему потребления:

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

Вывод: таким образом оптимальное решение задачи предполагает перевозку 10 тонн из цеха А в пункты № 1 и № 2, 15 тонн - из цеха В на склад № 4, 25 тонн - из цеха С на склады № 2 и №3. Минимальная стоимость перевозок составила 285 ден. ед.

Задача № 1765

Завод имеет три цеха А, В, С и четыре склада № 1, 2, 3, 4. Цех А производит 30 тыс. шт. изделий, цех В - 40 тыс. шт., цех С - 20 тыс. шт. Пропускная способность складов за то же время характеризуется следующими показателями: склад №1 - 20 тыс. шт., склад №2 - 30 тыс. шт., склад №3 - 30 тыс. шт., склад №4 - 10 тыс. шт. Стоимость перевозки 1 тыс. шт. изделий из цеха А в склады № 1, 2, 3, 4 соответственно равны 2, 3, 2, 4 ден. ед., из цеха В - 3, 2, 5, 1 ден. ед., а из цеха С - 4, 3, 2, 6 ден. ед. Составить такой план перевозки изделий, при котором расходы на перевозку 90 тыс. шт. изделий были бы наименьшими.

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

Целевая функция:

где х_i,j - объем груза, которое должно быть перевезено с i-ого исходного пункта в j-ый пункт назначения;

с_i,j - стоимость перевозки одной единицы грузов.

В данной задаче m=3, n=4.

Составляем ограничения на удовлетворение потребностей на всех пунктах потребления:



и ограничения на возможности вывоза запасов со всех пунктов производства:

Данная задача является сбалансированной, т.к. суммарный объем производства равен суммарному объему потребления:

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

Вывод: таким образом оптимальное решение задачи предполагает перевозку 30 тыс. шт. из цеха А на склады № 1 и № 3, 40 тыс. шт. - из цеха В на склады № 2 и № 4 и 20 тыс. шт. - из цеха С на склад №3. Минимальная стоимость перевозок составляет 170 ден. Ед.

Транспортная задача

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

4 предприятия для производства продукции использует некоторое сырье. Спрос на сырье каждого из предприятия соответственно составляет 120, 50, 190, 110 у.е. Сырте сосредоточено в 3 - х местах. Предложение поставщиков сырья = 160, 140, 170 у.е. На каждое предприятие сырье может завозиться от любого поставщика. Найти оптимальный план перевозок. Тарифы представлены в таблице:

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

Целевая функция:

где х_i,j - объем сырья, которое должно быть перевезено с i-ого исходного пункта в j-ый пункт назначения;

с_i,j - стоимость перевозки одной единицы грузов.

В данной задаче m=3, n=4.

Составляем ограничения на удовлетворение потребностей на всех пунктах потребления:

и ограничения на возможности вывоза запасов со всех пунктов производства:



Данная задача является сбалансированной, т.к. суммарный объем производства равен суммарному объему потребления:

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

Вывод: таким образом оптимальное решение задачи предполагает перевозку 160 у.е. из места А предприятиям № 3 и № 4, 140 у.е. - из места В предприятиям № 1 и № 2 и 170 у.е. - из места С предприятиям №3 и №4. Все потребности 4-х предприятий удовлетворены в полном объеме. Минимальная стоимость перевозок при этом составит 1330 ден.ед.



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

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

В регионе располагаются хранилища ГСМ и центры их распределения. Доставка ГСМ от хранилищ к центрам распределения осуществляется периодически или по заявкам автомобильным транспортом. Исходные данные о емкости хранилищ и центров распределения, а также о среднем времени доставки ГСМ от хранилищ к центрам распределения представлены в нижеследующей таблице:

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

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

Затраты с_ij будут соответствовать времени доставки ГСМ от хранилищ к центрам распределения t_ij. Отличие рассматриваемой задачи от классической задачи о назначениях состоит в том, что к одному хранилищу может быть прикреплено несколько центров распределения, но при этом центр распределения может быть прикреплен только к одному хранилищу.

Для построения математической модели введем следующие обозначения:

V _i^ц - емкость i-го центра, i = 1,...,т;

V_j^x - емкость j-го хранилища, j = 1,...,n;

t_ij - среднее время движения автомобильного транспорта от i-го центра распределения к j-му хранилищу;

Так как i-й центр распределения может быть прикреплен только к одному j-му хранилищу, то будем иметь:

Так как к j-му хранилищу может быть прикреплено несколько i-х центров распределения, то будем иметь:

Целевая функция будет иметь вид:

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.



Вывод: таким образом, оптимальный план прикрепления состоит в следующем: Хранилище 1 обслуживает Центр1, Центр3 и Центр7, Хранилище2 - Центр2 и Центр9, Хранилище3 - Центр4, Центр6 Центр 10, Хранилище4 - Центр5 и Центр8. При таком плане общее время разовой доставки ГСМ от хранилищ к центрам распределения составит 6,9 часа.

2.2 Задача про ученых

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

Институт получил гранты на выполнение 4-х исследовательских проектов. Выходные результаты 1-го проекта является входными данными для 2-го проекта, выходные результаты 2-го проекта - входные данные для 3-го проекта. Результаты 3-го проекта используются для работы над 4-м проектом. В качестве научных руководителей проектов рассматриваются кандидатуры 4-х ученых, обладающих различным опытом и способностями. Каждый ученый оценил время, необходимое ему для реализации проекта. Продолжительность времени задана в месяцах. Требуется выбрать научного руководителя для выполнения каждого проекта так, чтобы суммарное время выполнения всех проектов было минимальным. Данные представлены в следующей таблице:

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

Целевая функция:

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

Вывод: таким образом, мы видим, что первый ученый будет научным руководителем первого проекта, второй ученый - четвертого проекта, третий ученый - третьего проекта, четвертый ученый - второго проекта. Минимальное суммарное время выполнения всех проектов составляет 17 месяцев.

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

3.1 Задача про затоваривание

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

Предприятие производит изделия трех видов, поставляет их заказчикам и реализует на рынке. Заказчикам требуется 1000 изделий первого вида, 2000 изделий второго вида и 2500 изделий третьего вида. Условия спроса на рынке ограничивают число изделий первого вида 2000 единицами, второго - 3000 и третьего - 5000 единицами. Для изготовления изделий используются 4 типа ресурсов. Количество ресурсов, потребляемых для производства одного изделия, общее количество ресурсов и прибыль от реализации одного изделия каждого вида заданы в табл.. Как организовать производство, чтобы:1) обеспечить заказчиков; 2) не допустить затоваривания; 4)получить максимальную прибыль?

Тип ресурсов	Вид изделий	Всего ресурсов
	1	2	3
1	500	300	1000	25000000
2	1000	200	100	30000000
3	150	300	200	20000000
4	100	200	400	40000000
Прибыль	20	40	50

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

Целевая функция:

f=20x₁+40x₂+50x₃ max,

где х₁- число изделий первого вида,

х₂ - число изделий второго вида,

х₃ - число изделий третьего вида,

f - максимальная прибыль предприятия от реализации товара.

Система ограничений:

х₁ ? 1000

х₂ ? 2000

х₃ ? 2500

х₁ ? 2000

х₂ ? 3000

х₃ ? 5000

500х₁+ 300х₂ + 1000х ? 25000000

1000х₁ + 200х₂ + 100х₃ ? 30000000

150х₁ + 300х₂ + 200х₃ ? 20000000

100х₁ + 200х₂ + 400х₃ ? 40000000

х_1, х_2, х_{3 -} имеют неотрицательные значения, и модель является линейной.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

x₁=2000,

x₂=3000,

x₃=5000.



f= 410000

Вывод: для того, чтобы получить максимальную прибыль f=410000, обеспечить заказчиков и не допустить затоваривания , необходимо произвести 2000 изделий первого вида(х₁), 3000 изделий второго вида (х₂), и 5000 изделий третьего вида (х₃).

3.2 Задача про мороженое

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

Предприятие выпускает сливочное и шоколадное мороженое. Для изготовления мороженого используются молоко и наполнители, расходы которых на 1 кг мороженого приведены в табл.. Маркетинговые исследования показали, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого равна 46 руб, шоколадного - 48 руб. Какое количество мороженого каждого вида должно производиться, чтобы доход от его реализации был максимальным?

Исходный продукт	Расход исходного продукта на 1 кг мороженого	Запас, кг
	Сливочное	Шоколадное
Молоко	0,8	0,5	400
Наполнители	0,4	0,8	365

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

Целевая функция:

f=46x₁+48x₂ max,



где х₁- необходимое количество сливочного мороженого,

х₂ - необходимое количество шоколадного мороженого,

f - максимальная прибыль предприятия от реализации товара.

Система ограничений:

0,8х₁ + 0,5х₂ ? 400

0,4х₁ + 0,8х₂ ? 365

х₁-х₂ ? 100

х₂ ? 350

х₁ ? 0

х₂ ? 0

Модель является линейной.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

x₁=312,5,

x₂=300.

f=28775

Вывод: для того, чтобы получить максимальную прибыль f=28775, необходимо производить 312,5 кг сливочного мороженого и 300 кг шоколадного мороженого.

3.3 Задача про банки

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

Пусть собственные средства банка в сумме с депозитами составляет 100 млн. руб. Эти средства банк может разместить в кредиты по ставке r₁ и в государственные ценные бумаги по ставке r₂ . Так как кредиты менее ликвидны по сравнению с ценными бумагами, то r₁>r₂. Банк обязан не менее 35 % от суммы в 100 млн. руб. разместить в кредитах. Ликвидное ограничение состоит в том, что ценные бумаги должны составлять не менее 30 % средств размещенных в кредитах и ценных бумагах. Определить такое размещение средств в кредиты и ценные бумаги, при котором прибыль банка будет максимальной (r₁ =18%, r₂ =12%) .

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

Целевая функция:

f= 0.18x₁+0.12x₂ max,

где х₁- собственные средства банка,

х₂ - депозиты,

f - максимальная прибыль предприятия от реализации товара.

Система ограничений:

х₁+х₂ ? 100

х₂ ? 35

х₂ ? 0,3(х₁+х₂)

х₁ ? 0

х₂ ? 0

Модель является линейной.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

x₁=70,

x₂=30.

f=16

Вывод: для того, чтобы получить максимальную прибыль f=16, необходимо 70 млн. руб. собственных средств банка разместить в кредитах и 30 млн. руб. депозитов разместить в ценных бумагах.

3.4 Задача про поезда

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

Из Москвы в Санкт-Петербург ежедневно отправляются скорые и пассажирские поезда. Наличный парк вагонов разных типов, из которых ежедневно можно комплектовать данные поезда, и число пассажиров, вмещающихся в каждом из вагонов, приведены в таблице.

Определить:

1) количество скорых и пассажирских поездов, при которых число перевозимых пассажиров достигает максимума;

2) оптимальное количество поездов для случая, когда железная дорога не может пропустить более шести пассажирских поездов.

вагон	число вагонов в поезде	число пассажиров	парк вагонов
	скором	пассажирском
почтовый	1	-	-	8
плацкартный	5	8	58	81
купированный	6	4	40	70
мягкий	3	1	32	26
багажный	1	1	-	12

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

Целевая функция:

f=(5*58+6*40+3*32)*x₁ + (8*58+40*40+1*32)*x₂ max,

где х₁- количество скорых поездов,

х₂ - количество пассажирских поездов,

f - число перевозимых пассажиров.

1) Система ограничений:

5х₁+8х₂ ? 81

6х₁+4х₂ ? 70

3х₁+х₂ ? 26

х₁ ? 0

х₂ ? 0

Модель является линейной.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

x₁=5,

x₂=7.

f=7722

Вывод: для того, чтобы число перевозимых пассажиров достигало максимума f=7722, необходимо 5 скорых поездов и 7 пассажирских.

2) Система ограничений:

5х₁+8х₂ ? 81

6х₁+4х₂ ? 70

3х₁+х₂ ? 26

х₁ ? 0

х₂ ? 0

х₂ ? 6

Модель является линейной.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

x₁=6,

x₂=6.

f=7692

Данная задача относится к задачам целочисленного программирования.

Вывод: в случае когда железная дорога не может пропустить более 6 пассажирских поездов, оптимальным вариантом будет 6 скорых и 6 пассажирских поездов. При этом количество пассажиров = 7692.

3.5 Задача про столы и стулья

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

Небольшая фирма производит два вида продукции: столы и стулья. Для изготовления одного стула требуется 3 фута древесины, а для изготовления одного стола - 7 футов. На изготовление одного стула уходит 2 часа рабочего времени, а на изготовление стола - 8 часов. Каждый стул приносит 1 $ прибыли, а каждый стол - 3 $. Сколько стульев и сколько столов должна изготовить эта фирма, если она располагает 420 футами древесины и 400 часами рабочего времени и хочет получить максимальную прибыль?

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

Целевая функция:



f= x₁+3x₂ max,

где х₁- объем производства стульев,

х₂ - объем производства столов,

f - максимальная прибыль предприятия от реализации товара.

Система ограничений:

3х₁+7х₂ ? 420

2х₁+8х₂ ? 400

х₁ ? 0

х₂ ? 0

Модель является линейной.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

x₁=56,

x₂=36.

f= 164

Вывод: для того, чтобы получить максимальную прибыль f=164, необходимо производить 56 стульев и 36 столов.

3.6 Задача про удобрения

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

Некоторая фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 фунта азотных, 4 фунта фосфорных и 1 фунт калийных удобрений, а в улучшенный - 2 фунта азотных, 6 фунтов фосфорных и 3 фунта калийных удобрений. Известно, что для некоторого газона требуется по меньшей мере 10 фунтов азотных, 20 фунтов фосфорных и 7 фунтов калийных удобрений. Обычный набор стоит 3 $, а улучшенный - 4 $. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

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

Целевая функция:

f= 3x₁+4x₂ min,

где х₁- количество обычных наборов удобрений,

х₂ - количество улучшенных наборов удобрений,

f - минимальная стоимость.

Система ограничений:

3х₁+2х₂ ? 10

4х₁+6х₂ ? 20

х₁+6х₂ ? 7

х₁ ? 0

х₂ ? 0

Модель является линейной.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

x₁=2,

x₂=2.

f= 14

Вывод: для того, чтобы стоимость была минимальной = 14 $ и питание почвы было эффективным, необходимо купить 2 набора обычных удобрений и 2 набора улучшенных.

3.7 Задача про корм для животных

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

На ферме в качестве корма для животных используются два продукта: M и H. Сбалансированное питание предполагает, что каждое животное должно получать в день не менее 200 калорий, причем потребляемое при этом количество жира не должно превышать 14 единиц. Подсчитано, что в одном килограмме каждого продукта содержится:

в продукте M -150 калорий и 14 единиц жира;

в продукте H - 200 калорий и 4 единицы жира.

Как разработать максимально дешевый рацион откорма животных, отвечающий этим условиям, если стоимость 1 кг продукта M составляет 1,5 $ , а 1 кг продукта H - 2,5 $?

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

Целевая функция:

f= 1,5x₁+2,5x₂ min,

где х₁- количество продукта M в рационе,

х₂ - количество продукта Н в рационе,

f - минимальная стоимость рациона.

Система ограничений:

150х₁+200х₂ ? 200

14х₁+4х₂ ? 14

х₁ ? 0

х₂ ? 0

Модель является линейной.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

x₁=0,909,

x₂=0,318.

f= 2,16

Вывод: для того, чтобы стоимость рациона была минимальной = 2,16 $ необходимо, чтобы при кормлении в рационе было 0,909 кг продукта M и 0,318 кг продукта Н.

К данной задачи составим двойственную задачу.

Математическая модель задачи будет иметь следующий вид:

Целевая функция:

G = 200y₁+14y₂ max,

где y₁, y₂ - двойственные переменные,

G - максимальная стоимость запасов всех ресурсов.

Система ограничений:

150y₁+14y₂? 1,5

200y₁+4y₂+ ?4

y₁ ? 0

y₂ ? 0

y₃ ? 0



Модель является линейной.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

y₁ ? 0,01

y₂ ? 0

G = 2,16$

Вывод: максимальная стоимость рациона при кормлении в рационе : y₁=0.01, y₂=0 составляет 2,16$.

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

Аналитическое решение данной задачи симплекс - методом:

Найти значения переменных x₁...x₂, при которых функция:

L = 1,5 x₁ + 2,5 x₂

принимает минимальное значение

где х₁- количество продукта M в рационе,

х₂ - количество продукта N в рационе,

L- минимальная стоимость.

при условии следующих ограничений :

150х₁+200х₂ ? 200 (1)

14х₁+4х₂? 14 (2)

х₁ ? 0

х₂ ? 0

Избавимся от неравенств в ограничениях, введя в ограничения 1, 2 неотрицательные балансовые переменные s₁, s₂.

150 x₁ + 200 x₂ - x₃ = 200 (1)

14 x₁ + 4 x₂ - x₄ = 14 (2)

x₁, x₂, x₃, x₄ ? 0

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

Введем по одной искусственной неотрицательной переменной r_i в каждое уравнение системы ограничений. Получим следующую систему ограничений,

159 x₁ + 200 x₂ - x₃ + r₁ = 200 (1)

14 x₁ + 4 x₂ - x₄ + r₂ = 14 (2)

x₁, x₂, x₃, x₄, x₅, r₁, r₂ ? 0

с базисными переменными r₁,r₂.

Целью решения вспомогательной задачи является получение допустимого базисного решения не содержащего искусственных переменных(r₁,r₂). Для этого сформируем вспомогательную целевую функцию :

G = r₁ + r₂

Для решения вспомогательной задачи симплекс-методом выразим функцию G через свободные переменные, для этого:

- вычтем из функции G уравнение 1

- вычтем из функции G уравнение 2



3.8 Задача про столы и шкафы

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

Мебельная фабрика выпускает шкафы и столы. При изготовлении этой продукции требуются сосновые и березовые доски. Для изготовления стола требуется 0,15 м³ сосновых досок и 0,2 м³ березовых, а для изготовления шкафа - 0,2 м³ и 0,1 м³ соответственно. Доски сосновые могут поступать на фабрику в количестве не более 60 м³ в сутки, а березовые - не более 40 м³ в сутки. Прибыль от реализации одного стола -

12 000 руб, шкафа - 15 000 руб. Составьте план производства мебели, чтобы прибыль от ее реализации была наибольшей.

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

Целевая функция:

f= 15000x₁+12000x₂ max,

где х₁- объем производства шкафов,

х₂ - объем производства столов,

f - максимальная прибыль предприятия от реализации товара.

Система ограничений:

0,2х₁+0,15х₂ ? 60

0,1х₁+0,2х₂ ? 40

х₁ ? 0

х₂ ? 0

Модель является линейной.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

x₁=240,

x₂=80.

f= 4560000

Вывод: для того, чтобы прибыль от реализации продукции была максимальной = 4560000 руб., необходимо производить 240 шкафов и 80 столов.

3.9 Задача про автомобили

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

Заводы автомобильной фирмы MG расположены в Лос-Анджелесе, Детройте и Новом Орлеане. Основные центры распределения продукции сосредоточены в Денвере и Майами. Объемы производства указанных трех заводов равняются 1000, 1500 и 1200 автомобилей ежеквартально. Величины квартального спроса в центрах распределения составляют 2300 и 1400 автомобилей соответственно. Стоимость перевозки по железной дороге одного автомобиля на одну милю равняется примерно 8 центам. Расстояния в милях между заводами и центрами распределения приведены в следующей таблице:



Найти опорный и оптимальный планы .

1 миля=1,523 км

переводной коэффициент = 0,08 долл./миля

Предположим, что перевозки автомобилей с завода Детройт в Денвер нежелательны. Каким образом это условие можно включить в модель?

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

Целевая функция:

где х_i,j - объем груза, которое должно быть перевезено с i-ого исходного пункта в j-ый пункт назначения;

с_i,j - стоимость перевозки одной единицы грузов.

В данной задаче m=3, n=2.

Составляем ограничения на удовлетворение потребностей на всех пунктах потребления:

и ограничения на возможности вывоза запасов со всех пунктов производства:



Данная задача является сбалансированной, т.к. суммарный объем производства равен суммарному объему потребления:

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

Вывод: таким образом, оптимальное решение задачи предполагает перевозку 1000 автомобилей из Лос-Анджелеса в Денвер, 1300 автомобилей - из Детройта в Денвер, 200 автомобилей - из Детройта в Майами и 1200 - из Нового Орлеана в Майами. Минимальная стоимость перевозок составляет 313200 долларов.

Если предположить, что перевозки автомобилей с завода Детройт в Денвер нежелательны, то для этого нужно в диалоговом окне Поиск решения ввести ограничение В12=0. В математической интерпретации это указание запишется в виде ограничения х₂₁=0.



Вывод: в результате, потребности Денвера будут удовлетворены не в полном объеме.

3.10 Задача про добычу руды

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

На нескольких шахтах, расположенных в разных районах нашей страны, идет добыча руды, которую необходимо по железной дороге доставить на ряд металлургических комбинатов для выплавки металла. Расстояния от шахт до каждого комбината разные, различна поэтому и стоимость перевозок руды. Необходимо так спланировать доставку руды на комбинаты, чтобы общая стоимость перевозок была как можно меньше. В таблице указаны стоимость (в тыс. руб.) перевозки 1000 т руды в любом направлении, сколько руды добывается за некоторое время на каждой из трех шахт А, В, С и сколько этой руды потребляют два комбината - 1, 2.



1) Комбинат 1 требует увеличить поставку руды до 80 тыс.т..

2) В шахте В неприкосновенный запас должен составлять 10 тыс. т.

3) По маршруту шахта А- комбинат 2 мост закрыт на реконструкцию.

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

Целевая функция:

Где х_i,j - объем груза, которое должно быть перевезено с i-ого исходного пункта в j-ый пункт назначения;

с_i,j - стоимость перевозки одной единицы грузов.

В данной задаче m=3, n=2.

Составляем ограничения на удовлетворение потребностей на всех пунктах потребления:

и ограничения на возможности вывоза запасов со всех пунктов производства:

Данная задача является сбалансированной, т.к. суммарный объем производства равен суммарному объему потребления:

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

Вывод: таким образом, все потребности в руде удовлетворены при минимальной стоимости перевозки =1100 тыс. руб.

1) Теперь увеличим потребность в руде у комбината № 1 до 80 тыс.т.

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



остается без изменения, т.е. все запасы будут вывезены, а вот

изменится на

т.е. потребности будут удовлетворены не в полном объеме.

Вывод: таким образом, эти изменения вызвали недопоставки руды в комбинат №1 в размере 20 тыс.т., стоимость перевозки составляет 1100 тыс.руб.

2) Теперь допустим, что неприкосновенный запас в шахте В должен составлять 10 тыс. т.



Вывод: таким образом, эти изменения вызвали недопоставки руды в комбинат №1 и комбинат №2 в размере 10 и 20 тыс.т. соответственно, а стоимость перевозки увеличилась до 1120 тыс. руб.

3) Теперь предположим, что по маршруту шахта А - комбинат № 2 мост закрыт на реконструкцию.

Вывод: таким образом, эти изменения вызвали недопоставки руды в комбинат №2 в размере 30 тыс.т., а стоимость перевозки увеличилась до 1140 тыс.руб.

Задача № 1744 (из задачника)

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

Для изготовления изделий двух видов имеется 100 кг металла. На изготовление одного изделия I вида расходуется 2 кг металла, а изделия II вида - 4 кг. Составить план производства обеспечивающий получение наибольшей прибыли от продажи изделий, если отпускная стоимость одного изделия I вида составляет 3 ден. ед., а изделия II вида - 2 ден. ед., при чем изделии I вида требуется изготовить не более 40, а изделий II вида -- не более 20.

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

Целевая функция:

f=3x₁+2x₂ max,

где х₁- необходимое количество изделий I вида,

х₂ - необходимое количество изделий II вида,

f - максимальная прибыль предприятия от реализации товара.

Система ограничений:

х₁ ? 40

х₂ ? 20

2х₁+4х₂ = 100

х₁ ? 0

х₂ ? 0

Модель является линейной.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

x₁=40,

x₂=5.

f= 130

Вывод: для того, чтобы прибыль от реализации продукции была максимальной = 130 ден. ед., необходимо производить 40 кг изделия I вида и 5 кг изделия II вида.

Задача № 1753 (из задачника)

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

Производственная мощность цеха сборки составляет 120 изделий типа А и 360 изделий типа В в сутки. Технический контроль пропускает в сутки 200 изделий того или другого типа (безразлично). Изделия типа А вчетверо дороже изделий типа B. Требуется спланировать выпуск готовой продукции так, чтобы предприятию была обеспечена наибольшая прибыль.

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

Целевая функция:

f=4x₁+x₂ max,



где х₁- необходимое количество изделий типа А,

х₂ - необходимое количество изделий типа В,

f - максимальная прибыль предприятия от реализации товара.

Система ограничений:

х₁ + х₂ ? 200

х₁ ? 120

х₂ ? 360

х₁ ? 0

х₂ ? 0

Модель является линейной.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

x₁=120,

x₂=80.

f= 560

Вывод: для того, чтобы прибыль от реализации продукции была максимальной = 560 ден. ед., необходимо производить 120 изделий типа А и 80 изделий типа В.

Задача № 1754 (из задачника)

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

Для изготовления изделий двух видов склад может отпустить металла не более 80 кг, причем на изделие I вида расходуется 2 кг, а на изделие II вида -- 1 кг металла. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий I вида требуется изготовить не более 30 шт.,а изделий II вида не более 40 шт., причем одно изделие I вида стоит 5 ден. ед., а II вида - 3 ден. ед.

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

Целевая функция:

f=5x₁+3x₂ max,

где х₁- необходимое количество изделий I вида,

х₂ - необходимое количество изделий II вида,

f - максимальная прибыль предприятия от реализации товара.

Система ограничений:

2х₁ + х₂ ? 80

х₁ ? 30

х₂ ? 40

х₁ ? 0

х₂ ? 0

Модель является линейной.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

x₁=20,

x₂=40.

f = 220

Вывод: для того, чтобы прибыль от реализации продукции была максимальной = 220 ден. ед., необходимо производить 20 кг изделий I вида и 40 кг изделий II вида.

Задача № 1755 (из задачника)

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

Для откорма животных употребляют два вида кормов; стоимость 1 кг корма I вида -- 5 ден. ед., а корма II вида - 2 ден. ед. В каждом килограмме корма I вида содержится 5 ед. питательного вещества А, 2,5 ед. питательного вещества Б и 1 ед. питательного вещества В, а в каждом килограмме корма II вида соответственно 3, 3 и 1,3 ед. Какое количество корма каждого вида необходимо расходовать ежедневно, чтобы затраты на откорм были минимальными, если суточный рацион предусматривает питательных единиц типа А не менее 225 ед., типа Б --не менее 150 ед. и типа В - не менее 80 ед.?

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

Целевая функция:

f=5x₁+2x₂ min,

где х₁- необходимое количество корма I вида,

х₂ - необходимое количество корма II вида,

f - минимальные затраты на откорм.

Система ограничений:

5х₁ +3 х₂ ? 225

2,5х₁ +3 х₂ ? 150

х₁ +1,3 х₂ ? 80

х₁ ? 0

х₂ ? 0

Модель является линейной.

После введения формул в ячейки MS Excel c помощью Поиска решений находим значения.

x₁=0,

x₂=75.

f = 150

Вывод: для того, чтобы затраты на откорм были минимальными = 150 ден. ед., необходимо расходовать ежедневно 75 кг корма II вида.

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