Menyelesaikan masalah pengaturcaraan linear menggunakan Excel. Menyelesaikan masalah pengaturcaraan linear dalam Excel - Abstrak

Sasaran: belajar menyelesaikan masalah pengaturcaraan linear dalam Excel menggunakan alat tambah Carian Penyelesaian.

Maklumat teori ringkas

Masalah pengoptimuman digunakan secara meluas dalam pelbagai bidang aktiviti praktikal: dalam mengatur kerja sistem pengangkutan, dalam pengurusan perusahaan perindustrian, dalam penyediaan projek untuk sistem yang kompleks. Banyak kelas masalah biasa analisis sistem, khususnya, masalah perancangan optimum, pengagihan pelbagai sumber, pengurusan inventori, penjadualan, dan keseimbangan antara industri sesuai dengan rangka kerja model pengaturcaraan linear.

Pernyataan masalah pengaturcaraan linear (LPP).

Terdapat banyak pembolehubah X= (x 1, x 2,..., x n). Fungsi objektif bergantung secara linear pada parameter terkawal:

Terdapat sekatan yang bentuk linear

di mana (2)

Ia diperlukan untuk menentukan maksimum (minimum) fungsi linear

dengan syarat bahawa titik (x 1, x 2,..., x n) tergolong dalam beberapa set D, yang ditentukan oleh sistem ketaksamaan linear

(4)

Mana-mana set nilai (x 1 *, x 2 *,..., x n *) yang memenuhi sistem ketaksamaan (4) masalah pengaturcaraan linear adalah penyelesaian yang sah untuk masalah ini. Sekiranya ketidaksamaan berlaku

c 1 x 1 o + c 2 x 2 o +..+ c n x n o ≥ c 1 x 1 + c 2 x 2 +..+ c n x n

untuk keseluruhan set nilai x 1, x 2,..., x n, maka nilai x 1 o .. x n o ialah penyelesaian optimum kepada masalah pengaturcaraan linear.

Contoh membina model matematik dan menyelesaikan ZLP.

Tugasan. Adalah perlu untuk menentukan dalam kuantiti yang diperlukan untuk menghasilkan produk empat jenis A, B, C dan D, pengeluaran yang memerlukan tiga jenis sumber: buruh, bahan mentah dan kewangan. Jumlah setiap jenis sumber yang diperlukan untuk menghasilkan satu unit pengeluaran jenis ini, dipanggil kadar penggunaan. Kadar penggunaan, serta keuntungan yang diterima daripada penjualan seunit bagi setiap jenis produk, ditunjukkan dalam jadual 1. Ketersediaan sumber yang ada juga ditunjukkan di sana.

Jadual 1.

Sumber

A

B

C

D

tanda

Ketersediaan

buruh

Mari buat model matematik, yang mana kami memperkenalkan notasi berikut:

x saya - kuantiti produk jenis ke-i, i = 1,2,3,4

b j – jumlah sumber yang ada bagi jenis j, j = 1,2,3

seorang ji - kadar penggunaan sumber ke-j untuk pengeluaran produk ke-i

c i – keuntungan daripada penjualan unit produk jenis ke-i.

Seperti yang dapat dilihat daripada Jadual 1, untuk satu unit keluaran A 6 unit bahan mentah diperlukan, yang bermaksud untuk menghasilkan semua produk A 6 diperlukan x 1 unit bahan mentah, di mana x 1- kuantiti produk yang dihasilkan A. Mengambil kira bahawa untuk jenis produk lain kebergantungan adalah serupa, had ke atas bahan mentah akan kelihatan seperti:

6x 1+ 5x 2+ 4x 3+ 3x 4≤ 110

Dalam kekangan ini, bahagian kiri adalah sama dengan jumlah sumber yang diperlukan, dan bahagian kanan menunjukkan jumlah sumber yang tersedia.

Begitu juga, anda boleh membuat sekatan untuk jenis sumber lain dan menulis kebergantungan untuk Fungsi objektif. Kemudian model matematik masalah akan kelihatan seperti:

x 1+ x 2+ x 3+ x 4≤ 16

6x 1+ 5x 2+ 4x 3+ 3x 4≤ 110

4x 1+ 6x 2+ 10x 3+ 13x 4≤ 100

x i≥ 0, i=1,2,3,4

1. Untuk memasukkan syarat masalah, cipta borang dalam Excel (Gamb. 1). Sel B3:E3 akan memaparkan nilai yang dikira x i .


Rajah 1. Borang untuk memasukkan keadaan masalah

2. Mari kita masukkan pekali fungsi objektif dan kekangan ke dalam bentuk. Mari kita perkenalkan kebergantungan daripada model matematik. Data yang dimasukkan ditunjukkan dalam Rajah 2.


Rajah.2. Data input tugas

Sel F6 mengandungi formula fungsi objektif, dan F9-F11 mengandungi bahagian kiri kekangan daripada model matematik. Dalam Rajah. Rajah 3 menunjukkan mod pembentangan formula. Pergi ke rejim ini boleh dilakukan menggunakan urutan tindakan berikut: tekan butang Microsoft Office , klik Pilihan Excel buka tab Selain itu dan tandakan kotak Tunjukkan formula, bukan nilainya.


Rajah.3. Mod persembahan formula.

3. Muat turun carian tambahan untuk penyelesaian Data│Analisis│Mencari penyelesaian.

4. Di padang Tetapkan sel sasaran Mari masukkan pautan ke sel sasaran dengan meletakkan kursor dalam medan dan klik kiri pada sel F6.

5. Pilih arah carian dengan menandakan kotak sama dengan nilai maksimum.

6. Letakkan kursor dalam medan Menukar sel dan gunakan tetikus untuk memasukkan nama sel B3:E3 yang akan ditukar. Dalam sel ini, hasil daripada mencari penyelesaian, penyelesaian akan dipaparkan - nilai pembolehubah x i., di mana fungsi objektif mempunyai nilai maksimum di bawah sekatan yang diberikan.

7. Mari kita perkenalkan sekatan pada pembolehubah yang diperlukan: x i ≥ 0 (batas bawah lalai ialah 0, kuantiti keluaran tidak boleh negatif). Kami juga akan memperkenalkan sekatan ke atas sumber (lebih banyak sumber tidak boleh digunakan daripada rizab mereka). Jom klik pada butang Tambah, dalam tetingkap yang muncul Menambah kekangan dalam medan kiri menggunakan tetikus, masukkan pautan ke sel B3, pilih tanda dari senarai juntai bawah ≥, dalam medan kanan, klik pada sel B4 (Gamb. 4). Marilah kita memperkenalkan sekatan yang selebihnya dengan cara yang sama.


Rajah.4. Tetingkap untuk menambah sekatan.

Rajah 5 menunjukkan tetingkap Carian untuk penyelesaian yang lengkap.


Fig.5 Tetingkap penuh Cari penyelesaian

8. Seterusnya, klik pada butang Laksanakan. Kotak dialog Keputusan Carian Penyelesaian muncul (Gamb. 6). Penyelesaian telah ditemui. Semua sekatan dan syarat optimum dipenuhi. Kami menyimpan penyelesaian yang ditemui. Dalam tetingkap ini, anda juga boleh mendapatkan tiga jenis laporan: mengenai hasil, kestabilan dan had, laporan dijana dalam lembaran kerja baharu.


Rajah.6. Tetingkap hasil carian penyelesaian

Keputusan penyelesaian optimum kepada masalah ditunjukkan dalam jadual (Rajah 7).


Rajah.7. Keputusan Penyelesaian Optimum

Demikian ternyata penyelesaian yang optimum(10;0;6;0), i.e. Adalah dinasihatkan untuk menghasilkan 10 unit produk A dan 6 unit produk C. Keuntungan maksimum ialah 1320 unit kewangan, manakala semua tenaga buruh dan sumber kewangan digunakan, 84 unit bahan mentah, 26 unit bahan mentah kekal dalam stok.

Tugasan kerja makmal.

Cipta model matematik dan selesaikan masalah pengaturcaraan linear yang terhasil dalam Excel menggunakan tambahan Carian Penyelesaian.

Untuk mengangkut barang, mesin jenis A dan B digunakan. Kapasiti tampung kedua-dua jenis mesin adalah sama dan sama dengan h t. Dalam satu perjalanan, mesin A menggunakan a 11 kg pelincir dan a 12 l bahan api, kereta B - a 21 kg pelincir dan a 22 l bahan api. Pangkalan mempunyai d 1 kg pelincir dan d 2 l bahan api. Keuntungan mengangkut satu kereta A ialah dari 1 gosok., kereta B - dari 2 gosok. Ia adalah perlu untuk mengangkut Ht kargo (data awal diberikan dalam jadual di bawah).

Berapakah bilangan kenderaan kedua-dua jenis yang mesti digunakan untuk memaksimumkan pendapatan daripada pengangkutan kargo?

Pilihan No.

Arahan untuk melaksanakan kerja makmal.

  1. Mempelajari bahan teori.
  2. Jalankan contoh yang diberikan.
  3. Pilih pilihan anda berdasarkan digit terakhir.
  4. Buat model matematik masalah.
  5. Cari penyelesaian optimum menggunakan Pencari Penyelesaian.
  6. Buat kesimpulan berdasarkan penyelesaian yang diperoleh, hasilkan laporan tentang keputusan penyelesaian, kestabilan dan had.
  7. Buat laporan makmal.
  1. Tajuk muka surat.
  2. Pernyataan masalah secara lisan.
  3. Rumusan matematik masalah.
  4. Tetingkap penuh Cari penyelesaian
  5. Hasil carian untuk penyelesaian (jadual).
  6. Kesimpulan terhadap penyelesaian yang diperolehi.

Senarai sumber

  1. Gelman V.Ya. Penyelesaian masalah matematik menggunakan Excel: Bengkel. – St. Petersburg: Peter, 2003
  2. Kuritsky B.Ya. Cari penyelesaian optimum menggunakan Excel. – St. Petersburg: BHV-St. Petersburg, 1997
  3. Pazyuk K.T. Kaedah dan model matematik dalam ekonomi. – Khabarovsk: KhSTU Publishing House, 2002
  4. John Walkenbach. MS OfficeExcel 2007 - Alkitab Pengguna, Penerbit: Williams, 2008

Adalah perlu untuk menentukan dalam kuantiti yang diperlukan untuk menghasilkan produk empat jenis Prod1, Prod2, Prod3, Prod4, pengeluaran yang memerlukan tiga jenis sumber: buruh, bahan mentah dan kewangan. Jumlah setiap jenis sumber yang diperlukan untuk menghasilkan unit produk daripada jenis tertentu dipanggil kadar penggunaan. Kadar penggunaan, serta keuntungan yang diterima daripada penjualan unit bagi setiap jenis produk, ditunjukkan dalam Rajah. 1.

Sumber

Samb1

Prod2

Prod3

Prod4

Tanda

Ketersediaan

Untung

buruh

Bahan mentah

Kewangan

Gambar 1.

Model matematik tugas mempunyai bentuk:

di mana x j ialah kuantiti produk perkilangan jenis j; F – fungsi matlamat; sebelah kiri ungkapan kekangan menunjukkan nilai sumber yang diperlukan, dan bahagian kanan menunjukkan kuantiti sumber yang ada.

Memasuki syarat tugas

Untuk menyelesaikan masalah dengan menggunakan Excel Anda harus membuat borang untuk memasukkan data awal dan memasukkannya. Borang input ditunjukkan dalam Rajah. 2.

Dalam sel F6, ungkapan untuk fungsi objektif diperkenalkan sebagai jumlah produk nilai keuntungan daripada keluaran unit produk setiap jenis dengan bilangan produk jenis yang sepadan. Untuk kejelasan, dalam Rajah. Rajah 3 menunjukkan borang untuk memasukkan data awal dalam mod output formula.

Bahagian kiri sekatan untuk sumber setiap jenis dimasukkan ke dalam sel F8:F10.

Rajah 2.

Rajah 3.

Menyelesaikan masalah pengaturcaraan linear

Untuk menyelesaikan masalah pengaturcaraan linear dalam Excel, gunakan alat yang berkuasa, dipanggil Mencari penyelesaian . Akses kepada Carian untuk penyelesaian dijalankan daripada menu Perkhidmatan , kotak dialog Cari Penyelesaian muncul pada skrin (Gamb. 4).

Rajah 4.

Memasuki syarat masalah untuk mencari penyelesaiannya terdiri daripada langkah-langkah berikut:

1 Berikan fungsi sasaran dengan meletakkan kursor dalam medan Tetapkan sel sasaran tetingkap Cari penyelesaian dan klik dalam sel F6 dalam borang input;

2 Hidupkan suis untuk nilai fungsi objektif, i.e. menunjukkannya sama Nilai maksimum ;

3 Masukkan alamat pembolehubah yang hendak ditukar (x j): untuk melakukan ini, letakkan kursor dalam medan Menukar sel tetingkap Cari penyelesaian, dan kemudian pilih julat sel B3:E3 dalam borang input;

4 Tekan butang Tambah Tetingkap carian penyelesaian untuk memasukkan kekangan untuk masalah pengaturcaraan linear; tetingkap muncul pada skrin Menambah kekangan (Gamb. 5) :

Masukkan syarat sempadan untuk pembolehubah x j (x j ³0), untuk ini dalam medan Rujukan sel tandakan sel B3 sepadan dengan x 1, pilih tanda yang dikehendaki (³) daripada senarai dalam medan Had menunjukkan sel borang input di mana nilai yang sepadan bagi keadaan sempadan disimpan (sel B4), klik butang Tambah ; ulangi langkah yang diterangkan untuk pembolehubah x 2, x 3 dan x 4;

Masukkan sekatan untuk setiap jenis sumber dalam medan Rujukan sel tingkap Menambah kekangan nyatakan sel F9 borang input, yang mengandungi ungkapan sebelah kiri sekatan yang dikenakan ke atas sumber buruh di ladang Had tunjukkan tanda £ dan alamat H9 di sebelah kanan sekatan, tekan butang Tambah ; juga memperkenalkan sekatan ke atas jenis sumber lain;

Selepas masuk sekatan terakhir bukannya Tambah tekan okey dan kembali ke tetingkap Carian untuk penyelesaian.

Rajah 5.

Menyelesaikan masalah pengaturcaraan linear bermula dengan menetapkan parameter carian:

Di tingkap Mencari penyelesaian tekan butang Pilihan , tetingkap muncul pada skrin Pilihan Carian Penyelesaian (Gamb. 6);

Kotak semak model linear, yang memastikan penggunaan kaedah simpleks;

Nyatakan bilangan maksimum lelaran (lalai ialah 100, yang sesuai untuk menyelesaikan kebanyakan masalah);

Kotak semak , jika anda perlu menyemak semua peringkat mencari penyelesaian yang optimum;

klik okey , kembali ke tetingkap Mencari penyelesaian .

Rajah 6.

Untuk menyelesaikan masalah, tekan butang Laksanakan dalam tingkap Mencari penyelesaian , terdapat tetingkap pada skrin Hasil carian penyelesaian (Gamb. 7), yang mengandungi mesej Penyelesaian telah ditemui. Semua sekatan dan syarat optimum dipenuhi. Jika keadaan masalah tidak konsisten, mesej dipaparkan Carian tidak dapat mencari penyelesaian yang sesuai. Jika fungsi objektif tidak terhad, maka mesej muncul Nilai sel sasaran tidak bertumpu.

Rajah 7.

Untuk contoh yang sedang dipertimbangkan, penyelesaian telah ditemui dan hasil penyelesaian optimum kepada masalah dipaparkan dalam bentuk input: nilai fungsi objektif yang sepadan keuntungan maksimum dan bersamaan dengan 1320, ditunjukkan dalam sel F6 borang input, rancangan pengeluaran optimum x 1 =10, x 2 =0, x 3 =6, x 4 =0 ditunjukkan dalam sel B3:C3 borang input (Rajah 8).

Jumlah sumber yang digunakan untuk menghasilkan produk dipaparkan dalam sel F9:F11: buruh - 16, bahan mentah - 84, kewangan - 100.

Rajah 8.

Jika, apabila menetapkan parameter dalam tetingkap Pilihan Carian Penyelesaian (Gamb. 6) kotak semak telah ditandai Tunjukkan hasil lelaran , maka semua langkah carian akan ditunjukkan secara berurutan. Tetingkap akan muncul pada skrin (Gamb. 9). Dalam kes ini, nilai semasa pembolehubah dan fungsi matlamat akan ditunjukkan dalam borang input. Oleh itu, keputusan lelaran pertama mencari penyelesaian masalah asal dibentangkan dalam borang input dalam Rajah 10.

Rajah 9.

Rajah 10.

Untuk terus mencari penyelesaian, klik butang teruskan dalam tingkap Keadaan sekarang mencari penyelesaian .

Analisis penyelesaian optimum

Sebelum meneruskan analisis keputusan penyelesaian, mari kita kemukakan masalah asal dalam bentuk

dengan memperkenalkan pembolehubah tambahan untuk i, mewakili nilai sumber yang tidak digunakan.

Mari wujudkan masalah dwi untuk masalah asal dan perkenalkan pembolehubah dwi tambahan v i .

Analisis hasil carian untuk penyelesaian akan membolehkan kita menghubungkannya dengan pembolehubah awal dan dua masalah.

Menggunakan tingkap Hasil carian penyelesaian Anda boleh memanggil tiga jenis laporan yang membolehkan anda menganalisis penyelesaian optimum yang ditemui:

Keputusan,

Kemampanan,

had.

Untuk memanggil laporan dalam medan Jenis laporan tajuk sorotan jenis yang betul dan tekan okey .

1 Laporan keputusan(Gamb. 11) terdiri daripada tiga jadual:

Jadual 1 mengandungi maklumat tentang fungsi objektif; dalam lajur Asalnya nilai fungsi objektif ditunjukkan sebelum pengiraan bermula;

Jadual 2 mengandungi nilai pembolehubah yang diperlukan x j yang diperoleh hasil daripada penyelesaian masalah (rancangan pengeluaran optimum);

Jadual 3 menunjukkan keputusan penyelesaian optimum untuk kekangan dan untuk keadaan sempadan.

Untuk Sekatan dalam lajur Formula kebergantungan yang telah dimasukkan semasa menetapkan sekatan dalam tetingkap ditunjukkan Mencari penyelesaian ; dalam lajur Maknanya nilai sumber yang digunakan ditunjukkan; dalam lajur Beza menunjukkan jumlah sumber yang tidak digunakan. Jika sumber digunakan sepenuhnya, maka dalam lajur negeri mesej dipaparkan berkaitan ; jika sumber tidak digunakan sepenuhnya, lajur ini menunjukkan tidak bersambung. Untuk Syarat sempadan nilai yang sama diberikan dengan satu-satunya perbezaan iaitu bukannya sumber yang tidak digunakan, perbezaan antara nilai pembolehubah x j dalam penyelesaian optimum yang ditemui dan keadaan sempadan yang ditentukan untuknya (x j ³0) ditunjukkan.

Ia ada dalam lajur Beza anda boleh melihat nilai pembolehubah tambahan y i masalah asal dalam rumusan (2). Di sini y 1 =y 3 =0, i.e. jumlah tenaga buruh dan sumber kewangan yang tidak digunakan adalah sifar. Sumber-sumber ini digunakan sepenuhnya. Pada masa yang sama, jumlah sumber yang tidak digunakan untuk bahan mentah y 2 = 26, bermakna terdapat lebihan bahan mentah.

Rajah 11.

2 Laporan kemampanan(Gamb. 12)terdiri daripada dua jadual.

Jadual 1 menunjukkan nilai berikut:

Hasil penyelesaian masalah (pelan pelepasan optimum);

- Normir. harga, iaitu nilai yang menunjukkan berapa banyak fungsi objektif akan berubah apabila unit pengeluaran jenis yang sepadan terpaksa dimasukkan ke dalam pelan optimum;

Pekali fungsi objektif;

Hadkan nilai untuk penambahan pekali fungsi objektif di mana rancangan pengeluaran optimum dikekalkan.

Jadual 2 mengandungi data yang serupa untuk sekatan:

Jumlah sumber yang digunakan;

- Harga bayangan, menunjukkan bagaimana fungsi objektif berubah apabila nilai sumber yang sepadan berubah sebanyak satu;

Nilai yang sah penambahan sumber di mana rancangan pengeluaran optimum dikekalkan.

Rajah 12.

Laporan kemampanan membenarkan penilaian dua kali.

Seperti yang diketahui, dwi pembolehubah z i menunjukkan bagaimana fungsi objektif berubah apabila sumber jenis ke-i berubah sebanyak satu. Dalam laporan Excel, anggaran dwi dipanggil Harga bayangan.

Dalam contoh kami, bahan mentah tidak digunakan sepenuhnya dan sumbernya y 2 = 26. Jelas sekali, peningkatan dalam jumlah bahan mentah, sebagai contoh, kepada 111, tidak akan memerlukan peningkatan dalam fungsi objektif. Oleh itu, untuk kekangan kedua pembolehubah dwi z 2 =0. Justeru, jika mengikut sumber ini ada rizab, maka pembolehubah tambahan akan lebih besar daripada sifar, dan penilaian berganda daripada kekangan ini adalah sifar.

Dalam contoh yang sedang dipertimbangkan, sumber buruh dan kewangan telah digunakan sepenuhnya, jadi pembolehubah tambahannya adalah sama dengan sifar (y 1 =y 3 =0). Jika sumber digunakan sepenuhnya, maka pertambahan atau penurunannya akan menjejaskan volum keluaran, dan oleh itu nilai fungsi objektif. Anggaran dua sekatan ke atas buruh dan sumber kewangan adalah berbeza daripada sifar, i.e. z 1 =20, z 3 =10.

Nilai anggaran dwi terdapat dalam Laporan kemampanan, dalam jadual 2, dalam lajur Harga bayangan.

Dengan pertambahan (penurunan) sumber tenaga kerja sebanyak satu unit, fungsi objektif akan meningkat (penurunan) sebanyak 20 unit dan bersamaan dengan

F=1320+20×1=1340 (dengan pembesaran).

Begitu juga, apabila jumlah kewangan meningkat sebanyak satu unit, fungsi objektif akan menjadi

F=1320+10×1=1330.

Di sini, dalam graf Peningkatan yang dibenarkan Dan Pengurangan yang dibenarkan Jadual 2 menunjukkan had yang dibenarkan untuk menukar jumlah sumber jenis ke-j. Sebagai contoh, apabila kenaikan dalam nilai sumber buruh berubah dari -6 kepada 3.55, seperti yang ditunjukkan dalam jadual, struktur penyelesaian optimum dikekalkan, iaitu keuntungan terbesar disediakan oleh output Prod1 dan Prod3, tetapi dalam kuantiti yang berbeza.

Pembolehubah dwi tambahan juga ditunjukkan dalam Laporan kemampanan dalam lajur Normir. harga jadual 1.

Jika pembolehubah utama tidak termasuk dalam penyelesaian optimum, i.e. adalah sama dengan sifar (dalam contoh x 2 =x 4 =0), maka pembolehubah tambahan yang sepadan mempunyai nilai positif (v 2 =10, v 4 =20). Jika pembolehubah utama dimasukkan ke dalam penyelesaian optimum (x 1 =10, x 3 =6), maka pembolehubah dwi tambahannya adalah sama dengan sifar (v 1 =0, v 3 =0).

Nilai ini menunjukkan berapa banyak fungsi objektif akan berkurangan (oleh itu tanda tolak dalam nilai pembolehubah v 2 dan v 4) dengan pelepasan paksa unit produk ini. Oleh itu, jika kita ingin melepaskan secara paksa satu unit produk jenis Prod3, maka fungsi objektif akan berkurangan sebanyak 10 unit dan akan bersamaan dengan 1320 -10×1 = 1310.

Mari kita nyatakan dengan Dс j perubahan dalam pekali fungsi objektif dalam model asal (1). Pekali ini menentukan keuntungan yang diterima daripada penjualan unit produk jenis ke-j.

Dalam graf Peningkatan yang dibenarkan Dan Pengurangan yang Dibenarkan jadual 1 Laporan kemampanan had perubahan dalam Dc j ditunjukkan di mana struktur pelan optimum dipelihara, i.e. Ia akan menguntungkan untuk terus menghasilkan produk jenis Prodj. Contohnya, jika Dc 1 berubah dalam -12 £ Dc 1 £ 40, seperti yang ditunjukkan dalam laporan, ia masih menguntungkan untuk menghasilkan produk jenis Prod1. Dalam kes ini, nilai fungsi objektif ialah F=1320+x 1 ×Dс j =1320+10×Dс j .

3 Hadkan laporan ditunjukkan dalam Rajah. 13. Ia menunjukkan dalam had apa nilai x j termasuk dalam penyelesaian optimum boleh berubah sambil mengekalkan struktur penyelesaian optimum. Di samping itu, untuk setiap jenis produk, nilai fungsi objektif diberikan, diperoleh dengan menggantikan ke dalam penyelesaian optimum nilai had bawah pengeluaran produk jenis yang sepadan dengan nilai tetap output yang lain. jenis. Sebagai contoh, jika untuk penyelesaian optimum x 1 =10, x 2 =0, x 3 =6, x 4 =0 kita letakkan x 1 =0 (had bawah) dengan x 2, x 3 dan x 4 tidak berubah, maka nilai fungsi objektif akan sama dengan 60×0+70×0+120×6+130×0=720.

Tambahan ialah alat untuk menyelesaikan masalah pengoptimuman dalam MS Excel Mencari penyelesaian. Prosedur carian penyelesaian membolehkan kami mencari nilai optimum formula yang terkandung dalam sel yang dipanggil sel sasaran. Prosedur ini berfungsi pada sekumpulan sel yang berkaitan secara langsung atau tidak langsung dengan formula dalam sel sasaran. Untuk mendapatkan hasil yang ditentukan daripada formula yang terkandung dalam sel sasaran, prosedur mengubah nilai dalam sel yang mempengaruhi.

Jika tambahan ini dipasang, kemudian Mencari penyelesaian dilancarkan daripada menu Perkhidmatan. Jika tiada item sedemikian, anda harus menjalankan arahan Perkhidmatan → Alat tambah... dan tandakan kotak pada add-in
Mencari penyelesaian(Gamb. 2.1).


Pasukan Perkhidmatan → Mencari penyelesaian membuka kotak dialog "Mencari penyelesaian".

Di tingkap Mencari penyelesaian tersedia bidang berikut:

Tetapkan sel sasaran– berfungsi untuk menentukan sel sasaran yang nilainya harus dimaksimumkan, diminimumkan atau ditetapkan kepada nombor tertentu. Sel ini mesti mengandungi formula.

sama– berfungsi untuk memilih pilihan untuk mengoptimumkan nilai sel sasaran (maksimum, pengecilan atau Pemilihan nombor yang diberi). Untuk menetapkan nombor, masukkannya dalam medan.

Menukar sel– berfungsi untuk menunjukkan sel yang nilainya berubah semasa mencari penyelesaian sehingga sekatan yang dikenakan dan syarat untuk mengoptimumkan nilai sel yang dinyatakan dalam medan Tetapkan sel sasaran dipenuhi.

teka- digunakan untuk carian automatik sel yang mempengaruhi formula yang dirujuk dalam kotak Tetapkan sel sasaran. Hasil carian dipaparkan dalam medan Mengedit sel.

Sekatan– berfungsi untuk memaparkan senarai syarat sempadan tugas.

Tambah- berfungsi untuk memaparkan kotak dialog Tambah Kekangan.

Ubah- Memaparkan kotak dialog Edit Had.

Padam- Berfungsi untuk menghapuskan sekatan yang ditentukan.

Laksanakan– Berfungsi untuk melancarkan pencarian untuk penyelesaian kepada masalah yang diberikan.

tutup– Berfungsi untuk keluar dari tetingkap dialog tanpa memulakan carian untuk penyelesaian tugas.

Pilihan carian penyelesaian, di mana anda boleh memuatkan atau menyimpan model untuk dioptimumkan dan menunjukkan pilihan yang disediakan untuk mencari penyelesaian.


Pulihkan– Berfungsi untuk mengosongkan medan tetingkap dialog dan memulihkan nilai lalai bagi parameter carian penyelesaian.

Untuk menyelesaikan masalah pengoptimuman, ikut langkah berikut:

1. Dalam menu Perkhidmatan pilih pasukan Mencari penyelesaian.

2. Di padang Tetapkan sel sasaran Masukkan alamat atau nama sel yang mengandungi formula model untuk dioptimumkan.

3. Untuk memaksimumkan nilai sel sasaran dengan menukar nilai sel yang mempengaruhi, tetapkan suis kepada nilai maksimum.

Untuk meminimumkan nilai sel sasaran dengan menukar nilai sel yang mempengaruhi, tetapkan suis kepada
nilai minimum.

Untuk menetapkan nilai dalam sel sasaran kepada nombor dengan menukar nilai sel yang mempengaruhi, tetapkan suis kepada maksudnya dan masukkan nombor yang diperlukan dalam medan yang sesuai.

4. Di padang Menukar sel Masukkan nama atau alamat sel yang hendak ditukar, dipisahkan dengan koma. Sel boleh tukar mestilah berkaitan secara langsung atau tidak langsung dengan sel sasaran. Sehingga 200 sel boleh ubah boleh dipasang.

Untuk mencari semua sel yang mempengaruhi formula model secara automatik, klik Anggaplah.

5. Di padang Sekatan masukkan semua sekatan yang dikenakan untuk mencari penyelesaian.

6. Klik butang Laksanakan.

Untuk memulihkan data asal, tetapkan suis kepada

Peringkat C. Analisis penyelesaian yang ditemui kepada masalah pengoptimuman.

Untuk memaparkan mesej akhir tentang keputusan keputusan, kotak dialog digunakan Hasil carian untuk penyelesaian.

Kotak dialog Keputusan Carian Penyelesaian mengandungi medan berikut:

Pulihkan nilai asal- berfungsi untuk pemulihan nilai awal mempengaruhi sel-sel model.

Laporan– berfungsi untuk menunjukkan jenis laporan yang disiarkan lembaran berasingan buku.

Keputusan. Digunakan untuk membuat laporan yang terdiri daripada sel sasaran dan senarai sel model yang mempengaruhi, nilai awal dan akhir mereka serta formula kekangan dan maklumat tambahan tentang sekatan yang dikenakan.

Kelestarian. Digunakan untuk membuat laporan yang mengandungi maklumat tentang sensitiviti penyelesaian kepada perubahan kecil dalam formula (medan Tetapkan sel sasaran, tetingkap dialog Cari penyelesaian) atau dalam formula kekangan.

Sekatan. Digunakan untuk membuat laporan yang terdiri daripada sel sasaran dan senarai sel model yang mempengaruhi, nilainya serta sempadan bawah dan atas. Laporan ini tidak dijana untuk model yang nilainya terhad kepada banyak integer. Had bawah ialah nilai terkecil yang boleh terkandung dalam sel yang mempengaruhi, manakala nilai sel yang mempengaruhi selebihnya ditetapkan dan memenuhi sekatan yang dikenakan. Sehubungan itu, had atas adalah nilai terbesar.

Simpan skrip– berfungsi untuk memaparkan kotak dialog Menyimpan skrip di mana anda boleh menyimpan skrip untuk menyelesaikan masalah untuk menggunakannya kemudian menggunakan pengurus skrip MS Excel. Dalam bahagian berikut kita akan melihat beberapa model tertentu pengoptimuman linear dan contoh penyelesaian mereka menggunakan MS Excel.

2.4 Masalah perancangan pengeluaran

Perumusan masalah. Syarikat mesti mengeluarkan produk n jenis: dan 1 ,dan 2 ,...dan p, dan kuantiti setiap produk yang dihasilkan tidak boleh melebihi permintaan β 1, β 2,..., β n dan pada masa yang sama tidak boleh kurang daripada nilai yang dirancang b 1 ,b 2 ,...,b n masing-masing. Ia digunakan untuk pembuatan produk m jenis bahan mentah s l ,s 2 ,...,s m, rizab yang masing-masing dihadkan oleh nilai γ 1 , γ 2 ,..., γ m. Adalah diketahui bahawa untuk pengeluaran i-produk ke- akan datang dan ij unit j-bahan mentah ke. Keuntungan yang diterima daripada penjualan produk anda 1, ,dan 2,...dan p sama dengan sewajarnya daripada 1, daripada 2,..., daripada p. Ia dikehendaki merancang pengeluaran produk sedemikian rupa sehingga keuntungan dimaksimumkan dan pada masa yang sama rancangan untuk pengeluaran setiap produk dipenuhi, tetapi permintaan untuknya tidak melebihi.

Model matematik. Mari kita nyatakan dengan x 1, x 2,...x n bilangan unit produk anda 1, ,dan 2,...dan p, dihasilkan oleh perusahaan. Keuntungan yang dibawa oleh pelan (fungsi sasaran) akan sama dengan:

z = z(x 1 ,x 2 ,...,x n) = c 1 x 1 + c 2 x 2 + ...+c n x n → maks. Sekatan ke atas pelaksanaan pelan akan ditulis dalam borang: x i ≥β i untuk i = 1,2,...,n Untuk tidak melebihi permintaan, adalah perlu untuk mengehadkan pengeluaran produk: x i ≤β i Untuk i= 1,2,...n. Dan akhirnya, sekatan ke atas bahan mentah akan ditulis dalam bentuk sistem ketidaksamaan:

α 11 x 1 + α 12 x 2 +...+ α 1n x n ≤b 1

α 21 x 1 + α 22 x 2 +...+ α 2n x n ≤b 2

................................................

α m1 x 1 + α m2 x 2 +...+ α mn x n ≤b m

dengan syarat itu x 1, x 2,...x n bukan negatif.

Contoh 2.1:

Mari kita pertimbangkan contoh khusus masalah tentang perancangan pengeluaran dan berikan urutan tindakan yang perlu untuk menyelesaikannya menggunakan MS Excel.

Tugas. Syarikat itu mengeluarkan dua jenis produk konkrit bertetulang: penerbangan tangga dan papak balkoni. Untuk menghasilkan satu tangga, 3.5 meter padu diperlukan. konkrit dan 1 pakej tetulang, dan untuk pengeluaran papak - 1 meter padu. konkrit dan 2 bungkusan tetulang. Setiap unit pengeluaran memerlukan 1 hari kerja buruh. Keuntungan daripada penjualan 1 tangga ialah 200 rubel, dan satu papak adalah 100 rubel. Perusahaan itu menggaji 150 orang, dan diketahui bahawa perusahaan itu menghasilkan tidak lebih daripada 350 meter padu setiap hari. konkrit dan tidak lebih daripada 240 bungkusan tetulang diimport. Ia dikehendaki merangka pelan pengeluaran supaya keuntungan daripada produk yang dihasilkan adalah maksimum.

Penyelesaian.

1. Pada helaian buku kerja MS Excel mengisi jadual parameter tugasan (Gamb. 2.2).

2. Buat model masalah dan isikan sel untuk nilai pembolehubah (pada mulanya sel x (dan x z diisi dengan sewenang-wenangnya nilai berangka, sebagai contoh, nilai 10), fungsi objektif (sel mengandungi formula) dan kekangan (sel mengandungi formula)
(Gamb. 2.2)

3. Jalankan arahan Perkhidmatan Cari penyelesaian dan tetapkan nilai yang diperlukan dalam medan kotak dialog Mencari penyelesaian menambah sekatan pada tetingkap Menambah sekatan.

Komen. Di tingkap Menambah sekatan jika perlu, adalah mungkin untuk menetapkan sekatan ke atas integriti pembolehubah model.

4. Klik pada butang Laksanakan dan tetapkan parameter dalam tetingkap Hasil carian penyelesaian(tukar Simpan penyelesaian yang ditemui atau Pulihkan nilai asal Dan Jenis laporan).

Ulasan: Jika terdapat ralat dalam formula, kekangan atau parameter model yang salah, mesej berikut mungkin muncul dalam tetingkap ini: "Nilai sel sasaran tidak bertumpu," "Cari tidak dapat mencari penyelesaian," atau "Syarat model linear tidak dipenuhi .” Dalam kes ini, suis harus ditetapkan pada kedudukan Pulihkan nilai asal, semak data pada helaian dan ulangi prosedur untuk mencari penyelesaian.

5. Akibatnya, dalam sel dengan pembolehubah tugas nilai yang sepadan dengan pelan optimum akan muncul (80 penerbangan tangga dan 70 papak lantai setiap hari), dan dalam sel untuk fungsi objektif - nilai keuntungan (23,000 rubel) sepadan rancangan ini(Gamb. 2.3)

6. Jika penyelesaian yang diperolehi adalah memuaskan, anda boleh menyimpan pelan optimum dan melihat hasil carian, yang dipaparkan pada helaian berasingan.

Senaman:

Cth. 2.1. Syarikat itu mengeluarkan televisyen, sistem stereo dan Sistem akustik menggunakan gudang biasa komponen. Stok casis di gudang ialah 450 pcs., tiub gambar - 250 pcs., pembesar suara - 800 pcs., bekalan kuasa - 450 pcs., papan - 600 pcs. Setiap produk memerlukan bilangan komponen yang ditunjukkan dalam jadual:

Keuntungan daripada pengeluaran satu TV ialah 90 USD, satu sistem stereo – 50 dan sistem audio – 45. Ia adalah perlu untuk mencari nisbah optimum volum keluaran produk di mana keuntungan daripada pengeluaran semua produk akan menjadi maksimum.

Untuk menyelesaikan masalah pengaturcaraan linear kaedah simplex dalam persekitaran MS Excel, sel diisi dengan data sumber dalam mod nombor dan formula model matematik.

MS Excel membolehkan anda mendapatkan penyelesaian yang optimum tanpa mengehadkan dimensi sistem ketaksamaan fungsi objektif.

Mari kita selesaikan masalah produk perkilangan menggunakan kaedah simpleks menggunakan tambahan "Carian Penyelesaian" dalam MS Excel.

1. Isi Hamparan Excel dalam mod nombor (Gamb. 1)

2. Isikan jadual Excel dalam mod formula (Gamb. 2)

Rajah.1 Jadual dalam mod nombor

Rajah 1 Jadual dalam mod formula

Di sini: B9:C9 – hasil ( kuantiti optimum produk setiap jenis);

В6:С6 – pekali bagi fungsi objektif;

B10 – nilai fungsi objektif;

В3:С5 – pekali had;

D12:D14 – sebelah kanan sekatan;

B12:B14 – nilai dikira (sebenar) di sebelah kiri sekatan.

Mari selesaikan masalah menggunakan arahan Carian Data/Penyelesaian. Kotak dialog Cari Penyelesaian muncul pada skrin.

Dalam medan Tetapkan fungsi objektif, pautan ke sel aktif, iaitu pada B10. Lebih-lebih lagi, pautan ini adalah mutlak. Dalam bahagian Sama, tetapkan suis kepada nilai Maksimum (minimum) bergantung pada fungsi sasaran. Sekatan ditetapkan menggunakan butang Tambah, yang membuka kotak dialog input Tambah Sekatan.

Dalam medan Pautan Sel: input, nyatakan alamat sel yang mengandungi formula di sebelah kiri kekangan. Kemudian tanda nisbah dipilih daripada senarai. Medan Sekatan menentukan alamat sel yang mengandungi sebelah kanan sekatan. Klik pada butang Tambah dan ulangi sehingga kekangan seterusnya. Selepas memasukkan semua sekatan, klik OK.

Memandangkan semua pembolehubah membawa keadaan bukan negatif, kepositifannya ditetapkan melalui butang Parameter dalam kotak dialog Cari Penyelesaian. Selepas mengklik padanya, tetingkap Pilihan Carian Penyelesaian muncul pada skrin.

Tandai kotak semak Jadikan pembolehubah tidak terhad bukan negatif dan pilih Kaedah penyelesaian Cari penyelesaian kepada masalah linear menggunakan kaedah simpleks. Klik pada butang Cari Penyelesaian.

Excel akan membentangkan tetingkap Keputusan Carian Penyelesaian dengan mesej bahawa penyelesaian telah ditemui atau penyelesaian yang tidak dapat mencari penyelesaian yang sesuai.

Jika pengiraan berjaya, Excel akan membentangkan tetingkap ringkasan berikut. Anda boleh menyimpannya atau membuangnya. Di samping itu, anda boleh mendapatkan salah satu daripada tiga jenis laporan (Hasil , Kelestarian , Had) yang membolehkan kita lebih memahami hasil yang diperoleh, termasuk menilai kebolehpercayaannya.



Selepas penyelesaian ditemui, bilangan optimum produk bagi setiap jenis akan muncul dalam sel B9:C9.

Apabila menyimpan laporan, pilih – Laporkan hasil (Gamb. 3).

Laporan menunjukkan bahawa sumber 1 tidak digunakan sepenuhnya oleh 150 kg, manakala sumber 2 dan 3 digunakan sepenuhnya.

Hasilnya, pelan optimum telah diperolehi di mana produk jenis 1 mesti dihasilkan dalam jumlah 58 keping, dan produk jenis 2 dalam jumlah 42 keping. Pada masa yang sama, keuntungan daripada jualan mereka adalah maksimum dan berjumlah 4,660 ribu rubel.

Rajah.3 Laporan keputusan

1. Kereta api penumpang dan laju yang terdiri daripada tempat duduk simpanan, petak dan gerabak lembut berlepas setiap hari dari stesen pembentukan. Bilangan tempat duduk dalam kereta tempat duduk yang ditempah ialah 54, dalam kereta petak – 36, dalam kereta lembut – 18. Jadual menunjukkan komposisi setiap jenis kereta api dan bilangan kereta yang terdapat dalam armada pelbagai jenis. Tentukan bilangan kereta api laju dan penumpang yang perlu dibentuk setiap hari supaya jumlah penumpang yang diangkut adalah maksimum.



Menyelesaikan masalah pengangkutan

Masalah pengangkutan adalah tugas untuk menentukan rancangan optimum untuk mengangkut kargo dari tempat berlepas tertentu ke tempat penggunaan tertentu.

b 1 b 2 … b k … b g
a 1 }

ARTIKEL BERKAITAN

Kami mengesyorkan

Hak Cipta 2024 - Pembaikan komputer dan komputer riba. Kad video, cakera keras, Internet, monitor.